# Post-quantum cryptography

Post-quantum cryptography refers to research on cryptographic primitives (usually public-key cryptographic systems) that are not efficiently breakable using quantum computers more than classical computer architectures. This term came about because most currently popular public-key cryptographic systems rely on the integer factorization problem or discrete logarithm problem, both of which would be easily solvable on large enough quantum computers using Shor's algorithm.[1][2] Even though current publicly known experimental quantum computing is nowhere near powerful enough to attack real cryptographic systems,[3] many cryptographers are researching new algorithms in case quantum computing becomes a threat in the future. This work has been popularized by the PQCrypto conference series since 2006.[4][5]

In contrast, most current symmetric cryptographic systems (symmetric ciphers and hash functions) are secure from quantum computers.[2][6] The quantum Grover's algorithm can speed up attacks against symmetric ciphers, but this can be counteracted by increasing key size.[7] Thus post-quantum symmetric cryptography does not differ significantly from conventional symmetric cryptography. See Section on Symmetric Key Approach below.

Post-quantum cryptography is also distinct from quantum cryptography, which refers to using quantum phenomena to achieve secrecy.

## Algorithms

Currently post-quantum cryptography is mostly focused on six different approaches:[2][5]

### Lattice-based Cryptography

This includes cryptographic systems such as Ring-Learning with Errors[8][9] or the older NTRU or GGH encryption schemes. According to Micciancio and Regev, Lattice-based Cryptography can be divided into two categories: practical and efficiency oriented schemes like NTRU which do not possess a proof of security and theoretical schemes like matrix based Learning with Errors schmes that offer strong proofs of security but use keys which are too large for general use.[10] Research since 2008, however, has been able to merge these two categories and create a new class of cryptographic systems based on lattice problems which are both efficient like NTRU and provably secure like standard LWE. These are the Ring-LWE cryptosystems.[11] While there are many patents on the use of Ring-LWE techniques in homomorphic encryption there appear to be no patents on Ring-LWE techniques for key exchange or signature.

### Multivariate Cryptography

This includes cryptographic systems such as the Rainbow (Unbalanced Oil and Vinegar) scheme which is based on the difficulty of solving systems of multivariate equations. As noted in the linked Wikipedia article, various attempts to build secure multivariate equation encryption schemes have failed. However, multivariate signature schemes like Rainbow could provide the basis for a quantum secure digital signature.[12] There is a patent on the Rainbow Signature Scheme

### Hash-based Cryptography

This includes cryptographic systems such as Lamport signatures and the Merkle signature scheme Hash based digital signatures were invented in the late 1970s by Ralph Merkle and have been studied ever since as an interesting alternative to number theoretic digital signatures like RSA and DSA. Their primary drawback is that for any Hash based public key, there is a limit on the number of signatures that can be signed using the corresponding set of private keys. This fact reduced interest in this signature until there was increased interest in cryptography that was resistant to attack by quantum computers. There appear to be no patents on the Merkle signature scheme and there exist many non-patented hash functions that could be used with this scheme

### Code-based Cryptography

This includes cryptographic systems which rely on error-correcting codes, such as McEliece encryption and Niederreiter signatures The original McEliece signature using random Goppa codes has withstood scrutiny for over 30 years. 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.[13] There appear to be no patents on the McEliece encryption algorithm

### Supersingular Elliptic Curve Isogeny Cryptography

This cryptographic system relies on the properties of supersingular elliptic curves to create a Diffie-Hellman replacement with forward secrecy [14] This cryptographic system uses the well studied mathematics of supersingular elliptic curves to create a Diffie-Hellman like key exchange that can serve as a Quantum computing resistant replacement for the Diffie-Hellman and Elliptic Curve Diffie-Hellman key exchange methods that are in widespread use today. Because it works much like existing Diffie-Hellman implementations, it offers Forward Secrecy which is viewed as important both to prevent mass surveillance by governments but also to protect against the compromise of long term keys through failures.[15] In 2012, researchers Sun, Tian and Wang of the Chinese State Key Lab for Integrated Service Networks and Xidian University, extended the work of De Feo, Jao, and Plut to create quantum secure digital signatures based on supersingular elliptic curve isogenies.[16] There are no patents covering this cryptographic system.[17]

