On Lattices, Learning with Errors, Random Linear Codes ...

1 On Lattices, Learning with Errors, Random Linear Codes , and CryptographyOded Regev May 2, 2009 AbstractOur main result is a reduction from worst-case lattice problems such asGAPSVPandSIVPto acertain Learning problem. This Learning problem is a natural extension of the Learning from parity witherror problem to higher moduli. It can also be viewed as the problem of decoding from a Random linearcode. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, isquantum.

2 Hence, an efficient solution to the Learning problem implies aquantumalgorithm forGAPSVPandSIVP. A main open question is whether this reduction can be made classical ( , non-quantum).We also present a (classical) public-key cryptosystem whose security is based on the hardness of thelearning problem. By the main result, its security is also based on the worst-case quantum hardness ofGAPSVPandSIVP. The new cryptosystem is much more efficient than previous lattice-based cryp-tosystems: the public key is of size O(n2)and encrypting a message increases its size by a factor of O(n)(in previous cryptosystems these values are O(n4)and O(n2), respectively).

3 In fact, under theassumption that all parties share a Random bit string of length O(n2), the size of the public key can bereduced to O(n).1 IntroductionMain an integern 1and a real number 0, consider the Learning from parity witherror problem, defined as follows: the goal is to find an unknowns Zn2given a list of equations witherrors s,a1 b1(mod 2) s,a2 b2(mod 2)..where theai s are chosen independently from the uniform distribution onZn2, s,ai = jsj(ai)jis theinner product modulo2ofsandai, and each equation is correct independently with probability1.

4 More precisely, the input to the problem consists of pairs(ai, bi)where eachaiis chosen independently and School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. Supported by an Alon Fellowship, by the BinationalScience Foundation, by the Israel Science Foundation, by the Army Research Office grant DAAD19-03-1-0082, by the EuropeanCommission under the Integrated Project QAP funded by the IST directorate as Contract Number 015848, and by a EuropeanResearch Council (ERC) Starting fromZn2and eachbiis independently chosen to be equal to s,ai with probability1.

5 Thegoal is to finds. Notice that the case = 0can be solved efficiently by, say, Gaussian elimination. ThisrequiresO(n)equations andpoly(n) problem seems to become significantly harder when we take any positive >0. For example, let usconsider again the Gaussian elimination process and assume that we are interested in recovering only the firstbit ofs. Using Gaussian elimination, we can find a setSofO(n)equations such that Saiis(1,0, .. ,0).Summing the corresponding valuesbigives us a guess for the first bit ofs.

6 However, a standard calculationshows that this guess is correct with probability12+ 2 (n). Hence, in order to obtain the first bit withgood confidence, we have to repeat the whole procedure2 (n)times. This yields an algorithm that uses2O(n)equations and2O(n)time. In fact, it can be shown that given onlyO(n)equations, thes Zn2thatmaximizes the number of satisfied equations is with high probabilitys. This yields a simple maximumlikelihood algorithm that requires onlyO(n)equations and runs in time2O(n).

7 Blum, Kalai, and Wasserman [11] provided the first subexponential algorithm for this problem. Theiralgorithm requires only2O(n/logn)equations/time and is currently the best known algorithm for the is based on a clever idea that allows to find a small setSof equations (say,O( n)) among2O(n/logn)equations, such that Saiis, say,(1,0, .. ,0). This gives us a guess for the first bit ofsthat is correctwith probability12+ 2 ( n). We can obtain the correct value with high probability by repeating the wholeprocedure only2O( n)times.

8 Their idea was later shown to have other important applications, such as thefirst2O(n)-time algorithm for solving the shortest vector problem [23,5].An important open question is to explain the apparent difficulty in finding efficient algorithms for thislearning problem. Our main theorem explains this difficulty for a natural extension of this problem to highermoduli, defined (n) poly(n)be some prime integer and consider a list of equations with error s,a1 b1(modp) s,a2 b2(modp)..where this times Znp,aiare chosen independently and uniformly fromZnp, andbi Zp.

9 The errorin the equations is now specified by a probability distribution :Zp R+onZp. Namely, for eachequationi,bi= s,ai +eiwhere eachei Zpis chosen independently according to . We denote theproblem of recoveringsfrom such equations byLWEp, ( Learning with error). For example, the learningfrom parity problem with error is the special case wherep= 2, (0) = 1 , and (1) = . Under areasonable assumption on (namely, that (0)>1/p+ 1/poly(n)), the maximum likelihood algorithmdescribed above solvesLWEp, forp poly(n)usingpoly(n)equations and2O(nlogn)time.

10 Under asimilar assumption, an algorithm resembling the one by Blum et al. [11] requires only2O(n) is the best known algorithm for main theorem shows that for certain choices ofpand , a solution toLWEp, implies a quantumsolution to worst-case lattice (Informal)Letn, pbe integers and (0,1)be such that p >2 n. If there exists anefficient algorithm that solvesLWEp, then there exists an efficient quantum algorithm that approximatesthe decision version of the shortest vector problem (GAPSVP) and the shortest independent vectors problem(SIVP) to within O(n/ )in the worst exact definition of will be given later.