Lattice-based cryptography

Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA or Diffie-Hellman cryptosystems, which are easily attacked by a quantum computer, some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are known to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.

History

In 1996, Miklós Ajtai introduced the first lattice-based cryptographic construction whose security could be based on the hardness of well-studied lattice problems.^[1] Fundamentally, Ajtai's result was a worst-case to average-case reduction. I.e., he showed that a certain average-case lattice problem, known as Short Integer Solutions (SIS), is at least as hard to solve as a worst-case lattice problem. He then showed a cryptographic hash function whose security is equivalent to the computational hardness of SIS.

Also in 1996, Jeffrey Hoffstein (de), Jill Pipher, and Joseph H. Silverman introduced a lattice-based public-key encryption scheme, known as NTRU.^[2] However, their scheme is not known to be at least as hard as solving a worst-case lattice problem.

The first lattice-based public-key encryption scheme with provable security was introduced by Oded Regev in 2005,^[3] together with the Learning with Errors problem (LWE). Since then, much follow-up work has focused on improving Regev's security proof^[4][5] and improving the efficiency of the original scheme.^[6][7][8][9] Much more work has been devoted to constructing additional cryptographic primitives based on LWE and related problems. In 2009, Craig Gentry introduced the first fully homomorphic encryption scheme, which was based on a lattice problem.^[10]

Mathematical background

A lattice is the set of all integer linear combinations of basis vectors . I.e., For example, is a lattice, generated by the standard orthonormal basis for . Crucially, the basis for a lattice is not unique. For example, the vectors , , and form an alternative basis for .

The most important lattice-based computational problem is the Shortest Vector Problem (SVP or sometimes GapSVP), which asks us to approximate the minimal Euclidean length of a non-zero lattice vector. This problem is thought to be hard to solve efficiently, even with approximation factors that are polynomial in , and even with a quantum computer. Many (though not all) lattice-based cryptographic constructions are known to be secure if SVP is in fact hard in this regime.

Lattice-based cryptosystems

On June 25, 2009, Craig Gentry using lattice-based cryptography showed the first fully homomorphic encryption scheme as announced by IBM.^[11][12][13] His scheme supports evaluations of arbitrary depth circuits.

Encryption

• Peikert's Ring - Learning With Errors (Ring-LWE) Key Exchange^[7]
• GGH encryption scheme
• NTRUEncrypt

Signature

• Gunesyu, Lyubashevsky, and Poppleman's Ring - Learning with Errors (Ring-LWE) Signature^[14]
• GGH signature scheme
• NTRUSign

Hash function

• SWIFFT
• LASH (Lattice Based Hash Function)^[15][16]

Security

Lattice-based cryptographic constructions are the leading candidates for public-key post-quantum cryptography.^[17] Indeed, the main alternatives to lattice-based cryptography are schemes based on the hardness factoring and related problems and schemes based on the hardness of the discrete logarithm and related problems. However, both factoring and the discrete logarithm are known to be solvable in polynomial time on a quantum computer.^[18] Furthermore, algorithms for factorization tend to yield algorithms for discrete logarithm, and vice versa. This further motivates the study of constructions based on alternative assumptions, such as the hardness of lattice problems.

Many lattice-based cryptographic schemes are known to be secure assuming the worst-case hardness of certain lattice problems.^[1][3][4] I.e., if there exists an algorithm that can efficiently break the cryptographic scheme with non-negligible probability, then there exists an efficient algorithm that solves a certain lattice problem on any input. In contrast, cryptographic schemes based on, e.g., factoring would be broken if factoring were hard ``on an average input,'' even if factoring were in fact hard in the worst case. However, for the more efficient and practical lattice-based constructions (such as schemes based on NTRU and even schemes based on LWE with more aggressive parameters), such worst-case hardness results are not known. For some schemes, worst-case hardness results are known only for certain structured lattices.^[6]

Functionality

For many cryptographic primitives, the only known constructions are based on lattices or closely related objects. These primitives include fully homomorphic encryption,^[10] indistinguishability obfuscation,^[19] cryptographic multilinear maps, and functional encryption.^[19]

See also

• Lattice problems
• Learning with errors
• Post-quantum cryptography
• Ring learning with Errors Key Exchange

References