### Symmetric Key Quantum Resistance

Provided one uses sufficiently large key sizes, the symmetric key cryptographic systems like AES and SNOW 3G are already resistant to attack by a quantum computer.[18] Further, key management systems and protocols that use symmetric key cryptography instead of public key cryptography like Kerberos and the 3GPP Mobile Network Authentication Structure are also inherently secure against attack by a quantum computer. Given its widespread deployment in the world already, some researchers recommend expanded use of Kerberos-like symmetric key management as an efficient and effective way to get Post Quantum cryptography today.[19]

## Security Reduction

In cryptography research the provable equivalence of the security of a cryptographic algorithm to some known hard mathematical problem is viewed as an important fact in support of using a given cryptographic systems. These proofs are often called "security reductions." In other words the security of a given cryptographic algorithm is reduced to the security of a known hard problem. Researchers are actively looking for security reductions in the prospects for post quantum cryptography. Current results are given here:

### Lattice Based Cryptography - Ring-LWE Signature

Security reduction to the Shortest Vector Problem (SVP) in a Lattice is a lower bound on the security. The SVP is known to be NP-hard.[20]

### Lattice-Based Cryptography - NTRU

Security is related to but not reducible to the Closest Vector Problem (CVP) in a Lattice. The CVP is known to be NP-hard[21]

### Multivariate Cryptography - Rainbow

The Rainbow Multivariate Equation Signature Scheme is a member of a class of multivariate quadratic equation cryptosystems called "Unbalanced Oil and Vinegar Cryptosystems" (UOV Cryptosystems) Bulygin, Petzoldt and Buchmann have shown a reduction of generic multivariate quadratic UOV systems to the NP-Hard Multivariate Quadratic Equation Solving problem.[22]

### Hash Based Cryptography - Merkle Trees

In 2005, Garcia proved that there was a security reduction of Merkle Hash Tree signatures to the security of the underlying hash function. He showed that if computationally one-way hash functions exist then the Merkle Hash Tree signature is provably secure. Thus if one used a hash function with a provable reduction of security to a known hard problem one would have a provable security reduction of the Merkle Tree signature to a known hard problem. Such hash functions exist.[23]

### Code-based Cryptography - McEliece

Security reduction to the Syndrome Decoding Problem (SDP). The SDP is known to be NP-hard[24]

### Supersingular Elliptic Curve Isogeny Cryptography

Security is related to the problem of constructing an isogeny between two supersingular curves with the same number of points. The lastest investigation of the difficulty of this problem is by Delfs and Galbraith.[25]

## Key sizes

One common characteristic of many post-quantum cryptography algorithms is that they require larger key sizes than commonly used "pre-quantum" public key algorithms. There are often tradeoffs to be made in key size, computational efficiency and ciphertext or signature size. It is therefore difficult to compare one scheme against another in only one dimension like key size. However the following paragraphs provide some publicized key sizes for a fixed level of security.

### Lattice Based Cryptography - Ring-LWE Signature

For 100 bits of security in Lyubashevsy's Ring LWE signature, Guneysu, Lyubashevsky and Popplemann suggest a public key size of about 11,800 bits and a corresponding secret key size of 1620 bits. For 256 bits of security they estimate one would need to use public keys of 25,000 bits with secrets keys on the order of 3200 bits.[9]

### Lattice-Based Cryptography - NTRU

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 $\bmod{\left(2^{10}\right)}$. This results in a public key of 6130 bits. The corresponding private key would be 6743 bits.[26]

### Multivariate Cryptography - Rainbow

For 128 bits of security and the smallest signature size in a Rainbow Multivariate Quadratic Equation Signature scheme, Petzoldt, Bulygin and Buchmann, recommend using equations in $\mathbb{F}_{16}$ with a public key size of just over 1.2 million bits, a private key of just over 800,000 bits and digital signatrures which are 388 bits in length.[27]

### Hash Based Cryptography - Merkle Trees

In order to get 128 bits of security for hash based signatures to sign 1 million messages using the Fractal Merkle Tree method of Naor Shenhav and Wool the public and private key sizes are roughly 36,000 bits in length.[28]

### Code-based Cryptography - McEliece

