Report

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] • GapCVPn/logn 2 NP∩coAM [GoldreichGoldwasser98] • GapCVPn 2 NP∩coNP [AharonovRegev04] 1 nc/loglogn NP-hard n NP∩coAM NP∩coNP n NP∩coNP 2n loglogn/logn P What’s ahead? 1. GapCVPn/logn 2 NP∩coAM [GoldreichGoldwasser98] 2. GapCVPn 2 NP∩coNP [AharonovRegev04] 8 What’s ahead? 1. GapCVPn/logn 2 2. GapCVPn 2 coAM [GoldreichGoldwasser98] coNP [AharonovRegev04] 9 Chapter I GapCVPn 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 coin was heads of tails (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 GapCVPn 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 yL 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 yL 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 zL* z 2 27 f as an expectation f ( x) wL* ˆf ( w)e 2i x , w Ew fˆ [e 2i 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