### Slides (.ppt)

```The Complexity of
Lattice Problems
Oded Regev, Tel Aviv University
(for more details, see LLL+25 survey)
Amsterdam, May 2010
1
Lattice
• For vectors v1,…,vn in Rn we define the
lattice generated by them as
L={a1v1+…+anvn | ai integers}
2v1 v1+v2
• We call v1,…,vn a basis of L
v1
v2
2v2
2v2-v1
2v2-2v1
0
Lattices from a Computational Complexity
Point of View
• Lattice problems are among the richest problems
in complexity theory, exhibiting a wide range of
behaviors:
– Some problems are in P (as shown by LLL)
– Some problems are NP-hard
– Some problems are not known to be in P, but believed
not to be NP-hard
• As a rule of thumb, ‘algebraic’ problems are easy;
‘geometric’ problems are hard
3
Shortest Vector Problem (SVP)
v2
v1
0
• GapSVP: Given a lattice, decide if the length of the
shortest vector is:
– YES: less than 1
– NO: more than 
4
Closest Vector Problem (CVP)
v
v2
v1
0
• GapCVP: Given a lattice and a point v, decide if the distance of v
from the lattice is:
– YES: less than 1
– NO: more than 
• GapSVP is not harder than GapCVP [GoldreichMicciancioSafraSeifert99]
• Both problems are clearly in NP (for any )
5
Known Results
• Polytime algorithms for gap 2n loglogn/logn
[LLL82,Schnorr87,AjtaiKumarSivakumar02]
• Hardness is known for:
– GapCVP: nc/loglogn [vanEmdeBoas81…,DinurKindlerRazSafra03]
– GapSVP: 1 in l1 [vanEmdeBoas81] 1 [Ajtai96]
2 [Micciancio98] 2^(log½-εn) [Khot04]
nc/loglogn [HavivR07]
1
nc/loglogn
NP-hard
?n
Cryptography
[Ajtai96,AjtaiDwork97…]
2n loglogn/logn
P
Known Results
Limits on Inapproximability
• GapCVPn 2 NP∩coNP [LagariasLenstraSchnorr90,
Banaszczyk93]
• GapCVPn/logn 2 NP∩coAM [GoldreichGoldwasser98]
• GapCVPn 2 NP∩coNP [AharonovRegev04]
1
nc/loglogn
NP-hard
n
NP∩coAM
NP∩coNP
n
NP∩coNP
2n loglogn/logn
P
1. GapCVPn/logn 2 NP∩coAM [GoldreichGoldwasser98]
2. GapCVPn 2 NP∩coNP [AharonovRegev04]
8
1. GapCVPn/logn 2
2. GapCVPn 2
coAM [GoldreichGoldwasser98]
coNP [AharonovRegev04]
9
Chapter I
GapCVPn in coAM
[GoldreichGoldwasser98]
10
Our Goal
Given:
- Lattice L (specified by a basis)
- Point v
We want to:
Be convinced that v is far from L by interacting
with an (all powerful) prover (using a constant
number of rounds)
11
The Idea
12
Basic High-dimensional Geometry
• How big is the intersection of two balls of radius 1
in n dimensions whose centers are at distance 
apart?
– When 2, balls disjoint
– When =0, balls exactly overlap
– When =0.1, intersection is exponentially small
– When =1/n, intersection is constant fraction
13
The Protocol
•
Flip a fair coin
– If heads, choose a random point in L+B
– If tails, choose a random point in L+B+v
•
•
Send the resulting point to the prover
The prover is supposed to tell whether the
(Can be implemented efficiently)
14
Demonstration of Protocol
15
Demonstration of Protocol
16
Analysis
• If dist(v,L)>2 then prover can always answer
correctly
• If dist(v,L)<1/n then with some constant
probability, the prover has no way to tell what
the coin outcome was
– Hence we catch the prover cheating with some
constant probability
• This completes the proof
17
Chapter II
GapCVPn in coNP
[AharonovR04]
18
Our Goal
Given:
- Lattice L (specified by a basis)
- Point v
We want:
A witness for the fact that v is far from L
19
Overview
Step 1: Define f
Its value depends on the distance from L:
– Almost zero if distance > n
– More than zero if distance < log n
Step 2: Encode f
Show that the function f has a short description
Step 3: Verifier
Construct the NP verifier
20
Step 1:
Define f
21
The function f
Consider the Gaussian:
Periodize over L:
 ( x)  e
g ( x)   ( L  x)   e
Normalize by g(0):
f ( x) 
 x
 x  y
yL
g ( x)
g (0)
22
2
2
The function f (pictorially)
23
f distinguishes between far and close
vectors
(a) d(x,L)≥n
(b) d(x,L)≤logn
 f(x)≤2-Ω(n)
 f(x)>n-5
Proof: (a) [Banaszczyk93]
(b) Not too difficult
24
Step 2:
Encode f
25
The function f (again)
g ( x)   e
 x  y
2
yL
f ( x) 
g ( x)
g ( 0)
Let’s consider its Fourier transform !
26
f̂
is a probability distribution
Claim: f̂ : L*R+ is a probability
distribution on L*
L*  w |  w, x  Z
g is a convolution of a Gaussian and δL
Proof:
gˆ ( w)  e
x  L
 x
fˆ ( w) 
2
e
 ˆL  
 0
gˆ ( w )
g (0)
 w

e
2
w L*
o.w.
 w 2
e
zL*
 z 2
27
f as an expectation
f ( x) 

wL*
ˆf ( w)e 2i  x , w
 Ew fˆ [e
2i  x , w
]
In fact, it is an expectation of
a real variable between -1 and 1:
f ( x)  Ew fˆ [cos(2  x, w )]
28
Encoding f
f ( x)  Ew fˆ [cos(2  x, w )]
Pick W=(w1,w2,…,wN) with N=poly(n)
according to the f̂ distribution on L*
fW ( x ) 
N
1
N
 cos(2  x, w  )
j 1
j
f ( x )  fW ( x )
(Chernoff)
This is true even pointwise!
29
The Approximating Function
fW ( x ) 
N
1
N
 cos(2  x, w  )
j 1
j
(with N=1000 dual vectors)
30
Interlude: CVPP
GapCVPP
Solve GapCVP on a preprocessed lattice (allowed infinite
computational power, but before seeing v)
(ideas led to [MicciancioVoulgaris10]’s recent deterministic 2n
algorithm for lattice problems)
Algorithm for GapCVPP:
Prepare the function fW in advance;
When given v, calculate fW(v).
 Algorithm for GapCVPP(n/logn) (best known!)
31
This concludes Step 2: Encode f
The encoding is a list W of vectors in L*
fW(x) ≈ f(x)
32
Step 3:
NP Verifier
33
The Verifier (First Attempt)
Given input L,v, and witness W, accept iff
1. fW (v) < n-10, and
2. fW(x) > n-5 for all x within distance logn from L
• This verifier is correct
• But: how to check (2) efficiently?
- First check that fW is periodic over L (true if W in L*)
- Then check that >n-5 around origin
• We don’t know how to do this for distance logn
• Instead, we do this for distance 0.01
34
The Verifier (Second Attempt)
Given input L,v, and witness W, accept iff
1. fW (v) < n-10, and
2. w1,…,wN  L*, and
2

fW ( x )
3.
n
x   , u ,
 100
2
 xu
2 implies that fW is periodic on L:
x   n , y  L, fW ( x  y ) 

N
1
N
N
1
N
 cos(2  x  y, w  )
j
j 1
 cos(2  x, w   2  y, w  )  f
j 1
j
j
W
(x)
35
The Verifier (Second Attempt)
Given input L,v, and witness W, accept iff
1. fW (v) < n-10, and
2. w1,…,wN  L*, and
2
 fW ( x )
3.
n
x   , u ,
 100
2
 xu
1.2
3 implies that fW is at least 0.8 within
distance 0.01 of the origin:
1
fW (0)  1
fW
(0)  0
xu
fW(x)
0.8
0.6
0.4
0.2
0
-0.2
-.01
0
.01
36
The Final Verifier
Given input L,v, and witness W, accept iff
1. fW (v) < n-10, and
2. w1,…,wN  L*, and
   
 
   



3.
||WWT||<N where W    w1  w2 ....... wN  
   
 
 
   
3 checks that in any direction the w’s are not too long:
N
WW T  max u 1 uWW T u T  max u 1  u , w j  2
j 1
37
The Final Verifier
Given input L,v, and witness W, accept iff
1. fW (v) < n-10, and
2. w1,…,wN  L*, and
   
 
   



3.
||WWT||<N where W    w1  w2 ....... wN  
   
 
 
   
 2 fW ( x)  4 2

2
 xu
N
 2 fW ( x) 4 2

2
 xu
N
N
  w , u
j 1
j
2
cos(2  w j , x )
2
2
4

4

2
T T
T

w
,
u


uWW
u

WW
 100

j
N
N
j 1
N
38
Conclusion and Open Questions
• Lattice problems with approximation factors
>n are unlikely to be NP-hard
– These are the problems used for crypto
– Can we say anything about their hardness?
• Perhaps relate to hardness of other problems, say
factoring?
• Extremely important question for crypto
• Can the containment in NP∩coNP be
improved to (n/logn) or even below?
41
Thanks!
42
```