Gröbner bases for public key cryptography

ABSTRACT

Up to now, any attempt to use Gröbner bases in the design of public key cryptosystems has failed, as anticipated by a classical paper of B. Barkee et al.; we show why, and show that the only residual hope is to use binomial ideals, i.e. lattices. We propose two lattice-based cryptosystems that will show the usefulness of multivariate polynomial algebra and Grobner bases in the construction of public key cryptosystems. The first one tries to revive two cryptosystems Polly Cracker and GGH, that have been considered broken, through a hybrid; the second one improves a cryptosystem (NTRU) that only has heuristic and challenged evidence of security, providing evidence that the extension cannot be broken with some of the standard lattice tools that can be used to break some reduced form of NTRU. Because of the bounds on length, we only sketch the construction of these two cryptosystems, and leave many details of the construction of private and public keys, of the proofs and of the security considerations to forthcoming technical papers.

REFERENCES

• 1: L Babai, On Lova´sz' lattice reduction and the nearest lattice point problem, Combinatorica, v.6 n.1, p.1-13, 1986 [doi>10.1007/BF02579403]
• 2: Boo Barkee , Deh Cac Can , Julia Ecks , Theo Moriarty , R. F. Ree, Why you cannot even hope to use Gro¨bner bases in public key cryptography: an open letter to a scientist who failed and a challenge to those who have not yet failed, Journal of Symbolic Computation, v.18 n.6, p.497-501, Dec. 1994 [doi>10.1006/jsco.1994.1061]
• 3: CoCoATeam. Cocoa: a system for doing Computations in Commutative Algebra. Available at http://cocoa.dima.unige.it.
• 4: D. Coppersmith, A. Shamir. Lattice attacks on NTRU. In Advances in Cryptology--EUROCRYPT '97, Lecture Notes in Comput. Sci., 1233:52--61, 1997.
• 5: J.-C. Faugere. A new efficient algorithm for computing Grobner bases (F4). in J. of Pure and Appl. Algebra, 139(1):61--88, 1999.
• 6: M. Fellows and N. Koblitz. Combinatorial Cryptosystems Galore! In Finite fields: theory, applications, and algorithms (Las Vegas, NV, 1993), volume 168 of Contemp. Math., pages 51--61. Amer. Math. Soc., Providence, RI, 1994.
• 7: 4ti2 team. 4ti2--A software package for algebraic, geometric and combinatorial problems on linear spaces. Available at http://www.4ti2.de
• 8: Oded Goldreich , Shafi Goldwasser , Shai Halevi, Public-Key Cryptosystems from Lattice Reduction Problems, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.112-131, August 17-21, 1997
• 9: J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman and W. Whyte Digital Signatures Using the NTRU Lattice In Topics in Cryptology--CT-RSA 2003, Lecture Notes in Comput. Sci., 2162:122--140. 2003.
• 10: Jeffrey Hoffstein , Jill Pipher , Joseph H. Silverman, NTRU: A Ring-Based Public Key Cryptosystem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.267-288, June 21-25, 1998
• 11: D. Hofheinz and R. Steinwandt. A "differential" attack on Polly Cracker. Int. J. Inf. Secur., 1:143--148, 2002.
• 12: A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász. Factoring Polynomials with Rational Coefficients. Math. Ann., 261(4):515--534, 1982.
• 13: F. Levy-dit Vehel, M. Marinari, T. Mora, L. Perret, and C. Traverso. A Survey on Polly Cracker Systems. In Gröbner Bases, Coding, and Cryptography, RISC book series. Springer, Heidelberg, (to appear).
• 14: E.W. Mayr, A.R. Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Adv. Math., 46(3):305--329, 1982.
• 15: Daniele Micciancio, Improving Lattice Based Cryptosystems Using the Hermite Normal Form, Revised Papers from the International Conference on Cryptography and Lattices, p.126-145, March 29-30, 2001
• 16: Phong Q. Nguyen, Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto '97, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.288-304, August 15-19, 1999
• 17: Phong Q. Nguyen , Jacques Stern, The Two Faces of Lattices in Cryptology, Revised Papers from the International Conference on Cryptography and Lattices, p.146-180, March 29-30, 2001
• 18: T. Plantard, W. Susilo and K. T. Win. A Digital Signature Scheme Based on CVP∞. Public Key Cryptography, PKC 2008, Lecture Notes in Comput. Sci., 4939:288--307, 2008.
• 19: C. P. Schnorr , M. Euchner, Lattice basis reduction: improved practical algorithms and solving subset sum problems, Mathematical Programming: Series A and B, v.66 n.2, p.181-199, Sept. 7, 1994 [doi>10.1007/BF01581144]
• 20: V. Shoup. NTL: A Library for doing Number Theory. Available at http://www.shoup.net/ntl/.
• 21: Carlo Traverso, Hilbert functions and the Buchberger algorithm, Journal of Symbolic Computation, v.22 n.4, p.355-376, Oct. 1996 [doi>10.1006/jsco.1996.0056]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Algorithms

Keywords:
gröbner basis, hermite normal form, lattice, public key cryptosystem