**Authors:** Daniele Micciancio

Cryptography and Lattices Conference - CaLC 2001. March 29-30, 2001, Providence, Rhode Island. Lecture Notes in Computer Science 2146. Springer-Verlag, pp. 126-145

**Abstract:** We describe a simple technique that can be used
to substantially reduce the key and ciphertext size of various lattice based
cryptosystems and trapdoor functions of the kind proposed by Goldreich,
Goldwasser and Halevi (GGH). The improvement is significant both from the
theoretical and practical point of view, reducing the size of both key and
ciphertext by a factor $n$ equal to the dimension of the lattice (i.e.,
several hundreds for typical values of the security parameter.) The
efficiency improvement is obtained without decreasing the security of the
functions: we formally prove that the new functions are at least as secure as
the original ones, and possibly even better as the adversary gets less
information in a strong information theoretical sense. The increased
efficiency of the new cryptosystems allows the use of bigger values for the
security parameter, making the functions secure against the best
cryptanalytic attacks, while keeping the size of the key even below the
smallest key size for which lattice cryptosystems were ever conjectured to be
hard to break.