After the seminal work of Ajtai and Dwork and the first lattice based cryptosystem from Goldreich, Goldwasser and Halevi, many cryptosystems based on lattice theory have been proposed. These systems use the Shortest Vector Problem (SVP) or the Closest Vector Problem (CVP) as their underlying hard problem to construct the trapdoor function.

Recently a new public key cryptosystem, Lattice Polly Cracker (LPC), has been defined. LPC is a lattice encryption scheme using lattice Groebner bases and the connection between binomial ideals and lattices.

In this talk we will present a new signature scheme whose security is related to standard lattice problem, mainly the approximate SVP and CVP.

We recall briefly the general setting of LPC and we investigate the use of Normal Form function defined by Groebner basis to solve the lattice approximate CVP. This allows to approach the formal security analysis of LPC.

We show how to define instances of LPC suitable for a signature protocol, and discuss how an analysis of an instances of the private key may confirm that some of the attack not only will be hard, but in case of success the heuristic of some of them will fail.