A Selection of Recent Lattice-Based Signature and Encryption Schemes

Bansarkhani, Rachid El; Cabarcas, Daniel; Kuo, Po-Chun; Schmidt, Patrick; Schneider, Michael

doi:10.2478/v10127-012-0040-x

Abstract

It is known that the development of quantum computers will break the cryptographic schemes that are in use today. Since Shor’s algorithm is able to solve the factoring and discrete logarithm problems, all cryptographic systems based on these two problems will get broken in the presence of large-scale quantum computers. Lattice-based schemes, however, are considered secure against attacks with these new machines. In this paper we present an overview of lattice-based cryptosystems, showing the most recent and the most promising candidates for encryption and signatures based on lattice problems. We explain the advantages and disadvantages of the cryptographic schemes. We also adjoin details about zero knowledge identification. With this work we try to give insight to one of the most promising candidates of future cryptography, for the time when potential quantum computers exist. We also point out drawbacks of these systems, which discloses directions for future work in lattice-based cryptography.

References

[Ajt96] AJTAI, M.: Generating hard instances of lattice problems (extended abstract), in: Proc. of the 28th Annual ACM Symposium on the Theory of Comput.-STOC ’96, Philadelphia, USA, 1996, ACM, New York, pp. 99-108.10.1145/237814.237838
Search in Google Scholar
[Ajt99] AJTAI, M.: Generating hard instances of the short basis problem, in: Automata, Languages and Programming, 26th Internat. Colloq.-ICALP ’99 (J. Wiedermann et al., eds.), Prague, 1999, Lecture Notes in Comput. Sci., Vol. 1644, Springer, Berlin, 1999, pp. 1-9.
Search in Google Scholar
[AP09] ALWEN, J.-PEIKERT, CH.: Generating shorter bases for hard random lattices, in: 26th Internat. Symposium on Theoretical Aspects of Comput. Sci.-STACS ’09 (S. Albers et al., eds.), Freiburg, Germany, 2009, LIPICS-Leibniz Internat. Proc. in Informatics, Vol. 3, Schloss Dagstuhl Leibniz Zentrum f¨ur Informatik, Wadern, 2009, pp. 75-86.
Search in Google Scholar
[BD10] BENDLIN, R.-DAMG˚ARD, I.: Threshold decryption and zero-knowledge proofs for lattice-based cryptosystems, in: Theory of Cryptography, 7th Theory of Cryptography Conf.-TCC ’10 (D. Micciancio, ed.), Zurich, Switzerland, 2010, Lecture Notes in Comput. Sci., Vol. 5978, Springer, Berlin, 2010, pp. 201-218.
Search in Google Scholar
[BDS08] BUCHMANN, J.-DAHMEN, E.-SCHNEIDER, M.: Merkle tree traversal revisited, in: Post-Guantum Cryptography, 2nd Internat. Workshop-PQCrypto ’08 (J. Buchmann et al., eds.), Cincinnati, OH, USA, 2008, Lecture Notes in Comput. Sci., Vol. 5299, Springer, Berlin, 2008, pp. 63-78.
Search in Google Scholar
[BGV11] BRAKERSKI, Z.-GENTRY, C.-VAIKUNTANATHAN, V.: Fully homomorphic encryption without bootstrapping, Electronic Colloq. Comput. Complex. (ECCC) 18 (2011), p. 111.
Search in Google Scholar
[BV11] BRAKERSKI, Z.-VAIKUNTANATHAN, V.: Fully homomorphic encryption from ring-LWE and security for key dependent messages, in: Advances in Cryptology- -CRYPTO ’11, 31st Annual Cryptology Conf. (P. Rogaway, ed.), Santa Barbara, CA, USA, 2011, Lecture Notes in Comput. Sci., Vol. 6841, Springer, Berlin, 2011, pp. 505-524.
Search in Google Scholar
[CLRS10] CAYREL, P.-L.-LINDNER, R.-RÜCKERT, M.-SILVA, R.: Improved zero-knowledge identification with lattices, in: Provable Security, 4th Internat. Conf.- -ProvSec ’10 (S.H. Heng et al., eds.), Malacca, Malaysia, 2010, Lecture Notes in Comput. Sci., Vol. 6402, Springer, Berlin, 2010, pp. 1-17.
Search in Google Scholar
[FFS88] FEIGE, U.-FIAT, A.-SHAMIR, A.: Zero-knowledge proofs of identity, J. Cryp-tology 1 (1988), 77-94.10.1007/BF02351717
Search in Google Scholar
[Gen09] GENTRY, C.: Fully homomorphic encryption using ideal lattices, in: Proc. of the 41st Annual ACM Symposium on Theory of Comput.-STOC ’09, (M. Mitzen-macher, ed.), Bethesda, MD, USA, 2009, ACM, New York, 2009, pp. 169-178.10.1145/1536414.1536440
Search in Google Scholar
[GFS12] GÖTTERT,N.-FELLER, T.-SCHNEIDER,M.-HUSS, S.A.-BUCHMANN,J.: On the design of hardware building blocks for modern lattice-based encryption schemes, in: Workshop on Cryptograph. Hardware and Embedded Syst.-CHES ’12 (E. Prouff and P. Schaumont, eds.), Leuven, Belgium, Lecture Notes in Comput. Sci., Vol. 7428, Springer, Berlin, 2012, pp. 512-529.
Search in Google Scholar
[GG00] GOLDREICH,O.-GOLDWASSER,S.: On the limits of nonapproximability of lattice problems, J. Comput. System Sci. 60 (2000), 540-563.10.1006/jcss.1999.1686
Search in Google Scholar
[GGH96] GOLDREICH, O.-GOLDWASSER, S.-HALEVI, S.: Public-key cryptosystems from lattice reduction problems, Electronic Colloq. on Computational Complexity (ECCC) 3 (1996).
Search in Google Scholar
[GGH97] GOLDREICH, O.-GOLDWASSER, S.-HALEVI, S.: Public-key cryptosystems from lattice reduction problems, in: Advances in Cryptology-CRYPTO ’97, 17th Annual Internat. Cryptology Conf. B. S. Kaliski, Jr., ed.), Santa Barbara, CA, USA, 1997, Lecture Notes in Comput. Sci., Vol. 1294, Springer, Berlin, 1997, pp. 112-131.
Search in Google Scholar
[GPV08] GENTRY, C.-PEIKERT, C.-VAIKUNTANATHAN, V.: Trapdoors for hard lattices and new cryptographic constructions, in: Proc. of the 40th Annual ACM Symposium on Theory of Comput.-STOC ’08 Victoria, Canada, 2008, ACM, New York, pp. 197-206.10.1145/1374376.1374407
Search in Google Scholar
[HPS96] HOFFSTEIN, J.-PIPHER, J.-SILVERMAN, J. H.: NTRU: a new high speed public key cryptosystem, Preprint; presented at the rump session of Crypto ’96, 1996.
Search in Google Scholar
[KTX08] KAWACHI, A.-TANAKA, K.-XAGAWA, K.: Concurrently secure identification schemes based on the worst-case hardness of lattice problems, in: Advances in Cryptology-ASIACRYPT ’08, 14th Internat. Conf. on the Theory and Appl. of Cryptol. and Inform. Security (J. Pieprzyk, ed.), Melbourne, Australia, 2008, Lecture Notes in Comput. Sci., Vol. 5350, Springer, Berlin, 2008, pp. 372-389.
Search in Google Scholar
[LM06] LYUBASHEVSKY, V.-MICCIANCIO, D.: Generalized compact knapsacks are collision resistant, in: Automata, Languages and Programming, 33rd Internat. Colloq.-ICALP ’06, Venice, Italy, 2006, Lecture Notes in Comput. Sci., Vol. 4052, Springer, Berlin, 2006, pp. 144-155.
Search in Google Scholar
[LM08] LYUBASHEVSKY, V.-MICCIANCIO, D.: Asymptotically efficient lattice-based digital signatures, in: Theory of Cryptography, 14th Theory of Cryptography Conf.-TCC ’08, New York, USA, 2008, Lecture Notes in Comput. Sci., Vol. 4948, Springer, Berlin, 2008, pp. 37-54.
Search in Google Scholar
[LP11] LINDNER, R.-PEIKERT, C.: Better key sizes (and attacks) for LWE-based encryption, in: Topics in Cryptology-CT-RSA ’11, The Cryptographers’ Track at the RSA Conf. (A. Kiayias, ed.), San Francisco, CA, USA, 2011, Lecture Notes in Comput. Sci., Vol. 6558, Springer, Berlin, 2011, pp. 319-339.
Search in Google Scholar
[LPR10] LYUBASHEVSKY, V.-PEIKERT, C.-REGEV, O.: On ideal lattices and learning with errors over rings, in: Advances in Cryptology-EUROCRYPT ’10, 29th Annual Internat. Conf. on the Theory and Appl. of Cryptogr. Tech. (H. Gilbert, ed.), French Riviera, 2010, Lecture Notes in Comput. Sci., Vol. 6110, Springer, Berlin, 2010, pp. 1-23.
Search in Google Scholar
[Lyu08a] LYUBASHEVSKY, V.: Lattice-based identification schemes secure under active attacks, in: Public key Cryptography-PKC ’08, 11th Internat. Workshop on Practice and Theory in Public-Key Cryptography (R. Cramer, ed.), Barcelona, Spain, 2008, Lecture Notes in Comput. Sci., Vol. 4939, Springer, Berlin, 2008, pp. 162-179.
Search in Google Scholar
[Lyu08b] LYUBASHEVSKY, V.: Towards practical lattice-based cryptography, PhD Thesis, University of California, San Diego, 2008.
Search in Google Scholar
[Lyu09] LYUBASHEVSKY, V.: Fiat-Shamir with Aborts: Applications to lattice and factoring-based signatures, in: Advances in Cryptology-ASIACRYPT ’09, 15th Internat. Conf. on the Theory and Appl. of Cryptology and Information Security (M. Matsui, ed.), Tokyo, Japan, 2009, Lecture Notes in Comput. Sci., Vol. 5912, Springer, Berlin, 2009, pp. 598-616.
Search in Google Scholar
[Lyu12] LYUBASHEVSKY, V.: Lattice signatures without trapdoors, in: Advances in Cryptology-EUROCRYPT ’12, 31st Annual Internat. Conf. on the Theory and Appl. of Cryptogr. Techniques (D. Pointcheval et al., eds.), Cambridge, UK, 2012, Lecture Notes in Comput. Sci., Vol. 7237, Springer, Berlin, 2012, pp. 738-755.
Search in Google Scholar
[Mic10] MICCIANCIO, D.: Duality in lattice cryptography, in: 13th Internat. Conf. on Practice and Theory in Public Key Cryptography-PKC ’10, Paris, France, 2010 (invited talk).
Search in Google Scholar
[MP12] MICCIANCIO, D.-PEIKERT, CH.: Trapdoors for lattices: simpler, tighter, faster, smaller, in: Advances in Cryptology-EUROCRYPT ’12, 31st Annual Internat. Conf. on the Theory and Appl. of Cryptogr. Techniques (D. Pointcheval et al., eds.), Cambridge, UK, 2012, Springer, Berlin, Vol. 7237, pp. 700-718.10.1007/978-3-642-29011-4_41
Search in Google Scholar
[MR07] MICCIANCIO, D.-REGEV, O.: Worst-case to average-case reductions based on Gaussian measures, SIAM J. Comput. 37 (2007), 267-302.10.1137/S0097539705447360
Search in Google Scholar
[MR08] MICCIANCIO, D.-REGEV, O.: Lattice-based cryptography, in: Post-Quantum Cryptography-PQC ’08, 2nd Internat. Workshop, Cincinnati, OH, USA, 2008, Lecture Notes in Comput. Sci., Vol. 5299, Springer, Berlin, 2008, pp. 147-191.
Search in Google Scholar
[MV03] MICCIANCIO, D.-VADHAN, S.: Statistical zero-knowledge proofs with efficient provers: lattice problems and more, in: Advances in Cryptology-CRYPTO ’03, 23rd Annual Internat. Cryptology Conf. (D. Boneh, ed.), Santa Barbara, California, USA, 2003, Lecture Notes in Comput. Sci., Vol. 2729, Springer, Berlin, 2003, pp. 282-298.
Search in Google Scholar
[Pei09] CHRIS PEIKERT: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract, in: Proc. of the 41st Annual ACM Symposium on Theory of Comput.-STOC ’09 (M. Mitzenmacher, ed.), Bethesda, MD, USA, 2009, ACM, New York, 2009, pp. 333-342.10.1145/1536414.1536461
Search in Google Scholar
[Pei10] PEIKERT, CH.: An efficient and parallel Gaussian sampler for lattices, in: Advances in Cryptology-CRYPTO ’10, 30th Annual Cryptology Conf. (T. Rabin, ed.), Santa Barbara, CA, USA, 2010, Lecture Notes in Comput. Sci., Vol. 6223, Springer, Berlin, 2010, pp. 80-97.
Search in Google Scholar
[PV08] PEIKERT, CH.-VAIKUNTANATHAN, V.: Noninteractive statistical zero-knowledge proofs for lattice problems, in: Advances in Cryptology-CRYPTO ’08, 28th Annual Internat. Cryptology Conf., Santa Barbara, CA, USA, 2008, Lecture Notes in Comput. Sci., Vol. 5157, Springer, Berlin, 2008, pp. 536-553.
Search in Google Scholar
[Reg05] REGEV, O.: On lattices, learning with errors, random linear codes, and cryptography, in: Proc. of the 37th Annual ACM Symp. on Theory of Comput.-STOC ’05, Baltimore, USA, 2005, ACM, New York, 2005, pp. 84-93.10.1145/1060590.1060603
Search in Google Scholar
[SCL11] SILVA, R.-CAYREL, P.-L.-LINDNER, R.: La tt ice- ba sed z ero -know l ed geiden ti -fication with low communication cost, in: XI Simposio Brasileiro de Seguranca da Informacao e de Sistemas Computacionais-SBSEG ’11, Brasil, 2011, pp. 95-107.10.5753/sbseg.2011.20566
Search in Google Scholar
[SS11] STEHLÉ, D.-STEINFELD, R.: Making NTRU as secure as worst-case problemso ver ideal lat ti ces, in: Advances in Cryptology-EUROCRYPT ’11, 30th Annual Internat. Conf. on the Theory and Appl. of Cryptogr. Tech. (K. G. Paterson, ed.), Tallinn, Estonia, 2011, Lecture Notes in Comput. Sci., Vol. 6632, Springer, Berlin, 2011, pp. 27-47.
Search in Google Scholar
[SSTX09] STEHLÉ, D.-STEINFELD, R.-TANAKA, K.-XAGAWA, K.: Efficient public key encryption based on ideal lattices, in: Advances in Cryptology-ASIA-CRYPT ’09, 15th Internat. Conf. on the Theory and Appl. of Cryptology and Inform. Security (M. Matsui, ed.), Tokyo, Japan, 2009, Lecture Notes in Comput. Sci., Vol. 5912, Springer, Berlin, 2009, pp. 617-635.
Search in Google Scholar
[Ste96] STERN, J.: A new paradigm for public key identification, IEEE Trans. Inform. Theory 42 (1996), 1757-1768.10.1109/18.556672
Search in Google Scholar
[XT09] XAGAWA, K.-TANAKA, K.: Zero-knowledge protocols for NTRU: application to identification and proof of plaintext knowledge, in: The Provable Security- -ProvSec ’09 (J. Pieprzyk et al., eds.), Guangzhou, China, 2009, Lecture Notes in Comput. Sci., Vol. 5848, Springer, Berlin, 2009, pp. 198-213.
Search in Google Scholar

A Selection of Recent Lattice-Based Signature and Encryption Schemes

Abstract

Paradigm

My account