Lattice-based Cryptography

Short Description
based cryptography such as RSA. Such alternatives will be needed in case an …. As is often the case in lattice-based cryptography, the cryptosystems them- …

Website: www.cs.tau.ac.il | Filesize: 212kb

Content
Lattice-based Cryptography
Oded Regev?
Tel Aviv University, Israel
Abstract. We describe some of the recent progress on lattice-based
cryptography, starting from the seminal work of Ajtai, and ending with
some recent constructions of very efficient cryptographic schemes.
1 Introduction
In this survey, we describe some of the recent progress on lattice-based cryptography.
What is a lattice? It is a set of points in n-dimensional space with a
periodic structure, such as the one illustrated in Figure 1. More formally, given
n-linearly independent vectors v1, . . . , vn 2 Rn, the lattice generated by them is
the set of vectors
L(v1, . . . , vn) := ( n
Xi=1
ivi
i 2 Z).
The vectors v1, . . . , vn are known as a basis of the lattice.
Fig. 1. A lattice in R2 and two of its bases
Historically, lattices were investigated since the late 18th century by mathematicians
such as Lagrange, Gauss, and later Minkowski. More recently, lattices
have become an active topic…