Lattice polly cracker cryptosystems (Q633081)

The paper discusses the possibilities to build cryptosystems based on Gröbner bases. While Gröbner bases have revealed fruitful as a cryptoanalytic tool all attempts of using them to build cryptosystems (Polly Cracker) have failed, see \textit{F. Levy-dit-Vehel} et al. [Sala, Massimiliano (ed.) et al., Gröbner bases, coding, and cryptography. Berlin: Springer. 285--305 (2009; Zbl 1177.94159)]. The only possibilities to build a successful cryptosystem seems to be ideals generated by binomials (lattice ideals), possibility first explored by \textit{M. Caboara, F. Caruso} and \textit{C. Traverso} [in: J. Sendra and L. Gonzalez-Vega (Eds), ISSAC. ACM, 315--324 (2008; Zbl 1237.94053)]. Here the authors continue that work building a cryptosystem based on Gröbner bases of lattices (Lattice Polly Cracker, LPC), whose security relies not on the difficulty of computing a Gröbner basis but on a change of variables that transforms the private lattice into the public lattice. After reviewing the existing attacks to Polly Cracker cryptosystems and some properties of binomial ideals and lattices the paper proposes a basic version of LPC and, after showing that it is insecure, gives (Section 9) the generalized LPC version. The rest of the paper analyzes the security of the proposal and shows experimental results of three implementations (in \texttt{CoCoA}, Lisp and C++).