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. 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).

2 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 .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.

3 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. 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).

4 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. 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).

5 Where this times Znp,aiare chosen independently and uniformly fromZnp, andbi Zp. 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. 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.

6 For now, it is enough to know that it is a distribution onZpthat has the shape of a discrete Gaussian centered around 0 with standard deviation p, as in Figure1. Also,the probability of0( , no error) is roughly1/( p). A possible setting for the parameters isp=O(n2)and = 1/( nlog2n)(in fact, these are the parameters that we use in our cryptographic application). 1 1 Probability 1 1 ProbabilityFigure 1: forp= 127with = (left) and = (right). The elements ofZpare arranged on two of the main computational problems on lattices. InGAPSVP, for instance,the input is a lattice, and the goal is to approximate the length of the shortest nonzero lattice vector. Thebest known polynomial time algorithms for them yield only mildly subexponential approximation factors[24,38,5]. It is conjectured that there is no classical ( , non-quantum) polynomial time algorithm thatapproximates them to within any polynomial factor. Lattice-based constructions of one-way functions, suchas the one by Ajtai [2], are based on this might even conjecture that there is noquantumpolynomial time algorithm that approximatesGAPSVP(orSIVP) to within any polynomial factor.

7 One can then interpret the main theorem as say-ing that based on this conjecture, theLWEproblem is hard. The only evidence supporting this conjecture isthat there are no known quantum algorithms for lattice problems that outperform classical algorithms, eventhough this is probably one of the most important open questions in the field of quantum fact, one could also interpret our main theorem as a way to disprove this conjecture: if one findsan efficient algorithm forLWE, then one also obtains a quantum algorithm for approximating worst-caselattice problems. Such a result would be of tremendous importance on its own. Finally, we note that it ispossible that our main theorem will one day be made classical. This would make all our results stronger andthe above discussion can be equivalently presented as the problem of decoding Random Linear Codes . Morespecifically, letm= poly(n)be arbitrary and lets Znpbe some vector. Then, consider the followingproblem: given a Random matrixQ Zm npand the vectort=Qs+e Zmpwhere each coordinateof the error vectore Zmpis chosen independently from , recovers.

8 The Hamming weight ofeisroughlym(1 1/( p))(since a value chosen from is0with probability roughly1/( p)). Hence, theHamming distance oftfromQsis roughlym(1 1/( p)). Moreover, it can be seen that for large enoughm, for any other words , the Hamming distance oftfromQs is roughlym(1 1/p). Hence, we obtainthat approximating the nearest codeword problem to within factors smaller than(1 1/p)/(1 1/( p))on Random Codes is as hard as quantumly approximating worst-case lattice problems. This gives a partial1If forced to make a guess, the author would say that the conjecture is to the important open question of understanding the hardness of decoding from Random Linear turns out that certain problems, which are seemingly easier than theLWEproblem, are in fact equiv-alent to theLWEproblem. We establish these equivalences in Section4using elementary reductions. Forexample, being able to distinguish a set of equations as above from a set of equations in which thebi s arechosen uniformly fromZpis equivalent to solvingLWE.

9 Moreover, it is enough to correctly distinguishthese two distributions for some non-negligible fraction of alls. The latter formulation is the one we use inour cryptographic Section5we present a public key cryptosystem and prove that it is secure based onthe hardness of theLWEproblem. We use the standard security notion of semantic, or IND-CPA, secu-rity (see, , [20, Chapter 10]). The cryptosystem and its security proof are entirely classical. In fact,the cryptosystem itself is quite simple; the reader is encouraged to glimpse at the beginning of , the idea is to provide a list of equations as above as the public key; encryption is performed bysumming some of the equations (forming another equation with error) and modifying the right hand sidedepending on the message to be transmitted. Security follows from the fact that a list of equations with erroris computationally indistinguishable from a list of equations in which thebi s are chosen using our main theorem, we obtain that the security of the system is based also on the worst-casequantum hardness of approximatingSIVPandGAPSVPto within O( ).

10 In other words, breakingour cryptosystem implies an efficient quantum algorithm for approximatingSIVPandGAPSVPto within O( ). Previous cryptosystems, such as the Ajtai-Dwork cryptosystem [4] and the one by Regev [36], arebased on the worst-case (classical) hardness of the unique-SVPproblem, which can be related toGAPSVP(but notSIVP) through the recent result of Lyubashevsky and Micciancio [26].Another important feature of our cryptosystem is its improved efficiency. In previous cryptosystems,the public key size is O(n4)and the encryption increases the size of messages by a factor of O(n2). In ourcryptosystem, the public key size is only O(n2)and encryption increases the size of messages by a factor ofonly O(n). This possibly makes our cryptosystem practical. Moreover, using an idea of Ajtai [3], we canreduce the size of the public key to O(n). This requires all users of the cryptosystem to share some (trusted) Random bit string of length O(n2).