Petros Mol

Lattices and Cryptography:An Overview of Recent Results with
Emphasis on RSA and NTRU Cryptosystems.

Traditionally, the study of lattices was closely connected to areas
such as theory and geometry of numbers. The invention of LLL in 1982
and the intractability of some computational problems related to
lattices led to lattice applications in various theoretical areas such
as factorization of integer polynomials, integer programming and
Public-Key Cryptography.  In PKC, lattice theory has played a crucial
role in the definition of new cryptosystems, in the study of
cryptographic primitives and in cryptanalysis.

In this survey, we present some of the most representative
applications of lattices in Cryptography with emphasis on RSA and NTRU
Cryptosystems.We present how Coppersmith's technique for finding small
solutions to polynomial equations can be used to attack certain
instances of RSA Cryptosystem. We also highlight the importance of
finding short vectors in certain lattices and their corresponding
applications in breaking NTRU instances of moderate level of
security.Finally, we review some recent advancements which give hope
that lattice based cryptography provides a possible alternative to
number-theoretic based encryption schemes.