Cryptography Reference
In-Depth Information
of work where interesting improvements and variants are regularly being developed
and much progress is expected in the coming years.
8.9.2 Lattice-Based Cryptography
Aswe have just mentioned, Gentry's fully homomorphic encryption scheme is lattice-
based, as are some other encryption schemes that also have interesting properties.
Although the study of these schemes is beyond the scope of this topic, we make
a brief reference to some of them for the interested reader. Lattice-based cryptog-
raphy relies on the presumed hardness of lattice problems such as, for example,
SVP ('Shortest Vector Problem') and its variants (see [102, Chap. 6] for a discussion
of these problems and their application to cryptography). One of the reasons why
lattice-based cryptography is interesting is because these problems are believed to be
hard even for quantum computers and, in contrast with what happens, for example,
with the integer factorization problem and the discrete logarithm problem, there are
currently no known quantum algorithms for solving lattice problems that perform
significantly better than the best classical algorithms.
Another interesting aspect of lattice-based cryptography is that some of its
schemes enjoy very strong security reductions based on worst-case hardness instead
of the average-case hardness of almost all non-lattice schemes. This means that
breaking the scheme with non-negligible probability is at least as hard as solv-
ing some lattice problem in the worst case. This is a clear advantage over, say, a
factorization-based scheme, where breaking the scheme would imply the ability to
factor integers chosen according to a certain distribution but not all integers. An
interesting scheme of this type is the Ajtai-Dwork public-key encryption scheme [4]
which has the practical disadvantages of requiring keys of very large size and being
inefficient; we refer also to [141] and its references for more details on this scheme
and on lattice-based cryptography in general.
Yet another advantage of lattice-based cryptography is that, in addition to schemes
such as Ajtai-Dwork, which are secure in a very strong sense but inefficient, it also
includes schemes that lack a formal security proof but are extremely efficient; the
best-known of them is probably the NTRU encryption scheme of Hoffstein, Pipher
and Silverman. Although without the guarantee of a formal proof, schemes like this
are regarded as good candidates to be secure even if quantum computers are built.
We refer to [102] for a detailed study of the NTRU scheme.
