A New Design for Lattice-Based Cryptographic Constructions

• Charles F. de Barros UFRJ
• L. Menasché Schechter UFRJ

DOI: https://doi.org/10.5753/sbseg.2015.20096

Resumo

In this paper, we propose a new type of construction for a secure and efficient public-key cryptosystem, which is based on a new problem from the theory of lattices.

Referências

Ajtai, M. and Dwork, C. (1997). A public-key cryptosystem with worst-case/average-case equivalence. In Proc. 29th Annual ACM Symp. on Theory of Computing (STOC), pages 284–293.

Babai, L. (1986). On Lovász’ lattice reduction and the nearest lattice point problem. volume 1 of Combinatorica, pages 1–13.

Berman, A. and Plemmons, R. J. (1987). Nonnegative Matrices in the Mathematical Sciences. Classics in Applied Mathematics. SIAM.

Goldreich, O. (1999). Private communication.

Goldreich, O., Goldwasser, S., and Halevi, S. (1997). Public-key cryptosystems from lattice reduction problems. In Crypto’97, Lecture Notes in Computer Science, volume 1294, pages 112–131.

Hoffstein, J., Pipher, J., and Silverman, J. H. (1998). NTRU: a ring based public-key cryptosystem. In Proceedings of ANTS-III (LNCS), volume 1423, pages 267–288.

Lee, M. S. and Hahn, S. G. (2010). Cryptanalysis of the GGH cryptosystem. In Mathematics in Computer Science, volume 3, pages 201–208.

Lenstra, A. K., Lenstra, H. W., and Lovász, L. (1982). Factoring polynomials with rational coefficients. In Mathematische Annalen, volume 261, pages 515–534.

Lyubashevsky, V., Peikert, C., and Regev, O. (2013). On ideal lattices and learning with errors over rings. Journal of the ACM, 60(6):1–43.

Micciancio, D. (2001). Improving lattice based cryptosystems using the Hermite Normal Form. In CaLC Lecture Notes in Computer Science, volume 2146, pages 126–145.

Nguyen, P. Q. (1999). Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto’97. In Crypto’99, Lecture Notes in Computer Science, volume 1666, pages 288–304.

Regev, O. (2005). On lattices, learning with errors, random linear codes, and cryptography. In Proc. 37th ACM Symp. on Theory of Computing (STOC), pages 84–93.

Schnorr, C. P. and Euchner, M. (1994). Lattice basis reduction: improved practical algorithms and solving subset sum problems. In Math. Programming, volume 66, pages 181–199.

Shoup, V. (2015). Number Theory C++ Library (NTL) version 9.0.2. Available at http://www.shoup.net/ntl/.

Yoshino, M. and Kunihiro, N. (2012). Improving GGH cryptosystem for large error vector. In International Symposium on Information Theory and its Applications, pages 416–420.