Carl Bosley

Internet path-quality monitoring in the presence of adversaries

Daniele Micciancio (from LLL+25, Caen, France 2007).

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.