Efficient variants of the GGH-YK-M cryptosystem

• João M. M. Barguil USP
• Renan Yuri Lino USP
• Paulo S. L. M. Barreto USP

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

Resumo

The Goldreich-Goldwasser-Halevi scheme was deemed broken until recently proposed variants were shown to thwart all known attacks. However, the associated key sizes and generation times are notoriously inefficient. In this paper, we improve on the most promising such variant, proposed by Barros and Schechter and called GGH-YK-M, by reducing public key sizes rom O(n² lg n) down to O(n lg n) bits, and making key generation over 3 orders of magnitude faster than the results in the literature.

Palavras-chave: lattice-based encryption

Referências

Abraham Berman and Robert J. Plemmons. Nonnegative Matrices in the Mathematical Sciences, volume 9. Society for Industrial and Applied Mathematics (SIAM), 1994.

D. J. Bernstein, J. Buchmann, and E. Dahmen. Post-Quantum Cryptography. Springer, Heidelberg, Deutschland, 2008.

Daniel J. Bernstein. A subfield-logarithm attack against ideal lattices. Blog entry, February 2014. http://blog.cr.yp.to/20140213-ideal.html.

Massimo Chenal and Qiang Tang. On key recovery attacks against existing somewhat homomorphic encryption schemes. In International Conference on Cryptology and Information Security in Latin America – Latincrypt 2014, Lecture Notes in Computer Science. Springer, 2014. To appear.

Henri Cohen. A course in computational algebraic number theory, volume 138. Springer, 1993.

Charles F. de Barros and L. Menasché Schechter. GGH may not be dead after all. In XXXV Congresso Nacional de Matemática Aplicada e Computacional – CNMAC 2014. Sociedade Brasileira de Matemática Aplicada e Computacional – SBMAC, 2014.

E. Fujisaki and T. Okamoto. Secure integration of asymmetric and symmetric encryption schemes. In Advances in Cryptology – Crypto 1999, volume 1666 of Lecture Notes in Computer Science, pages 537–554, Santa Barbara, USA, 1999. Springer.

D. J. H. Garling. Inequalities: A Journey into Linear Analysis. Cambridge, 2007.

Craig Gentry and Shai Halevi. Implementing Gentry’s fully-homomorphic encryption scheme. In Advances in Cryptology – Eurocrypt 2011, volume 6632 of Lecture Notes in Computer Science, pages 129–148. Springer, 2011.

Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems from lattice reduction problems. In Advances in Cryptology – CRYPTO ’97, pages 112–131. Springer, 1997.

J. Hoffstein, J. Pipher, and J. Silverman. NTRU: A ring-based public key cryptosystem. In J. P. Buhler, editor, Algorithmic Number Theory, volume 1423 of Lecture Notes in Computer Science, pages 267–288. Springer Berlin Heidelberg, Oregon, USA, 1998.

Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982.

Richard Lindner and Chris Peikert. Better key sizes (and attacks) for LWE-based encryption. In Topics in Cryptology – CT-RSA 2011, volume 6558 of Lecture Notes in Computer Science, pages 319–339, San Francisco, CA, USA, 2011. Springer.

Jake Loftus, Alexander May, Nigel P. Smart, and Frederik Vercauteren. On CCA-secure somewhat homomorphic encryption. In International Conference on Selected Areas in Cryptography – SAC 2011, volume 7118 of Lecture Notes in Computer Science, pages 55–72. Springer, 2012.

Vadim Lyubashevsky and Daniele Micciancio. Generalized compact knapsacks are collision resistant. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, volume 4052 of Lecture Notes in Computer Science, pages 144–155. Springer, 2006.

Robert J McEliece. A public-key cryptosystem based on algebraic coding theory. DSN progress report, 42(44):114–116, 1978.

Daniele Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient oneway functions from worst-case complexity assumptions. In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, pages 356–365. IEEE, 2002.

Daniele Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient oneway functions. Computational Complexity, 16(4):365–411, 2007.

Phong Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from CRYPTO ’97. In Advances in Cryptology – CRYPTO ’99, pages 288–304. Springer, 1999.

Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC ’05, pages 84–93, New York, NY, USA, 2005. ACM.

Claus-Peter Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical computer science, 53(2):201–224, 1987.

P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26:1484–1509, 1995.

Nigel P. Smart and Frederik Vercauteren. Fully homomorphic encryption with relatively small key and ciphertext sizes. In P. Q. Nguyen and D. Pointcheval, editors, Public Key Cryptography – PKC 2010, volume 6056 of Lecture Notes in Computer Science, pages 420–443. Springer, 2010.

Vasilios Evangelos Tourloupis. Hermite normal forms and its cryptographic applications. Master’s thesis, University of Wollongong, 2013.

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