# Cryptographic functions from worst-case complexity assumptions

**Authors**
Daniele Micciancio.

In **The LLL Algorithm: Survey and Applications**, pp. 427-452, Springer, December 2009.

[BibTex]
[Postscript]
[PDF]
[DOI:10.1007/978-3-642-02295-1_13]

**Abstract:**
Lattice problems have been suggested as a potential source of
computational hardness to be used in the construction of cryptographic
functions that are provably hard to break.
A remarkable feature of lattice-based cryptographic functions is that
they can be proved secure (that is, hard to break on the average)
based on the assumption that the underlying lattice problems are
computationally hard in the *worst-case*.
In this paper we give a survey of the constructions and proof
techniques used in this area, explain the importance of basing
cryptographic functions on the *worst-case* complexity of lattice
problems, and discuss how this affects the traditional approach to
cryptanalysis based on random challenges.

### Notes

Preliminary version in
Proceedings of the LLL+25
conference in honor of the 25th anniversary of LLL.
Caen, France (June 2007).