Lattice Polly Cracker cryptosystems
Using Grobner bases for the construction of public key cryptosystems has been often attempted, but has always failed. We review the reason for these failures, and show that only ideals generated by binomials may give a successful cryptosystem. As a consequence, we concentrate on binomial ideals that correspond to Euclidean lattices. We show how to build a cryptosystem based on lattice ideals and their Grobner bases, and, after breaking a simple variant, we construct a more elaborate one. In this variant the trapdoor information consists in a "small" change of coordinates that allows one to recover a "fat" Grobner basis. While finding a change of coordinates giving a fat Grobner basis is a relatively easy problem, finding a small one seems to be a hard optimization problem. This paper develops the details and proofs related to computer algebra, the cryptographic details related to security, the comparison with other lattice cryptosystems and discusses the implementation. (C) 2010 Elsevier Ltd. All rights reserved.
lattice polly cracker cryptosystem grobner basis hermite normal form