On Lattices, Learning with Errors,Random Linear Co

OnLattices,LearningwithErrors,RandomLinearCodes,andCryptographyOdedRegev¤May2,2009AbstractOurmainresultisareductionfromworst-caselatticeproblemssuchasGAPSVPandSIVPtoacertainlearningproblem.Thislearningproblemisanaturalextensionofthe‘learningfromparitywitherror’problemtohighermoduli.Itcanalsobeviewedastheproblemofdecodingfromarandomlinearcode.This,webelieve,givesastrongindicationthattheseproblemsarehard.Ourreduction,however,isquantum.Hence,anefficientsolutiontothelearningproblemimpliesaquantumalgorithmforGAPSVPandSIVP.Amainopenquestioniswhetherthisreductioncanbemadeclassical(i.e.,non-quantum).Wealsopresenta(classical)public-keycryptosystemwhosesecurityisbasedonthehardnessofthelearningproblem.Bythemainresult,itssecurityisalsobasedontheworst-casequantumhardnessofGAPSVPandSIVP.Thenewcryptosystemismuchmoreefficientthanpreviouslattice-basedcryp-tosystems:thepublickeyisofsize~O(n2)andencryptingamessageincreasesitssizebyafactorof~O(n)(inpreviouscryptosystemsthesevaluesare~O(n4)and~O(n2),respectively).Infact,undertheassumptionthatallpartiessharearandombitstringoflength~O(n2),thesizeofthepublickeycanbereducedto~O(n).1IntroductionMaintheorem.Foranintegern¸1andarealnumber¸0,considerthe‘learningfromparitywitherror’problem,definedasfollows:thegoalistofindanunknowns2Zn2givenalistof‘equationswitherrors’hs;a1i¼b1(mod2)hs;a2i¼b2(mod2)...wheretheai’sarechosenindependentlyfromtheuniformdistributiononZn2,hs;aii=Pjsj(ai)jistheinnerproductmodulo2ofsandai,andeachequationiscorrectindependentlywithprobability1¡.Moreprecisely,theinputtotheproblemconsistsofpairs(ai;bi)whereeachaiischosenindependentlyand¤SchoolofComputerScience,TelAvivUniversity,TelAviv69978,Israel.SupportedbyanAlonFellowship,bytheBinationalScienceFoundation,bytheIsraelScienceFoundation,bytheArmyResearchOfficegrantDAAD19-03-1-0082,bytheEuropeanCommissionundertheIntegratedProjectQAPfundedbytheISTdirectorateasContractNumber015848,andbyaEuropeanResearchCouncil(ERC)StartingGrant.1uniformlyfromZn2andeachbiisindependentlychosentobeequaltohs;aiiwithprobability1¡.Thegoalistofinds.Noticethatthecase=0canbesolvedefficientlyby,say,Gaussianelimination.ThisrequiresO(n)equationsandpoly(n)time.Theproblemseemstobecomesignificantlyharderwhenwetakeanypositive0.Forexample,letusconsideragaintheGaussianeliminationprocessandassumethatweareinterestedinrecoveringonlythefirstbitofs.UsingGaussianelimination,wecanfindasetSofO(n)equationssuchthatPSaiis(1;0;:::;0).Summingthecorrespondingvaluesbigivesusaguessforthefirstbitofs.However,astandardcalculationshowsthatthisguessiscorrectwithprobability12+2¡£(n).Hence,inordertoobtainthefirstbitwithgoodconfidence,wehavetorepeatthewholeprocedure2£(n)times.Thisyieldsanalgorithmthatuses2O(n)equationsand2O(n)time.Infact,itcanbeshownthatgivenonlyO(n)equations,thes02Zn2thatmaximizesthenumberofsatisfiedequationsiswithhighprobabilitys.ThisyieldsasimplemaximumlikelihoodalgorithmthatrequiresonlyO(n)equationsandrunsintime2O(n).Blum,Kalai,andWasserman[11]providedthefirstsubexponentialalgorithmforthisproblem.Theiralgorithmrequiresonly2O(n=logn)equations/timeandiscurrentlythebestknownalgorithmfortheproblem.ItisbasedonacleverideathatallowstofindasmallsetSofequations(say,O(pn))among2O(n=logn)equations,suchthatPSaiis,say,(1;0;:::;0).Thisgivesusaguessforthefirstbitofsthatiscorrectwithprobability12+2¡£(pn).Wecanobtainthecorrectvaluewithhighprobabilitybyrepeatingthewholeprocedureonly2O(pn)times.Theirideawaslatershowntohaveotherimportantapplications,suchasthefirst2O(n)-timealgorithmforsolvingtheshortestvectorproblem[23,5].Animportantopenquestionistoexplaintheapparentdifficultyinfindingefficientalgorithmsforthislearningproblem.Ourmaintheoremexplainsthisdifficultyforanaturalextensionofthisproblemtohighermoduli,definednext.Letp=p(n)·poly(n)besomeprimeintegerandconsideralistof‘equationswitherror’hs;a1i¼Âb1(modp)hs;a2i¼Âb2(modp)...wherethistimes2Znp,aiarechosenindependentlyanduniformlyfromZnp,andbi2Zp.TheerrorintheequationsisnowspecifiedbyaprobabilitydistributionÂ:Zp!R+onZp.Namely,foreachequationi,bi=hs;aii+eiwhereeachei2ZpischosenindependentlyaccordingtoÂ.WedenotetheproblemofrecoveringsfromsuchequationsbyLWEp;Â(learningwitherror).Forexample,thelearningfromparityproblemwitherroristhespecialcasewherep=2,Â(0)=1¡,andÂ(1)=.UnderareasonableassumptiononÂ(namely,thatÂ(0)1=p+1=poly(n)),themaximumlikelihoodalgorithmdescribedabovesolvesLWEp;Âforp·poly(n)usingpoly(n)equationsand2O(nlogn)time.Underasimilarassumption,analgorithmresemblingtheonebyBlumetal.[11]requiresonly2O(n)equations/time.ThisisthebestknownalgorithmfortheLWEproblem.OurmaintheoremshowsthatforcertainchoicesofpandÂ,asolutiontoLWEp;Âimpliesaquantumsolutiontoworst-caselatticeproblems.Theorem1.1(Informal)Letn;pbeintegersand®2(0;1)besuchthat®p2pn.IfthereexistsanefficientalgorithmthatsolvesLWEp;¹ª®thenthereexistsanefficientquantumalgorithmthatapproximatesthedecisionversionoftheshortestvectorproblem(GAPSVP)andtheshortestindependentvectorsproblem(SIVP)towithin~O(n=®)intheworstcase.2Theexactdefinitionof¹ª®willbegivenlater.Fornow,itisenoughtoknowthatitisadistribut