Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleLattice Polly Cracker cryptosystems
Author(s) Massimo Caboara, Fabrizio Caruso, Carlo Traverso
TypeArticle in Journal
AbstractUsing Gröbner 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 Gröbner 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” Gröbner basis. While finding a change of coordinates giving a fat Gröbner 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.
KeywordsGröbner basis, Hermite normal form, Polly Cracker, Cryptosystem, Lattice
URL http://www.sciencedirect.com/science/article/pii/S0747717110001732
JournalJournal of Symbolic Computation
Pages534 - 549
NoteGroebner Bases and Applications
Translation No
Refereed No