1. 1 2 Ajtai, Miklós (1996). "Generating Hard Instances of Lattice Problems". Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. pp. 99–108. ISBN 0-89791-785-5. doi:10.1145/237814.237838. 
2. ↑ Hoffstein, Jeffrey; Pipher, Jill; Silverman, Joseph H. (1998-06-21). "NTRU: A ring-based public key cryptosystem". Algorithmic Number Theory. Springer, Berlin, Heidelberg: 267–288. doi:10.1007/bfb0054868. 
3. 1 2 Regev, Oded (2005-01-01). "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography". Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing. STOC '05. New York, NY, USA: ACM: 84–93. ISBN 1581139608. doi:10.1145/1060590.1060603. 
4. 1 2 Peikert, Chris (2009-01-01). "Public-key Cryptosystems from the Worst-case Shortest Vector Problem: Extended Abstract". Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing. STOC '09. New York, NY, USA: ACM: 333–342. ISBN 9781605585062. doi:10.1145/1536414.1536461. 
5. ↑ Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien (2013-01-01). "Classical Hardness of Learning with Errors". Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing. STOC '13. New York, NY, USA: ACM: 575–584. ISBN 9781450320290. doi:10.1145/2488608.2488680. 
6. 1 2 Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010-05-30). "On Ideal Lattices and Learning with Errors over Rings". Advances in Cryptology – EUROCRYPT 2010. Springer, Berlin, Heidelberg: 1–23. doi:10.1007/978-3-642-13190-5_1. 
7. 1 2 Peikert, Chris (2014-07-16). "Lattice Cryptography for the Internet" (PDF). IACR. Retrieved 2017-01-11. 
8. ↑ Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015-01-01). "Post-quantum key exchange - a new hope". 
9. ↑ Bos, Joppe; Costello, Craig; Ducas, Léo; Mironov, Ilya; Naehrig, Michael; Nikolaenko, Valeria; Raghunathan, Ananth; Stebila, Douglas (2016-01-01). "Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE". 
10. 1 2 Gentry, Craig (2009-01-01). A Fully Homomorphic Encryption Scheme (Thesis). Stanford, CA, USA: Stanford University. 
11. ↑ Gentry, Craig (2009). Fully homomorphic encryption using ideal lattices. Proceedings of the forty-first annual ACM symposium on Theory of computing. pp. 169–178. ISBN 978-1-60558-506-2. doi:10.1145/1536414.1536440. 
12. ↑ "IBM Researcher Solves Longstanding Cryptographic Challenge". IBM Research. 2009-06-25. Retrieved 2017-01-11. 
13. ↑ Michael Cooney (2009-06-25). "IBM touts encryption innovation". Computer World. Retrieved 2017-01-11. 
14. ↑ Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). "Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems" (PDF). IACR. doi:10.1007/978-3-642-33027-8_31. Retrieved 2017-01-11. CS1 maint: Date and year (link)
15. ↑ "LASH: A Lattice Based Hash Function". Archived from the original on October 16, 2008. Retrieved 2008-07-31. CS1 maint: BOT: original-url status unknown (link) (broken)
16. ↑ Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Ron Steinfeld, Jian Guo, San Ling and Huaxiong Wang (2008). "Cryptanalysis of LASH" (PDF). doi:10.1007/978-3-540-71039-4_13. CS1 maint: Uses authors parameter (link)
17. ↑ Micciancio, Daniele; Regev, Oded (2008-07-22). "Lattice-based cryptography" (PDF). Retrieved 2017-01-11. 
18. ↑ Shor, Peter W. (1997-10-01). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing. 26 (5): 1484–1509. ISSN 0097-5397. doi:10.1137/S0097539795293172. 
19. 1 2 Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (2013-01-01). "Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits". 

Bibliography

• Oded Goldreich, Shafi Goldwasser, and Shai Halevi. "Public-key cryptosystems from lattice reduction problems". In CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, pages 112–131, London, UK, 1997. Springer-Verlag.
• Phong Q. Nguyen. "Cryptanalysis of the Goldreich–Goldwasser–Halevi cryptosystem from crypto ’97". In CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288–304, London, UK, 1999. Springer-Verlag.
• Chris Peikert, “Public-key cryptosystems from the worst-case shortest vector problem: extended abstract,” in Proceedings of the 41st annual ACM symposium on Theory of computing (Bethesda, MD, USA: ACM, 2009), 333–342, DOI 10.1145/1536414.1536461
• Oded Regev. Lattice-based cryptography. In Advances in cryptology (CRYPTO), pages 131–141, 2006.