Cryptography Reference
In-Depth Information
16
Lattices
The word “lattice” has two different meanings in mathematics. One meaning is related to
the theory of partial orderings on sets (for example, the lattice of subsets of a set). The other
meaning, which is the one relevant to us, is discrete subgroups of
n
.
There are several reasons for presenting lattices in this topic. First, there are hard
computational problems on lattices that have been used as a building block for public key
cryptosystems (e.g., the Goldreich-Goldwasser-Halevi (GGH) cryptosystem, the NTRU
cryptosystem, the Ajtai-Dwork cryptosystem and the LWE cryptosystem); however, we do
not present these applications in this topic. Second, lattices are used as a fundamental tool for
cryptanalysis of public key cryptosystems (e.g., lattice attacks on knapsack cryptosystems,
Coppersmith's method for finding small solutions to polynomial equations, attacks on
signatures and attacks on variants of RSA). Third, there are applications of lattices to
efficient implementation of discrete logarithm systems (such as the GLV method; see
Section
11.3.3
). Finally, lattices are used as a theoretical tool for security analysis of
cryptosystems, for example the bit security of Diffie-Hellman key exchange using the
hidden number problem (see Section
21.7
) and the security proofs for RSA-OAEP.
Some good references for lattices, applications of lattices and/or lattice reduction algo-
rithms are: Cassels [
114
], Siegel [
504
], Cohen [
127
], von zur Gathen and Gerhard [
220
],
Gr otschel, Lovasz and Schrijver [
245
], Nguyen and Stern [
414
,
415
], Micciancio and Gold-
wasser [
378
], Hoffstein, Pipher and Silverman [
261
], Lenstra's chapter in [
106
], Micciancio
and Regev's chapter in [
48
] and the proceedings of the conference LLL+25.
R
Notation used in this part
Z
Integers, rational, real numbers
b
,
v
,
w
Row vectors (usually in
,
Q
,
R
R
m
)
m
0
Zero vector in
R
m
e
i
i
th unit vector in
R
I
n
n
×
n
identity matrix
x
,
x
Inner product
x
Euclidean length (
2
norm)
·
a
a
-norm for
a
∈ N
