Lattice polly cracker cryptosystems
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++).
- Gröbner bases for public key cryptography
- A survey on Polly Cracker systems
- Private key extension of Polly Cracker cryptosystems
- Topics in Cryptology – CT-RSA 2006
- An introduction to Gröbner bases
- A Zero-Dimensional Gröbner Basis for AES-128
- Polly cracker, revisited
- Computing Gröbner bases of pure binomial ideals via submodules of Z^n
- Gröbner basis cryptosystems
- A survey on Polly Cracker systems
- Advances in Cryptology - CRYPTO 2003
- Algebraic aspects of cryptography. With an appendix on hyperelliptic curves by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato
- Block ciphers: algebraic cryptanalysis and Gröbner bases
- Computing toric ideals
- Gröbner bases for public key cryptography
- Gröbner basis cryptosystems
- Hilbert functions and the Buchberger algorithm
- scientific article; zbMATH DE number 2127871 (Why is no real title available?)
- scientific article; zbMATH DE number 3989251 (Why is no real title available?)
- scientific article; zbMATH DE number 1186948 (Why is no real title available?)
- scientific article; zbMATH DE number 691465 (Why is no real title available?)
- scientific article; zbMATH DE number 1088230 (Why is no real title available?)
- scientific article; zbMATH DE number 1925556 (Why is no real title available?)
- scientific article; zbMATH DE number 1852141 (Why is no real title available?)
- scientific article; zbMATH DE number 1852142 (Why is no real title available?)
- scientific article; zbMATH DE number 1418301 (Why is no real title available?)
- On Lovász' lattice reduction and the nearest lattice point problem
- Polly Two: a new algebraic polynomial-based public-key scheme
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
- Why you cannot even hope to use Gröbner bases in public key cryptography: An open letter to a scientist who failed and a challenge to those who have not yet failed
- Polly cracker, revisited
- Weyl Gröbner basis cryptosystems
- A survey on Polly Cracker systems
- scientific article; zbMATH DE number 1925556 (Why is no real title available?)
- Gröbner bases for public key cryptography
- Why you cannot even hope to use Gröbner bases in cryptography: an eternal golden braid of failures
This page was built for publication: Lattice polly cracker cryptosystems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633081)