For 128 bits of security in a McEliece scheme, Niebuhr, Meziani, Bulygin and Buchmann show that one needs to use a binary Goppa code with a code matrix of at least 2798 x 2088 and capable of correcting 62 errors. With these parameters the public key for the McEliece system will be 1,448,000 bits. According to their work the corresponding private key will be over 12 million bits in length.[29]

### Supersingular Elliptic Curve Isogeny Cryptography

For 128 bits of security in the Supersingular Isogeny Diffie-Hellman (SIDH) method, De Feo, Jao and Plut recommend using a supersingular curve modulo a 768-bit prime. If one uses elliptic curve point compression the public key will need to be no more than 4x768 or 3072 bits in length.[30]

### Symmetric Key Based Cryptography

For 128-bits of security a symmetric key based system can use key sizes of 256-bits or less. The best quantum attack against 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. To transmit an encrypted key to a device which possesses the symmetric key necessary to decrypt that key requires roughly 256 bits as well. It is clear that symmetric key systems offer the smallest key sizes for post quantum cryptography.

The following table is a summary of the information in this section giving the key sizes in bytes:

Algorithm Public key size Private key size
Ring-LWE 1,375 to 3,125 200 to 400
NTRU 763 838
Rainbow 150,000 100,000
Hash signature 4,500 4,500
McEliece 181,000 1,500,000
SIDH 384 384

One practical consideration on a choice for Post Quantum Cryptography concerns how reliably public keys can be transmitted over the internet. While Internet protocol packets can be very large, standard Ethernet frames are limited to 1500 byte payloads. A public key that requires more than one Ethernet frame for transmission may cause reliability problems, From this point of view, the Ring-LWE, NTRU, and SIDH algorithms seem best suited for general use. Hash signatures come close to being practical from a transmission standpoint. The McEliece and Rainbow schemes seem poorly suited to environments which require transmission of keys.

## Forward Secrecy

A public-key system demonstrates a property referred to as perfect forward secrecy when it generates random public keys per session for the purposes of key agreement. This means that the compromise of one message cannot lead to the compromise of others, and also that there is not a single secret value which can lead to the compromise of multiple messages. Security experts recommend using cryptographic algorithms that support forward secrecy over those that do not.[31] The reason for this is that forward secrecy can protect against the compromise of long term private keys associated with public/private key pairs. This is viewed as a means of preventing mass surveillance by intelligence agencies.

Both the Ring-LWE and Supersingular Isogeny Diffie-Hellman Key Exchange can support forward secrecy in one exchange with the other party. Both the Ring-LWE and SIDH Key Exchange can be used without forward secrecy by creating a variant of the classic ElGamal encryption variant of Diffie-Hellman

The other algorithms in this article do not support forward secrecy in one exchange. These other algorithms could be configured with forward secrecy by generating a new random public key for each key exchange and exchanging random public keys with the other party as a first exchange and then encrypting random numbers with the other party's public key and transmitting the result as a second exchange.

## References

