In this talk we investigate three different topics: Groebner bases,
integer lattices and cryptography, in their mutual interrelations.

Groebner bases and cryptography: polynomial system solving through
Groebner basis is used for cryptoanalysis, but the problem is NP-hard,
and it is tempting to use it to build public key cryptosystems;
however, the paper of Boo Barkee, Deh Cac Can, Julia Ecks, Theo
Moriarty, and R.~F. Ree, "Why you cannot even hope to use Groebner
Bases in Public Key cryptography: an open letter to a scientist who
failed and a challenge to those who have not yet failed", (JSC,
18(6):497--501, 1994) explains why this is doomed to fail.  A recent
survey has shown that the assertion is still valid, with one possible
exception that will be shown later. These cryptosystems are currently
named "Polly Cracker".

Lattices and cryptography: integer lattices are used to attack
cryptosystems via LLL lattice reduction; not only lattice-bases
cryptosystems, but also others, for example RSA.

Lattice cryptosystems can be attacked via lattice reduction; the first
victim has been the Merkle-Hellman cryptosystem, many more followed,
and it is tempting to paraphrase Barkee's assertion for
lattices. Currently, the only surviving lattice cryptosystem (NTRU) is
not a lattice cryptosystem at all: it is a polynomial algebra
cryptosystem that allows a lattice description.

Groebner bases and lattices: one can define a binomial ideal
associated to a lattice (a lattice ideal), and conversely. Such ideals
are widely studied, and have a large range of application: not only in
algebraic geometry (toric varieties), but also in integer programming,
statistics, biology, etc. Algorithms to deal with them need special
implementations, not only because of the special structure of the
data, but also because of the special tuning needed for the Buchberger
algorithm. In particular, both F4 and F5 are hopeless with such
ideals. An efficient, specialized package, with GPL licence exists
(http://www.4ti2.de/).

All together now: binomial ideals escape the cryptanalisis that
cracked all the Pollies. We have hence built a public key cryptosystem
using lattice ideals, and called it Lattice Polly Cracker (LPC). It is
similar to the Goldreich-Goldwasser-Halevi cryptosystem, (GGH), but
much more efficient and (we hope) secure.

We will discuss some of the issues that have led to the current
version, that seems to be reasonably secure for a range of parameters
that can make it useful. In particular, we show the pitfalls in which
we fell in previous versions, how we escaped them, and how cracking
the LPC private key of the current version implies solving several
optimization problems that are NP-hard