All of these problems could be easily solved on a sufficiently powerful quantum computer running Shor's algorithm[1][2] or even faster and less demanding (in terms of the number of qubits required) alternatives.
[5][6][7] The rumoured existence of widespread harvest now, decrypt later programs has also been seen as a motivation for the early introduction of post-quantum algorithms, as data recorded now may still remain sensitive many years into the future.
The stateful hash-based signature scheme XMSS developed by a team of researchers under the direction of Johannes Buchmann is described in RFC 8391.
This includes cryptographic systems which rely on error-correcting codes, such as the McEliece and Niederreiter encryption algorithms and the related Courtois, Finiasz and Sendrier Signature scheme.
However, many variants of the McEliece scheme, which seek to introduce more structure into the code used in order to reduce the size of the keys, have been shown to be insecure.
Among the more well-known representatives of this field are the Diffie–Hellman-like key exchange CSIDH, which can serve as a straightforward quantum-resistant replacement for the Diffie-Hellman and elliptic curve Diffie–Hellman key-exchange methods that are in widespread use today,[28] and the signature scheme SQIsign which is based on the categorical equivalence between supersingular elliptic curves and maximal orders in particular types of quaternion algebras.
Given its widespread deployment in the world already, some researchers recommend expanded use of Kerberos-like symmetric key management as an efficient way to get post quantum cryptography today.
[33] In cryptography research, it is desirable to prove the equivalence of a cryptographic algorithm and a known hard mathematical problem.
The security of the NTRU encryption scheme and the BLISS[17] signature is believed to be related to, but not provably reducible to, the closest vector problem (CVP) in a lattice.
[19] Unbalanced Oil and Vinegar signature schemes are asymmetric cryptographic primitives based on multivariate polynomials over a finite field
A practical consideration on a choice among post-quantum cryptographic algorithms is the effort required to send public keys over the internet.
For somewhat greater than 128 bits of security, Singh presents a set of parameters which have 6956-bit public keys for the Peikert's scheme.
In 2015, an authenticated key exchange with provable forward security following the same basic idea of Ding's was presented at Eurocrypt 2015,[56] which is an extension of the HMQV[57] construction in Crypto2005.
[56] For 128 bits of security in NTRU, Hirschhorn, Hoffstein, Howgrave-Graham and Whyte, recommend using a public key represented as a degree 613 polynomial with coefficients
[58] For 128 bits of security in a McEliece scheme, The European Commissions Post Quantum Cryptography Study group recommends using a binary Goppa code of length at least
With these parameters the public key for the McEliece system will be a systematic generator matrix whose non-identity part takes
With these parameters the public key for the McEliece system will be the first row of a systematic generator matrix whose non-identity part takes
With these parameters the public key for the McEliece system will be a systematic generator matrix whose non-identity part takes
[60] A March 2016 paper by authors Azarderakhsh, Jao, Kalach, Koziel, and Leonardi showed how to cut the number of bits transmitted in half, which was further improved by authors Costello, Jao, Longa, Naehrig, Renes and Urbanik resulting in a compressed-key version of the SIDH protocol with public keys only 2640 bits in size.
The best quantum attack against arbitrary symmetric-key systems is an application of Grover's algorithm, which requires work proportional to the square root of the size of the key space.
[63] The Open Quantum Safe (OQS) project was started in late 2016 and has the goal of developing and prototyping quantum-resistant cryptography.
It provides a common API suitable for post-quantum key exchange algorithms, and will collect together various implementations.
liboqs will also include a test harness and benchmarking routines to compare performance of post-quantum implementations.
In August 2023, Google released a FIDO2 security key implementation of an ECC/Dilithium hybrid signature schema which was done in partnership with ETH Zürich.
Apple stated that they believe their PQ3 implementation provides protections that "surpass those in all other widely deployed messaging apps", because it utilizes ongoing keying.
Apple intends to fully replace the existing iMessage protocol within all supported conversations with PQ3 by the end of 2024.
Apple also defined a scale to make it easier to compare the security properties of messaging apps, with a scale represented by levels ranging from 0 to 3: 0 for no end-to-end by default, 1 for pre-quantum end-to-end by default, 2 for PQC key establishment only (e.g. PQXDH), and 3 for PQC key establishment and ongoing rekeying (PQ3).
This is to ensure that the data are not compromised even if the relatively new PQ algorithm turns out to be vulnerable to non-quantum attacks before Y2Q.
[87] Indeed, one of the algorithms used in the 2019 test, SIKE, was broken in 2022, but the non-PQ X25519 layer (already used widely in TLS) still protected the data.
[89] The NSA and GCHQ argues against hybrid encryption, claiming that it adds complexity to implementation and transition.