1. ^ Peter W. Shor (1995-08-30). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". arXiv:quant-ph/9508027.
2. ^ a b c Daniel J. Bernstein (2009). "Introduction to post-quantum cryptography". (Introductory chapter to book "Post-quantum cryptography").
3. ^ New qubit control bodes well for future of quantum computing
4. ^ "Cryptographers Take On Quantum Computers". IEEE Spectrum. 2009-01-01.
5. ^ a b
6. ^
7. ^ Daniel J. Bernstein (2010-03-03). Grover vs. McEliece.
8. ^ Peikert, Chris (2014). "Lattice Cryptography for the Internet". IACR. Archived from the original on 31 January 2014. Retrieved 10 May 2014.
9. ^ a b Guneysu, Tim; Lyubashevsky; Poppelmann (2012). "Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems". INRIA. Retrieved 12 May 2014.
10. ^ Micciancio, Daniele; =Regev (2008). "Lattice-based Cryptography". UCSD.
11. ^ Lyubashevsky, Vadim; =Peikert; Regev (2013). "On Ideal Lattices and Learning with Errors Over Rings". IACR. Archived from the original on 22 July 2013. Retrieved 14 May 2013.
12. ^ Ding, Jintai; Schmidt (7 June 2005). "Rainbow, a New Multivariable Polynomial Signature Scheme". In Ioannidis, John. Third International Conference, ACNS 2005, New York, NY, USA, June 7–10, 2005. Proceedings. Lecture Notes in Computer Science 3531: 64–175. doi:10.1007/11496137_12. Retrieved 15 May 2014.
13. ^ Overbeck, Raphael; Sendrier (2009). "Code-based cryptography". In Bernstein, Daniel. Post-Quantum Cryptography (Springer Berlin Heidelberg): 95–145. doi:10.1007/978-3-540-88702-7_4. Retrieved 15 May 2014.
14. ^ De Feo, Luca; Jao; Plut (2011). "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies". PQCrypto 2011. Retrieved 14 May 2014.
15. ^ Higgins, Peter (2013). "Pushing for Perfect Forward Secrecy, an Important Web Privacy Protection". Electronic Frontier Foundation. Retrieved 15 May 2014.
16. ^ Sun, Xi; Tian; Wang (19–21 Sep 2012). "Browse Conference Publications > Intelligent Networking and Co ... Help Working with Abstracts Toward Quantum-Resistant Strong Designated Verifier Signature from Isogenies". Intelligent Networking and Collaborative Systems (INCoS), 2012 4th International Conference on (IEEE): 292–296. doi:10.1109/iNCoS.2012.70.
17. ^ "Supersingular Isogeny Key Exchange". Wikipedia. Wikipedia. 11 May 2014. Retrieved 13 July 2014.
18. ^ Perlner, Ray; Cooper (2009). "Quantum Resistant Public Key Cryptography: A Survey". NIST. Retrieved 23 May 2014.
19. ^ Campagna, Matt; Hardjono; Pintsov; Romansky; Yu (2013). "Kerberos Revisited Quantum-Safe Authentication". ETSI.
20. ^ Lyubashevsky, Vadim; Peikert; Regev (25 June 2013). "On Ideal Lattices and Learning with Errors Over Rings". http://www.cc.gatech.edu/~cpeikert/. Springer. Retrieved 19 June 2014.
21. ^ "NTRUencrypt". Wikipedia. Retrieved 18 June 2014.
22. ^ Bulygin, Stanislav; Petzoldt; Buchmann (2010). "Towards Provable Security of the Unbalanced Oil and Vinegar Signature Scheme under Direct Attacks". Progress in Cryptology - INDOCRYPT 2010. Lecture Notes in Computer Science (Springer) 6498: 17–32.
23. ^ Garcia, Luis. "On the security and the eﬃciency of the Merkle signature scheme". http://eprint.iacr.org/. IACR. Retrieved 19 June 2013.
24. ^ Blaum, Mario; Farrell; Tilborg (31 May 2002). Information, Coding and Mathematics. Springer. ISBN 978-1-4757-3585-7.
25. ^ Delfs, Christina; Galbraith. "Computing isogenies between supersingular elliptic curves over F_p". arXiv. Retrieved 19 June 2014.
26. ^ Hirschborrn, P; Hoffstein; Howgrave-Graham; Whyte. "Choosing NTRUEncrypt Parameters in Light of Combined Lattice Reduction and MITM Approaches". NTRU. Retrieved 12 May 2014.
27. ^ Petzoldt, Albrecht; Bulygin; Buchmann (2010). "Selecting Parameters for the Rainbow Signature Scheme - Extended Version -". Archived from the original on 11 Aug 2010. Retrieved 12 May 2014.
28. ^ Naor, Dalit; Shenhav; Wool (2006). "One-Time Signatures Revisited: Practical Fast Signatures Using Fractal Merkle Tree Traversal". IEEE. Retrieved 13 May 2014.
29. ^ Niebuhr, Robert; Meziani; Bulygin; Buchmann (2010). "Selecting Parameters for Secure McEliece-based Cryptosystems". CASED. Retrieved 10 May 2014.
30. ^ De Feo, Luca; Jao; Plut (2011). "TOWARDS QUANTUM-RESISTANT CRYPTOSYSTEMS FROM SUPERSINGULAR ELLIPTIC CURVE ISOGENIES". Archived from the original on October 2011. Retrieved 12 May 2014.
31. ^ Ristic, Ivan. "Deploying Forward Secrecy". SSL Labs. Retrieved 14 June 2014.