Block Lattice Polly Cracker: design, . . .

Lattice Polly Cracker, is a public key cryptosystem that uses Gröbner bases of lattices for the preparation of the public key and normal form for decryption. In a companion paper to this one we survey the family of Polly Cracker cryptosystems, with their basic flaw that allows a “differential” attack, from which only binomial ideals are immune; we then develop the basic theory of Lattice Polly Cracker, with all the tools for efficient encryption and decryption. In this paper, after a survey of the results of the previous one, we develop all the issues connected to the security of the cryptosystem. We show that security considerations force the adoption of a very tight form of block lattice, describe the possible attacks to simplified forms of the cryptosystem, and show that the known attacks to the full cryptosystem would require the solution of a hard optimization problem. We report on an implementation, and show that the cryptosystem might be reasonably secure and efficient