Sterncjblaze

FullyHomomorphicEncryptionUsingIdealLatticesCraigGentryStanfordUniversityandIBMWatsoncgentry@cs.
stanford.
eduABSTRACTWeproposeafullyhomomorphicencryptionscheme–i.
e.
,aschemethatallowsonetoevaluatecircuitsoverencrypteddatawithoutbeingabletodecrypt.
Oursolutioncomesinthreesteps.
First,weprovideageneralresult–that,toconstructanencryptionschemethatpermitsevaluationofarbitrarycircuits,itsucestoconstructanencryptionschemethatcanevaluate(slightlyaugmentedversionsof)itsowndecryptioncircuit;wecallaschemethatcanevaluateits(augmented)decryptioncircuitbootstrappable.
Next,wedescribeapublickeyencryptionschemeusingideallatticesthatisalmostbootstrappable.
Lattice-basedcryptosystemstypicallyhavedecryptionalgorithmswithlowcircuitcomplexity,oftendominatedbyaninnerproductcomputationthatisinNC1.
Also,ideallatticesprovidebothadditiveandmultiplicativehomomorphisms(moduloapublic-keyidealinapolynomialringthatisrepresentedasalattice),asneededtoevaluategeneralcircuits.
Unfortunately,ourinitialschemeisnotquitebootstrap-pable–i.
e.
,thedepththattheschemecancorrectlyevalu-atecanbelogarithmicinthelatticedimension,justlikethedepthofthedecryptioncircuit,butthelatterisgreaterthantheformer.
Inthenalstep,weshowhowtomodifytheschemetoreducethedepthofthedecryptioncircuit,andtherebyobtainabootstrappableencryptionscheme,with-outreducingthedepththattheschemecanevaluate.
Ab-stractly,weaccomplishthisbyenablingtheencryptertostartthedecryptionprocess,leavinglessworkforthede-crypter,muchliketheserverleaveslessworkforthede-crypterinaserver-aidedcryptosystem.
CategoriesandSubjectDescriptors:E.
3[DataEn-cryption]:PublickeycryptosystemsGeneralTerms:Algorithms,Design,Security,Theory1.
INTRODUCTIONWeproposeasolutiontotheoldopenproblemofcon-structingafullyhomomorphicencryptionscheme.
Thisno-tion,originallycalledaprivacyhomomorphism,wasintro-Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprotorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationontherstpage.
Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecicpermissionand/orafee.
STOC'09,May31–June2,2009,Bethesda,Maryland,USA.
Copyright2009ACM978-1-60558-506-2/09/05.
.
.
$5.
00.
ducedbyRivest,AdlemanandDertouzos[54]shortlyaf-tertheinventionofRSAbyRivest,AdlemanandShamir[55].
BasicRSAisamultiplicativelyhomomorphicencryp-tionscheme–i.
e.
,givenRSApublickeypk=(N,e)andciphertexts{ψi←πeimodN},onecanecientlycomputeiψi=(iπi)emodN,aciphertextthatencryptstheproductoftheoriginalplaintexts.
Rivestetal.
[54]askedanaturalquestion:Whatcanonedowithanencryptionschemethatisfullyhomomorphic:aschemeEwithane-cientalgorithmEvaluateEthat,foranyvalidpublickeypk,anycircuitC(notjustacircuitconsistingofmultiplicationgates),andanyciphertextsψi←EncryptE(pk,πi),outputsψ←EvaluateE(pk,C,ψ1,ψt),avalidencryptionofC(π1,πt)underpkTheiranswer:onecanarbitrarilycomputeonencrypteddata–i.
e.
,onecanprocessencrypteddata(queryit,writeintoit,doanythingtoitthatcanbeecientlyexpressedasacircuit)withoutthedecryptionkey.
Asanapplication,theysuggestedpri-vatedatabanks:ausercanstoreitsdataonanuntrustedserverinencryptedform,yetstillallowtheservertopro-cess,andrespondto,theuser'sdataqueries(withresponsesmoreconcisethanthetrivialsolution:theserverjustsendsalloftheencrypteddatabacktotheusertoprocess).
Sincethen,cryptographershaveaccumulatedalistof"killer"ap-plicationsforfullyhomomorphicencryption.
However,priortothisproposal,wedidnothaveaviableconstruction.
1.
1HomomorphicEncryptionAhomomorphicpublickeyencryptionschemeEhasfouralgorithmsKeyGenE,EncryptE,DecryptE,andanadditionalalgorithmEvaluateEthattakesasinputthepublickeypk,acircuitCfromapermittedsetCEofcircuits,andatupleofciphertextsΨ=ψ1,ψt;itoutputsaciphertextψ.
Thecomputationalcomplexityofallofthesealgorithmsmustbepolynomialinsecurityparameterλand(inthecaseofEvaluateE)thesizeofC.
EiscorrectforcircuitsinCEif,foranykey-pair(sk,pk)outputbyKeyGenE(λ),anycircuitC∈CE,anyplaintextsπ1,πt,andanyciphertextsΨ=ψ1,ψtwithψi←EncryptE(pk,πi),itisthecasethat:ψ←EvaluateE(pk,C,Ψ)C(π1,πt)=DecryptE(sk,ψ)Byitself,merecorrectnessdoesnotexcludetrivialschemes.
1So,werequireciphertextsizeanddecryptiontimetobeup-1Inparticular,wecoulddeneEvaluateE(pk,C,Ψ)tojustoutput(C,Ψ)without"processing"thecircuitorciphertextsatall,andDecryptEtodecryptthecomponentciphertextsandapplyCtoresults.
perboundedbyafunctionofthesecurityparameterλ,in-dependentlyofC(orperhaps,asarelaxation,dependentonthedepthofC,butnotthesize).
Definition1(HomomorphicEncryption).
Eisho-momorphicforcircuitsinCEifEiscorrectforCEandDecryptEcanbeexpressedasacircuitDEofsizepoly(λ).
Definition2(FullyHomomorphicEncryption).
Eisfullyhomomorphicifitishomomorphicforallcircuits.
Definition3(LeveledFullyHom.
Encryption).
Afamilyofschemes{E(d):d∈Z+}isleveledfullyhomo-morphiciftheyallusethesamedecryptioncircuit,E(d)ishomomorphicforallcircuitsofdepthatmostd(thatusesomespeciedsetofgatesΓ),andthecomputationalcom-plexityofE(d)'salgorithmsispolynomialinλ,d,and(inthecaseofEvaluateE(d))thesizeofC.
Remark1.
Onemaydesire–e.
g.
,forthetwo-partycom-putationsetting–theadditionalpropertythatEncryptEandEvaluateEhavethesameoutputdistribution,orthatthereisatleastsomepost-hocrandomizationprocedurethatin-ducesthesameoutputdistribution.
WediscusssuchcircuitprivacyinSection7.
Here,wefocusonconstructingaschemethatissemanti-callysecureagainstchosenplaintextattacks(orjust"seman-ticallysecure").
Unfortunatelyaschemethathasnontriv-ialhomomorphismscannotbesemanticallysecureagainstadaptivechosenciphertextattacks(CCA2),sinceitismal-leable.
TherearerelaxednotionsofCCA2security[3,16,52],buttheydonotapplytoafullyhomomorphicscheme.
However,constructingaCCA1-securefullyhomomorphicencryptionschemeisaninterestingopenproblem.
1.
2OurResultsWeconstructafullyhomomorphicencryptionschemeus-ingideallattices.
Theresultcanroughlybebrokendownintothreesteps:ageneral"bootstrapping"result,an"initialconstruction"usingideallattices,andatechniqueto"squashthedecryptioncircuit"topermitbootstrapping.
Ourresearchbeganwiththesecondstep:aPKEschemeE1describedinSection3thatusesideallatticesandishomo-morphicforshallowcircuits.
Aciphertextψhastheformv+xwherevisintheideallatticeandxisan"error"or"oset"vectorthatencodestheplaintextπ.
Interpret-ingciphertextvectorsascoecientvectorsofelementsinapolynomialringZ[x]/f(x),weaddandmultiplyciphertextsusingringoperations–ψ←ψ1+ψ2orψ←ψ1*ψ2–andinduceadditionandmultiplicationoftheunderlyingplain-texts.
Byitself,thisschemeimprovesuponpriorwork.
ItcomparesfavorablytoBoneh-Goh-Nissim[11];itishomo-morphicforcircuitswithgreatermultiplicativedepthwhileallowingessentiallyunlimitedadditions.
ThesecurityofE1isbasedonanaturaldecisionalversionoftheclosestvectorproblemforideallatticesforidealsinaxedring.
E1ishomomorphiconlyforshallowcircuitsbecausethe"error"vectorgrowswithadditionand(especially)multi-plicationoperations;eventually,itbecomessolongthatitcausesadecryptionerror.
Itisnaturaltoask:canwe"re-fresh"aciphertextwhoseerrorvectorisalmosttoolongtoobtainanewciphertextwhoseerrorvectorisshorterOb-viously,wecouldrefreshaciphertextifwecouldcompletelydecryptit!
Thisistheideabehindbootstrapping:wedodecrypttheciphertext,buthomomorphically!
Specically,supposeEisbootstrappablewithplaintextspacePis{0,1},andthatcircuitsareboolean.
Supposewehaveaciphertextψ1thatencryptsπunderpk1,whichwewanttorefresh.
Sothatwecandecryptithomomorphically,supposewealsohavesk1,thesecretkeyforpk1,encryptedunderasecondpublickeypk2:letsk1jbetheencryptedsecretkeybits.
Considerthefollowingalgorithm.
RecryptE(pk2,DE,sk1j,ψ1).
Setψ1jR←EncryptE(pk2,ψ1j)Outputψ2←EvaluateE(pk2,DE,sk1j,ψ1j)Above,Evaluatetakesinthebitsofsk1andψ1,eachen-cryptedunderpk2.
Then,Eisusedtoevaluatethede-cryptioncircuithomomorphically.
Theoutputψ2isthusanencryptionunderpk2ofDecryptE(sk1,ψ1)=π.
2ApplyingthedecryptioncircuitDEremovestheerrorvectorassoci-atedtotherstciphertext,butEvaluateEsimultaneouslyintroducesanewerrorvector.
Intuitively,wehavemadeprogressaslongastheseconderrorvectorisshorter.
SupposeCEcontainsnotjustDEbutalsotheaugmen-tationofDEbyNAND(i.
e.
,aNANDgateconnectingtwocopiesofDE).
Then,wesayEisbootstrappable.
Theorem1(Informal).
Onecanconstructa(seman-ticallysecure)family{E(d)}ofleveledfullyhomomorphicen-cryptionschemesfromany(semanticallysecure)bootstrap-pableencryptionschemeE.
E(d)'spublickeycontainsd+1Epublickeys,basicallyoneforeachlevelofthecircuit,andanacyclicchainofencryptedsecretkeys.
Itevaluatesad-depthNAND-circuitasfollows:givenciphertextsencryptedunderpkiassociatedtowiresattheithlevelofthecircuit,itRecryptsthemsothattheybecomeencryptedunderpki1,appliestheNANDgatesatthatlevel,andrecursesfori1.
IfEsecurelyencryptskey-dependentmessages(isKDM-secure)[9,24,12]–i.
e.
,roughly,ifprovidingaciphertextthatencryptsafunctionofthesecretkeydoesnothurtsecurity–thentheEpublickeysneednotbedistinct;wecanhavea"loop,"evena"self-loop,"ofencryptedsecretkeys,andthederivedschemeisfullyhomomorphic.
SeeSection2forformaldetails.
InSection4,wedescribeaschemeE2that"tweaks"E1,analyzethecomplexityofitsdecryptioncircuit,andexplainwhyweareunabletoprovethatitisbootstrappable.
InSection5,wedescribeatransformationofE2,labeledE3,wheretheE3publickeycontainsasetofvectorswithasecretsparsesubsetwhosesumisrelatedtoE2secretkey.
Thisallowsustore-expressdecryptionasasparsesubsetvectorsumratherthanafullmatrix-vectorproduct,whichrequiresacircuitoflowerdepth,permittingbootstrapping.
Italsoentailsanadditionalassumption:roughly,thatitishardtodistinguishasetthathasasparsesubsetwithaknownsumfromasetthatisuniform.
Similarassumptionshavebeenanalyzedinconnectionwithserver-aideddecryption.
Theorem2(Informal).
E3isbootstrappableandissemanticallysecure(undertwoassumptions).
2Recryptimpliesaone-wayproxyre-encryptionscheme[10].
1.
3OtherRelatedWorkHomomorphicencryptionschemesthatarenotsemanti-callysecure,likebasicRSA,mayalsohavestrongerattacksontheirone-wayness.
BonehandLipton[13]provedthatanyalgebraicprivacyhomomorphismoveraringZncanbebrokeninsub-exponentialtimeundera(reasonable)num-bertheoreticassumption,iftheschemeisdeterministicorotherwiseoersanequalityoracle.
Seealso[35]and[18].
GoldwasserandMicali[23]proposedtherstsemanti-callysecurehomomorphicencryptionscheme(andalsoin-troducedthenotionofsemanticsecurity).
Theirschemeis"additivelyhomomorphic"overZ2;inourterminology,itssetCEofpermittedcircuitscontainscircuitswithXORgates.
OtheradditivelyhomomorphicencryptionschemeswithproofsofsemanticsecurityareBenaloh[8],Naccache-Stern[42],Okamoto-Uchiyama[46],Paillier[47],andDamgard-Jurik[19].
Someadditivelyhomomorphicencryptionschemesuselatticesorlinearcodes[22,50,27,36,37,4].
ElGamal[20]ismultiplicativelyhomomorphic.
SemanticallysecureschemesthatallowbothadditionandmultiplicationincludeBoneh-Goh-Nissim[11](quadraticfor-mulas)and"PollyCracker"byFellowsandKoblitz[21,29,30,31](arbitrarycircuitsbutwithexponentialciphertext-sizeblow-up).
Sanders,YoungandYung[56,7](SYY)usecircuit-privateadditivelyhomomorphicencryptiontocon-structacircuit-privateschemethatcanhandleNC1circuits.
IshaiandPaskin[26]dothisforbranchingprograms,whichcoversNC1circuits(byBarrington[6]),andciphertextsintheirschemearemuchshorter–proportionaltothelengthofthebranchingprogramratherthanitssize,thoughthecomputationisproportionaltothesize.
2.
BOOTSTRAPPABLEENCRYPTIONTobebootstrappable,Eneedstobeabletoevaluatenotonlyitsdecryptioncircuit,whichmerelyallowsrecryptionsofthesameplaintext,butalsoslightlyaugmentedversionsofit,sothatwecanperformnontrivialoperationsonplaintextsandmakeprogressthroughacircuit.
Definition4(AugmentedDecryptionCircuit).
LetΓbeasetofgateswithinputsandoutputinplaintextspacePincludingtheidentitygate(inputandoutputarethesame).
Forgateg∈Γ,theg-augmenteddecryptioncircuitconsistsofag-gateconnectingmultiplecopiesofDE(thenumberofcopiesequalsthenumberofinputstog),whereDEtakesasecretkeyandciphertextasinputformattedaselementsofP(λ).
Wedenotethesetofg-augmentedde-cryptioncircuits,g∈Γ,byDE(Γ).
Definition5(BootstrappableEncryption).
LetCEbeasetofcircuitswithrespecttowhichEishomomorphic.
WesaythatEisbootstrappablewithrespecttoΓifDE(Γ)CE.
Forafamilyofschemes{E(d)}derivedfromEthatwewilldenemomentarily,wehavethefollowingtheorems.
Theorem3.
LetEbebootstrappablewithrespecttoasetofgatesΓ.
Thenthefamily{E(d)}isleveledfullyhomomor-phic(forcircuitswithgatesinΓ).
Theorem4.
LetAbeanalgorithmthatbreaksthese-manticsecurityofE(d)withadvantage.
Then,thereisanalgorithmBthatbreaksthesemanticsecurityofEwithprob-abilityatleast/(d+1),forasinDenition4,andtimepoly(,d)timesthatofA.
NotethatΓisarbitraryinTheorem3.
Forexample,eachgateinΓcouldbeacircuitof(ANDs,ORs,NOTs)ofdepthmandfan-in2;forthisvalueofΓ,Theorem3impliestheschemecorrectlyevaluates"normal"circuitsofdepthd·m.
Nowwespecifytheleveledfullyhomomorphicscheme.
LetEbebootstrappablewithrespecttoasetofgatesΓ.
Foranyintegerd≥1,weuseEtoconstructaschemeE(d)=(KeyGenE(d),EncryptE(d),EvaluateE(d),DecryptE(d))thatcanhandleallcircuitsofdepthdwithgatesinΓ.
WhenwerefertothelevelofawireinC,wemeanthelevelofthegateforwhichthewireisaninput.
WeusethenotationDE(Γ,δ)torefertothesetofcircuitsthatequalaδ-depthcircuitwithgatesinΓaugmentedbyDE(copiesofDEbecomeinputstotheδ-depthcircuit).
KeyGenE(d)(λ,d).
Takesasinputasecurityparameterλandapositiveintegerd.
For=(λ)asinDenition4,itsets(ski,pki)R←KeyGenE(λ)fori∈[0,d]skijR←EncryptE(pki1,skij)fori∈[1,d],j∈[1,]whereski1,skiistherepresentationofskiaselementsofP.
Itoutputsthesecretkeysk(d)←sk0andthepub-lickeypk(d)←(pki,skij).
Forδ≤d,letE(δ)refertotheschemeusingsk(δ)←sk0andpk(δ)←(pkii∈[0,δ],skiji∈[1,δ]).
EncryptE(d)(pk(d),π).
Takesasinputapublickeypk(d)andaplaintextπ∈P.
ItoutputsaciphertextψR←EncryptE(pkd,π).
DecryptE(d)(sk(d),ψ).
Takesasinputasecretkeysk(d)andaciphertextψ(whichshouldbeanencryptionunderpk0).
ItoutputsDecryptE(sk0,ψ).
EvaluateE(δ)(pk(δ),Cδ,Ψδ).
Takesasinputapublickeypk(δ),acircuitCδofdepthatmostδwithgatesinΓ,andatupleofinputciphertextsΨδ(whereeachinputciphertextshouldbeunderpkδ).
WeassumethateachwireinCδconnectsgatesatconsecutivelevels;ifnot,addidentitygatestomakeitso.
Ifδ=0,itoutputsΨ0andterminates.
Otherwise,itdoesthefollowing:Sets(Cδ1,Ψδ1)←AugmentE(δ)(pk(δ),Cδ,Ψδ).
Sets(Cδ1,Ψδ1)←ReduceE(δ1)(pk(δ1),Cδ1,Ψδ1).
RunsEvaluateE(δ1)(pk(δ1),Cδ1,Ψδ1).
AugmentE(δ)(pk(δ),Cδ,Ψδ).
Takesasinputapublickeypk(δ),acircuitCδofdepthatmostδwithgatesinΓ,andatupleofinputciphertextsΨδ(whereeachinputciphertextshouldbeunderpkδ).
ItaugmentsCδwithDE;calltheresultingcircuitCδ1.
LetΨδ1bethetupleofciphertextsformedbyreplacingeachinputciphertextψ∈Ψδbythetupleskδj,ψj,whereψj←EncryptE(δ1)(pk(δ1),ψj)andtheψj'sformtheproperly-formattedrepresentationofψaselementsofP.
Itoutputs(Cδ1,Ψδ1).
ReduceE(δ)(pk(δ),Cδ,Ψδ).
Takesasinputapublickeypk(δ),atupleofinputciphertextsΨδ(whereeachinputciphertextshouldbeanoutputofEncryptE(δ)),andacircuitCδ∈DE(Γ,δ+1).
ItsetsCδtobethesub-circuitofCδconsistingoftherstδlevels.
ItsetsΨδtobetheinducedinputciphertextsofCδ,wheretheciphertextψ(w)δassociatedtowirewatlevelδissettoEvaluateE(pkδ,C(w)δ,Ψ(w)δ),whereC(w)δisthesub-circuitofCδwithoutputwirew,andΨ(w)δaretheinputciphertextsforC(w)δ.
Itoutputs(Cδ,Ψδ).
RegardingthecomputationalcomplexityofEvaluateE(d):Theorem5.
ForacircuitCofdepthatmostdandsizes(denedhereasthenumberofwires),thecomputationalcomplexityofapplyingEvaluateE(d)toCisdominatedbyatmosts··dapplicationsofEncryptEandatmosts·dap-plicationsofEvaluateEtocircuitsinDE(Γ),whereisasinDenition4.
Asmentionedabove,ifEisKDM-secure,wecanshortenthepublickeytoincludepkandandanencryptionofskunderpk,a"self-loop"ratherthananacyclicchainofen-cryptedsecretkeys.
3Thisschemeisfullyhomomorphic,withsecurityfollowingfromKDM-security,andcorrectnessfollowingfromcorrectnessoftheabovescheme.
3.
ANINITIALCONSTRUCTIONOurgoalnowistoconstructanencryptionschemethatisbootstrappablewithrespecttoauniversalsetofgatesΓ–e.
g.
,whereΓincludesNANDandthetrivialgate.
Here,wedescribeaninitialattempt.
InSection4,wedescribesometweakstothisconstructionandndthatthedecryp-tioncomplexityisstilltoolargetopermitbootstrappability.
WenallyachievebootstrappabilityinSection5.
3.
1TheInitialConstruction,AbstractlyWestartbydescribingourinitialattemptsimplyintermsofringsandideals;webringinideallatticeslater.
Inourini-tialschemeE,weuseaxedringRthatissetappropriatelyaccordingtoasecurityparameterλ.
WealsouseaxedbasisBIofaidealIR,andanalgorithmIdealGen(R,BI)thatoutputspublicandsecretbasesBpkJandBskJofsome(variable)idealJ,suchthatI+J=R–i.
e.
,IandJarerelativelyprime.
(Actually,BskJcanbeabasisofa(frac-tional)idealthatcontainsJ,ratherthanofJ.
)Weassumethatift∈RandBMisabasisforidealMR,thenthevaluetmodBMisuniqueandcanbecomputedeciently–i.
e.
,thecosett+Mhasaunique,eciently-computable"distinguishedrepresentative"withrespecttothebasisBM.
WeusethenotationRmodBMtodenotethesetofdistin-guishedrepresentativesofr+Moverr∈R,withrespecttotheparticularbasisBMofM.
WealsouseanalgorithmSamp(x,BI,R,BJ)thatsamplesfromthecosetx+I.
Inthescheme,EvaluatetakesasinputacircuitCwhosegatesperformoperationsmoduloBI.
Forexample,anAddBIgateinCtakestwotermsinRmodBI,andoutputsathirdterminRmodBI,whichequalsthesumofthersttwotermsmoduloI.
KeyGen(R,BI).
TakesasinputaringRandbasisBIofI.
Itsets(BskJ,BpkJ)R←IdealGen(R,BI).
TheplaintextspacePis(asubsetof)RmodBI.
ThepublickeypkincludesR,BI,BpkJ,andSamp.
ThesecretkeyskalsoincludesBskJ.
3Initially,weusedE(withtheself-loop)andtriedtoproveKDM-security.
Canetti[15]proposedtheacyclic,leveledapproachtomakethisunnecessary.
Encrypt(pk,π).
Takesasinputthepublickeypkandplain-textπ∈P.
Itsetsψ←Samp(π,BI,R,BpkJ)andoutputsψ←ψmodBpkJ.
Decrypt(sk,ψ).
Takesasinputthesecretkeyskandaci-phertextψ.
Itoutputsπ←(ψmodBskJ)modBIEvaluate(pk,C,Ψ).
Takesasinputthepublickeypk,acir-cuitCinsomepermittedsetCEofcircuitscomposedofAddBIandMultBIgatesandasetofinputciphertextsΨ.
ItinvokesAddandMult,givenbelow,inthepropersequencetocomputetheoutputciphertextψ.
(WewilldescribeCEwhenweconsidercorrectnessbelow.
Ifdesired,onecouldusedierentarithmeticgates.
)Add(pk,ψ1,ψ2).
Outputsψ1+ψ2modBpkJ.
Mult(pk,ψ1,ψ2).
Outputsψ1*ψ2modBpkJ.
Now,letusconsidercorrectness,whichisahighlynon-trivialissueinthispaper.
Thefollowingdenitionsprovidestructureforouranalysis.
Tobegin,weobservethattheschemeisactuallyusingtwodierentcircuits.
First,Evaluatetakesamod-BIcircuitCasinput.
Thiscircuitisimplicitlyappliedtoplaintexts.
Second,EvaluateappliesacircuitrelatedtoC,whichwecallthegeneralizedcircuit,totheciphertexts;thiscircuitusestheringoperations(notmoduloI).
Definition6(GeneralizedCircuit).
LetCbeamod-BIcircuit.
Wesaygeneralizedcircuitg(C)ofCisthecir-cuitformedbyreplacingC'sAddBIandMultBIoperationswithaddition'+'andmultiplication'*'intheringR.
HereareafewmoredenitionsrelevanttoTheorem6below,whichconcernscorrectness.
Definition7(XEncandXDec).
LetXEncbetheimageofSamp.
NoticethatallciphertextsoutputbyEncryptareinXEnc+J.
LetXDecequalRmodBskJ,thedistinguishedrepresentativesofcosetsofJwrtthesecretbasisBskJ.
Definition8(PermittedCircuits).
LetCE={C:(x1,xt)∈XEnct,g(C)(x1,xt)∈XDec}Inotherwords,CEisthesetofmod-BIcircuitsthat,whengeneralized,theoutputisalwaysinXDeciftheinputsareinXEnc.
(ThevaluetwillofcoursedependonC.
)IfCECE,wesaythatCEisasetofpermittedcircuits.
Definition9.
ψisavalidciphertextwrtEpublickeypkandpermittedcircuitsCEifitequalsEvaluate(pk,C,Ψ)forsomeC∈CE,whereeachψ∈ΨisintheimageofEncrypt.
Theorem6.
AssumeCEisasetofpermittedcircuitscontainingtheidentitycircuit.
EiscorrectforCE–i.
e.
,Decryptcorrectlydecryptsvalidciphertexts.
Proof.
ForΨ={ψ1,ψt},ψk=πk+ik+jk,whereπk∈P,ik∈I,jk∈J,andπk+ik∈XEnc,wehaveEvaluate(pk,C,Ψ)=g(C)(Ψ)modBpkJ∈g(C)(π1+i1,πt+it)+JIfC∈CE,wehaveg(C)(XEnc,XEnc)∈XDec;so,Decrypt(sk,Evaluate(pk,C,Ψ))=g(C)(π1+i1,πt+it)modBI=g(C)(π1,πt)modBI=C(π1,πt)asrequired.
ThebottomlineisthatwehaveproventhatEiscorrectforpermittedcircuits,andourgoalnowistomaximizethisset.
Thepermittedcircuitsaredenedsomewhatindirectly;theyarethecircuitsforwhichthe"error"g(C)(x1,xt)oftheoutputciphertextissmall(i.
e.
,liesinsideXDec)whentheinputciphertextsareintheimageofEncryptE.
WhenwebegintoinstantiatetheabstractschemewithlatticesandgivegeometricinterpretationsofXEncandXDec,theproblemofmaximizingCEwillhaveageometricavor.
3.
2SecurityoftheAbstractConstructionForanabstract"instantiation"ofSampthatwedescribemomentarily,weprovideasimpleproofofsemanticsecuritybasedonthefollowingabstractproblem.
Definition10(IdealCosetProblem(ICP)).
FixR,BI,algorithmIdealGen,andanalgorithmSamp1thatef-cientlysamplesR.
ThechallengersetsbR←{0,1}and(BskJ,BpkJ)R←IdealGen(R,BI).
Ifb=0,itsetsrR←Samp1(R)andt←rmodBpkJ.
Ifb=1,itsamplestuniformlyfromRmodBpkJ.
Theproblem:guessbgiven(t,BpkJ).
BasicallytheICPasksonetodecidewhethertisuniformmoduloJ,orwhetheritwaschosenaccordingtoaknown"clumpier"distributioninducedbySamp1.
TogetaproofbasedontheICP,deneSampasfollows.
Lets∈Ibesuchthattheideal(s)isrelativelyprimetoJ.
(Assumefornowthatsuchanscanbeecientlygenerated.
)Samp(x,BI,R,BpkJ).
RunrR←Samp1(R).
Outputx+r*s.
Obviously,theoutputisinx+Isinces∈I.
ThevaluescouldbeaxedparameterwiredintothealgorithmSamp,orgenerateddynamicallyfromBIandBpkJaccordingtoaprescribeddistribution.
Theorem7.
SupposethatthereisanalgorithmAthatbreaksthesemanticsecurityofEwithadvantagewhenitusesSamp.
Then,thereisanalgorithmB,runninginaboutthesametimeasA,thatsolvestheICPwithadvantage/2.
Proof.
ThechallengersendsBaICPinstance(t,BpkJ).
Bsetss,andsetstheothercomponentsofpkintheobviouswayusingtheICPinstance.
WhenArequestsachallengeciphertextononeofπ0,π1∈P,BsetsabitβR←{0,1}andsendsbackψ←πβ+t*smodBpkJ.
Asendsbackaguessβ,andBguessesb←ββ.
Ifb=0,weclaimthatB'ssimulationisperfect;inpartic-ular,thechallengeciphertexthasthecorrectdistribution.
Whenb=0,wehavethatt=r+j,whererwaschosenaccordingtoSamp1andj∈J.
So,ψ←πβ+t*s=πβ+r*smodBpkJ;theciphertextisthuswell-formed.
InthiscaseAshouldhaveadvantage,whichtranslatesintoanadvantageofforB.
Ifb=1,thentisuniformlyrandommoduloJ.
Sincetheideal(s)isrelativelyprimetoJ,t*sisuniformlyrandommoduloJ,andconsequentlyψisauniformlyrandomele-mentofRmodBpkJthatisindependentofβ.
InthiscaseA'sadvantageis0.
Overall,B'sadvantageis/2.
3.
3BackgroundonIdealLatticesLetR=Z[x]/f(x),wheref(x)∈Z[x]ismonicandofdegreen.
Weviewanelementv∈Rbothasaringelementandasavector–specically,thecoecientvectorv∈Zn.
Theideal(v)generatedbyvdirectlycorrespondstothelatticegeneratedbythecolumnvectors{v*ximodf(x):i∈[0,n1]};wecallthistherotationbasisoftheideallattice(v).
Generallyspeaking,anidealIRneednotbeprincipal–i.
e.
,haveasinglegenerator–andabasisBIofIneednotbearotationbasis.
Rcorrespondstotheideal(1)or(e1),andtoZn.
TheHermitenormalform(HNF)ofalatticeIisanuppertriangularbasisthatcanbeecientlycomputablefromanyotherbasisofI,makingitwell-suitedtobeapublickey[39].
Theindex[R:I]equals|det(BI)|;sincethisisinvariant,werefertodet(I).
Asrequiredbyourabstractscheme,foranybasisBIofanidealIR,thetermtmodBIisuniquelydenedasthevectort∈P(BI)suchthattt∈I,whereP(BI)isthehalf-openparallelepipedP(B)←{ni=1xibi:xi∈[1/2,1/2)}.
ThevectortmodBIisecientlycomputableastB·B1·t,where·roundsthecoecientsofavectortothenearestinteger.
WedenethelengthBIofabasistobemax{bi:bi∈BI}.
CryptographicworkonideallatticesincludesNTRU[25]andmorerecentwork[41,32,33,48,49].
3.
4TheInitialConstruction,ConcretelyWhenweimplementtheabstractconstructionusingapolynomialringandideallatticesasdescribedinSection3.
3,thesetsXEncandXDecbecomesubsetsofZn.
Were-characterizethesesetsgeometricallyasfollows.
Definition11(rEncandrDec).
LetrEncbethesmallestvaluesuchthatXEncB(rEnc),whereB(r)istheballofradiusr.
LetrDecbethelargestsuchthatXDecB(rDec).
Now,letusdeneasetofpermittedcircuitsCEasfollows:CE={C:(x1,xt)∈B(rEnc)t,g(C)(x1,xt)∈B(rDec)}CEisdenedlikethemaximalsetCEofpermittedcircuitsinDenition8,butwehavereplacedXEncandXDecwithB(rEnc)andB(rDec).
Clearly,CECE.
(Atseveralpointslaterinthepaper,wenarrowoursetofpermittedcircuitsagainsoastoenablealesscomplexdecryptionalgorithm.
)ForxedvaluesofrEncandrDec,whatisCEThisisageometricproblem,andwecanboundtheEuclideanlengthg(C)(x1,xt)byboundingthelengthsofu+vandu*vintermsofuandv.
Foraddition,thisiseasy:usingthetriangleinequality,wehaveu+v≤u+vforu,v∈R.
Formultiplication,wecanprovethatu*v≤γMult(R)·u·v,whereγMult(R)issomefactorthatisdependentonlyontheringR.
(See[32]foradierentdenitionoftheexpansionfactorformultiplication.
)Thefollowingtheoremcharacterizesthe"errorexpansion"thatacircuitcancausebasedonthecircuit'sdepth.
Theorem8.
SupposerE≥1andthatcircuitC'sadditivefan-inisγMult(R),multiplicativeis2,anddepthisatmostloglogrDloglog(γMult(R)·rE)Then,C(x1,xt)∈B(rD)forallx1,xt∈B(rE).
Proof.
Forad-depthcircuit,letribeanupper-boundontheEuclideannormofthevaluesatleveli,giventhatrd=rE.
Bythetriangleinequality,anaddition(orsubtraction)gateatlevelioutputssomev∈Rsuchthatv≤γMult(R)·ri.
Amultiplicationgateatlevelioutputssomev∈Rsuchthatv≤γMult(R)·r2i.
Ineithercase,ri1≤γMult(R)·r2i,andthusr0≤(γMult(R)·rE)2d.
Theresultfollows.
An(oversimplied)bottomlinefromTheorem8isthat,tomaximizethedepthofcircuitsthatEcancorrectlyevaluate(seeTheorem6),weshouldminimizeγMult(R)andrEnc,andmaximizerDec.
Mostoftheremainderofthissubsectionconsistsofproposalstowardthisgoal.
First,though,weobservethatsemanticsecurityplacesalimitonhowlargewecantakerDec/rEnc.
Inconcreteterms,theICPbecomes(roughly):decidewhethertiswithinasmalldistance(lessthanrEnc)ofthelatticeJ(accordingtoadistributiondeterminedbySamp1),orisuniformlyran-dommoduloJ.
Thisisafairlynaturaldecisionalversionoftheclosestvectorproblem,thoughweareunawareofanequivalentproblemmentionedintheliterature.
Cer-tainlyrDec1/2x>1/(2·B).
ItiseasytoimagineadhocwaysofinstantiatingIdealGen–e.
g.
,onecouldgeneratearandomvectorvandsimplysetBskJtobetherotationbasisofv,andsetBpkJtobetheHNFof(v).
Veryroughlyspeaking,ifvisgeneratedasavectorthatisvery"nearlyparallel"toe1(i.
e.
,thevector(1,0,0)),thentherotationalbasiswillhaverDecwithinasmallfactorofv/2.
ThismethodcanbemadetoensurethatrDeciswithinapolynomialfactorofλ1(J).
Ontheotherhand,onemayprefertogenerateJaccordingtoa"nice"average-casedistributionthatpermitsaworst-case/average-casereduction[1,2,53].
Thisisatechnicalissuethatwetackleinaseparatework.
Westressthatouranalysisbelowregardingthedecryptioncircuitdoesnotrelyonanyoftheconcreteproposalsinthissubsection–e.
g.
,theanalysisdoesnotrequireItobeaprincipalideal.
4.
BOOTSTRAPPABLEYETHere,wedescribetwo"tweaks"totheschemetolowerthedecryptioncomplexityinpreparationforbootstrapping;welabelthetweakedschemeE2.
Next,weanalyzethedecryp-tioncomplexity(andndthatitistoolarge).
However,someoftheanalysisappliestothenalscheme.
WeseparateE2fromE1becausetheformeralreadyim-provesuponpreviouswork,irrespectiveofbootstrapping.
TheBoneh-Goh-Nissim(BGN)pairing-basedcryptosystem[11]wasthersttopermitecientevaluationofquadraticformulasthatmayhaveanarbitrarynumberofmonomials.
However,BGNhasasmallplaintextspace–logλbitsforsecurityparameterλ.
E1allowsbothgreatermultiplicativedepthinthecircuit(whileallowingessentiallyanarbitrarynumberofadditions)andalsoalargerplaintextspace.
4.
1SomeTweakstotheInitialConstructionIneachofthefollowingtweaks,weslightlynarrowoursetofpermittedcircuitsCE.
RecallfromSection3.
4thatE1'sdenitionofCEusedB(rEnc)andB(rDec).
Tweak1:RedenethesetofpermittedcircuitsCE,replac-ingB(rDec)withB(rDec/2).
Purpose:ToensurethatciphertextvectorsareclosertothelatticeJthantheystrictlyneedtobe,sothatwewillneedless"precision"toensurethecorrectnessofdecryption.
RecallthatDecryptcomputes(ψmodBskJ)modBI,whereψmodBskJ=ψBskJ·(BskJ)1·ψ.
Ifwepermittedthecoecientsof(BskJ)1·ψtobeveryclosetohalf-integers,wewouldneedhighprecisiontoensurecorrectrounding.
However,afterTweak1,wehavethefollowinglemma:Lemma2.
IfψisavalidciphertextafterTweak1,theneachcoecientof(BskJ)1·ψiswithin1/4ofaninteger.
Proof.
Observethatψ∈B(rDec/2)+J.
Letψ=x+jforx∈B(rDec/2)andj∈J.
Wehave(BskJ)1·ψ=(BskJ)1·x+(BskJ)1·j,wheretheformertermhascoecientsofmagnitudeatmost1/4byLemma1andthelatterisanintegervector.
PerTheorem8,thenewmaximumevaluationdepthoftheschemeafterTweak1isloglog(rDec/2)loglog(γMult(R)·rEnc),whichislessthantheoriginalamountbyonlyasub-constantadditivefactor.
Tweak2ismoretechnicalandless"essential"thanthersttweak.
Itreplacesmatrix-vectormultiplicationswithringmultiplications.
Thisisnice,butthetwocomputationsareessentiallyequallyparallelizable,andtheircircuitshaveessentiallythesamedepth.
So,really,thistweakisprimar-ilyusefulforreducingthepublickeysizeandtheper-gatecomputationduringbootstrappinginourultimatescheme.
Tweak2:FromBIandBskJ,computeashortvectorvskJ∈J1suchthatthereexistsu∈1+Iwithu*(vskJ)1∈1+I.
Also,redeneCEagain,nowusingB(2·rDec/(n1.
5·γMult(R)2·BI)).
Purpose:TomodifyDecryptfromψBskJ·(BskJ)1·ψmodBItothesimplerexpressionψvskJ*ψmodBI,wherevskJ∈Q[x]/f(x).
Tousebothtweaks,weneedtoreducetheradiusofthesphereinTweak2byanadditionalfactorof2.
Tweak2requiresustoreducethepermitteddistanceofciphertextsfromtheJ-latticemuchmorethanTweak1.
Still,itdoesnotaectourmaximumevaluationdepthverymuchwhenγMult(R)andBIarepolynomialinn,andrDec/rEncissuper-polynomial.
ThefollowingtwolemmassaythatwecanperformTweak2ecientlyandthatithastheexpectedeect–i.
e.
,thenewDecryptequationworkscorrectly.
Lemma3.
FromBIandBskJ,wecancomputeinpolyno-mialtimeavectorvskJ∈J1andavectoru∈1+Isuchthatu*(vskJ)1∈1+I.
Moreover,vskJ≤(n/2)·γMult(R)·((BskJ)1)T·BI.
Lemma4.
SupposeψisavalidciphertextafterTweak2whichdecryptstoπ.
Then,π=ψvskJ*ψmodBI.
4.
2DecryptionComplexityofTweakedSchemeTodecrypt,wecompute(ψBsk1J·Bsk2J·ψ)modBIwhereψ∈Zn,Bsk1J∈Zn*n,Bsk2J∈Qn*n,andBIisabasisofanidealIofR=Z[x]/f(x).
FromTweak1,wehavethepromisethatthecoecientsofBsk2J·ψareallwithin1/4ofaninteger.
Optionally,Tweak2ensuresthatBsk1JistheidentitymatrixandBsk2Jisarotationmatrix.
Wesplitthedecryptioncomputationintothefollowingsequenceofsteps:Step1:GeneratenvectorswithsumBsk2J·ψStep2:Fromthenvectorsx1,xn,generateintegervectorsy1,yn+1withsumxi.
Step3:Computeπ←ψBsk1J·(yi)modBIInStep1,toobtainthenvectors,weperformthemulti-plicationsassociatedtotheinnerproductsassociatedtothematrix-vectormultiplication;wedonotdiscussthisstepindetail,since(wewillndthat)Step2isalreadytooexpen-sivetopermitbootstrappability.
RegardingStep2,recallthatEvaluatetakesasinputcir-cuitswithmod-BIgates–i.
e.
,arithmeticgateswhosein-putsandoutputsareinRmodBI.
However,ingeneral"base-BI,"itisunclearhowtohandlethecarriesneededforaddingthevectorsinStep2withoutresortingtohigh-degreepolynomialsthatrequiremoremultiplicativedepththatourinitialconstructioncanevaluate.
Tohandlethiscomplication,weusetheplaintextspaceP={0,1}modBI,regardlessoftheunderlyingidealI.
Weemulatebooleanop-erations,wherecarriesareconstant-depth.
(Thisplaintextspacerestrictionisunnecessaryifweusetheinitialconstruc-tionwithoutbootstrapping.
)Wehavethefollowinglemma.
Lemma5.
Fori∈[1,t],letaiai,1,ai,0,ai,1,.
.
.
)bearealnumbergiveninbinaryrepresentationmodBIwiththepromisethatiaimod1∈[1/4,1/4].
Thereisamod-BIcircuitCforgeneratingt+1integersz1,zt+1(alsorepresentedinbinary)whosesumisiai,suchthatifthegeneralizedcircuitg(C)'sinputsareinB(rin),thenitsoutputsareinB(rout)for:rout≤(γMult(R)·n·BI·(1+γMult(R)·rin)t·t)polylog(t)ForBI≤rin,t≤n,andγMult(R)=n(1),wehave:rout≤(γMult(R)·rin)t+polylog(t)Proof(fragment).
Letaibetheintegerpartofaiandletai=(ai,1,ai,2,bethefractionalpart.
LetT=logt+2.
Letbi=(ai,1,ai,T).
First,weclaimthatai=bi.
Thisclaimfollowsfromthepromisethatiaiiswithin1/4ofaninteger,andthatiaiibi=j∈[T+1,∞]i2j·ai,j1ischosensothat(α1)·γsubset(n)isgreaterthanthepolylog(γsubset(n))termcomingfromLemma5,andcisaconstantrepresent-ingthedepthneededinacircuithavingAddBIgateswithγMult(R)=n(1)fan-inandMultBIgateswithconstantfan-intosequentiallyperformDecryptESteps0,1,3,and4,andaNANDgate.
Proof.
AsintheproofofTheorem8,forac-levelcircuit,iftheinputstothegeneralizedcircuitareinB(r),theout-putsareinB((γMult(R)·r)2c).
CombiningwithLemma5,wehavethatiftheinputstoourgeneralizedNAND-augmenteddecryptioncircuitareinB(rEnc),theoutputisin(γMult(R)·rEnc)2c·(γsubset(n)+polylog(γsubset(n)))TheresultfollowswhenthisvalueisatmostrDec/m.
Forexample,supposeγMult(R)·rEncispolynomialinn,andrDec=2nCforC<1.
Inthiscase,γsubset(n)canbepolyno-mialinn(butsub-linear).
Theconstantcisnotverylarge,thoughinpracticeonewouldwanttooptimizeitbeyondwhatwehavedone.
5.
4OntheNewHardnessAssumptionConcretely,theSplitKeyDistinguishingProblembecomes:Definition13(SplitKeyDP,concreteversion).
Letγset(n)andγsubset(n)befunctionsasabove,andBIabasisofanidealI.
Thechallengersets(sk,pk)R←KeyGenEandbR←{0,1},whereskincludesthesecretvectorvskJ∈R.
Ifb=1,itsetsvskJ←0.
Itsetsτtobeasetofγset(n)vectorst1,tγset(n)thatareuniformlyrandominJ1modBIsubjecttotheconstraintthatthereexistsasub-setS{1,γset(n)}ofcardinalityγsubset(n)suchthati∈Sti∈vskJ+I.
Theproblem:guessbgiven(τ,sk,pk).
Thisproblemisrelatedtothefollowingproblem,whichhasbeenanalyzedinconnectionwithserver-aidedcryptography[34,51,44,38,43],andwhichshouldnotbeconfusedwiththelow-densityknapsackproblem[45].
Definition14(SparseSubsetSumProblem(SSSP)).
Letγset(n)andγsubset(n)befunctionsasabove.
Letqbeapositiveinteger.
ThechallengersetsbR←{0,1}.
Ifb=0itgeneratesτasasetofγset(n)integers{a1,aγset(n)}in[q/2,q/2]thatareuniformlyrandom,exceptthatthereexistsasubsetS{1,γset(n)}ofcardinalityγsubset(n)suchthati∈Sai=0modq.
Ifb=1,itsetstheelementswithouttheconstraint.
Theproblem:guessbgivenτ.
KnownattacksontheSSSP[51,44,38,43]arefeasibleonlyforlimitedchoicesofparameters.
Someofthese[51](andpreviousrelatedresults[58,17])essentiallyamounttoatime-spacetradeowhosecomplexityisγset(n)O(γsubset(n));theseonlyrequireustotakeγsubset(n)=ω(1).
NguyenandShparlinski[43]presentalattice-basedcryptanalysisoftheSSSPthatprovablysucceedswithadvantageatleast1(γsubset(n)γset(n)+2·α)/qwhereαisatermthatisgreaterthan1.
Theattackbreaksdownwhenγset(n)exceedslogq.
Thoughweomitdetails,currentattacksagainstourcon-creteversionSplitKeyDPbegintobreakdownwhenγset(n)exceedslogdet(IJ).
Theintuitionisthat,onceγset(n)issucientlylarge,therewillbeexponentiallymanysubsetsinτ(notnecessarilysparse)whosevectorsumiscongruenttovskJ;latticereductiontechniqueshavetroubleextractingthesparsesubsetfromamongthemanysubsetsolutions.
6.
PERFORMANCEOurschemereliesontwoassumptions.
Therstassump-tionunderliesthesecurityE1anditsapproximationfactorismildlyimpactedbythetweaksofE2.
Thesecondarisesfromtheadditionofτtothepublickey.
Interestingly,thetwoas-sumptionscounterbalanceeachother:increasingγsubset(n)seemstomakethesecondproblemharder,butattheex-penseofincreasingtheapproximationfactorintherstproblem,makingtherstproblemeasier.
Usingacrudeanalysis,thebreakingtimeforthesecondproblemusingknownattacksisroughly2γsubset(n).
(Weignoreconstantsandlogarithmicfactorsintheexponent.
)Theapproximationfactorfortherstproblemisalsoroughly2γsubset(n).
Usingtheruleofthumbthatalatticeprob-lemforapproximationfactor2ktakestimeabout2n/k,thebreakingtimefortherstproblemisroughly2n/γsubset(n).
Settingγsubset(n)←√nmaximizestheminimalbreakingtimeatabout2√n.
Tomakethisbreakingtimetrulyexpo-nentialinthesecurityparameterλ,weneedn≈λ2.
Foreachgate,weevaluatethecircuitDEhomomorphi-cally.
(Actually,thereisatradeohere,sincea"gate"canbetakentobea"normalcircuit"ofdepthgreaterthan1.
)Thoughitisashallowcircuit,thecomputationalcomplex-ityofDEitselfinE3(notevaluatedhomomorphicallyintheencryptionscheme)isquitehigh(butpoly(λ)),primar-ilyduetothelargeunaryrepresentationofthesecretkeyinE3.
Thefactthatdecryptionisperformedhomomorphically,withciphertextelementsinRmodBpkJbeingusedinsteadofplaintextelementsinRmodBI,multipliesthecomplexitybyanotherfactorthatisquasi-linearinn·γsubset(n),sinceroughlylogdet(IJ)≈n·logrDec/rEnc≈n·γsubset(n)bitsofprecisionareneeded,butagainthisispolynomialinλ.
Twooptimizationsare:1)onecanreducethesizeoftheE3secretkeysubstantiallybyallowingamodestincreaseinthedepthofthedecryptioncircuit,and2)thehomomorphicde-cryptioncircuitcantaketheciphertextbitsasinputdirectly[15](ratherthantheencryptedciphertextbits).
Makingthefullschemepracticalremainsanopenproblem(thoughE1isquitepracticalforshallowcircuits).
7.
CIRCUITPRIVACYWeomitfulldetailsduetolackofspace,butmentionthatonecanconstructanalgorithmRandomizeCTEforourE2thatcanbeappliedtociphertextsoutputbyEncryptE2andEvaluateE2,respectively,thatinducesequivalentoutputdistributions.
ThecircuitprivacyofE2immediatelyimpliesthe(leveled)circuitprivacyofour(leveled)fullyhomomor-phicencryptionscheme.
Theideaissimple:toconstructarandomencryptionψofπfromaparticularencryptionψofπ,wesimplyaddanencryptionof0thathasamuchlargerrandom"error"vectorthanψ–super-polynomiallylarger,sothatthenewerrorvectorstatisticallyobliteratesallinformationaboutψ'serrorvector.
Thisentailsanotherre-denitionofCE.
8.
ACKNOWLEDGMENTSWethankBoazBarak,DanBoneh,RanCanetti,ShaGoldwasser,IftachHaitner,YuvalIshai,TalRabin,YaelTaumanKalai,SalilVadhan,andBrentWatersforveryhelpfuldiscussions.
9.
REFERENCES[1]M.
Ajtai.
Generatinghardinstancesoflatticeproblems(extendedabstract).
STOC'96,pp.
99–108.
[2]M.
AjtaiandC.
Dwork.
Apublickeycryptosystemwithworst-case/average-caseequivalence.
STOC'97,pp.
284–293.
[3]J.
H.
An,Y.
Dodis,andT.
Rabin.
Onthesecurityofjointsignatureandencryption.
Eurocrypt'02,pp.
83–107.
[4]F.
ArmknechtandA.
-R.
Sadeghi.
Anewapproachforalgebraicallyhomomorphicencryption.
Eprint2008/422.
[5]L.
Babai.
OnLovasz'slatticereductionandthenearestlatticepointproblem.
Combinatorica6(1986),1–14.
[6]D.
Barrington.
Bounded-widthpolynomial-sizebranchingprogramsrecognizeexactlythoselanguagesinNC1.
STOC'86,pp.
1–5.
[7]D.
Beaver.
Minimal-latencysecurefunctionevaluation.
Eurocrypt'00,pp.
335–350.
[8]J.
Benaloh.
Veriablesecret-ballotelections.
Ph.
D.
thesis,YaleUniv.
,Dept.
ofComp.
Sci.
,1988.
[9]J.
Black,P.
Rogaway,andT.
Shrimpton.
Encryption-schemesecurityinthepresenceofkey-dependentmessages.
SAC'02,pp.
62–75.
[10]M.
Blaze,G.
Bleumer,andM.
Strauss.
Divertibleprotocolsandatomicproxycryptography.
Eurocrypt'98,pp.
127–144.
[11]D.
Boneh,E.
-J.
Goh,andK.
Nissim.
Evaluating2-DNFformulasonciphertexts.
TCC'05,pp.
325–341.
[12]D.
Boneh,S.
Halevi,M.
Hamburg,andR.
Ostrovsky.
Circular-SecureEncryptionfromDecisionDie-Hellman.
Crypto'08,pp.
108–125.
[13]D.
BonehandR.
Lipton.
SearchingforElementsinBlack-BoxFieldsandApplications.
Crypto'96,pp.
283–297.
[14]J.
Boyar,R.
Peralta,andD.
Pochuev.
OntheMultiplicativeComplexityofBooleanFunctionsovertheBasis(∧,,1).
Theor.
Comput.
Sci.
235(1),pp.
43–57,2000.
[15]R.
Canetti.
Personalcommunication,2008.
[16]R.
Canetti,H.
Krawczyk,andJ.
B.
Nielsen.
Relaxingchosen-ciphertextsecurity.
Crypto'03,pp.
565–582.
[17]D.
CoppersmithandG.
Seroussi.
Ontheminimumdistanceofsomequadraticresiduecodes.
IEEETrans.
Inform.
Theory30(1984),407–411.
[18]W.
vanDam,S.
Hallgren,andL.
Ip.
QuantumAlgorithmsforSomeHiddenShiftProblems.
SIAMJ.
Comput.
,v.
36.
,no.
3,pp.
763–778,2006.
[19]I.
DamgardandM.
Jurik.
ALength-FlexibleThresholdCryptosystemwithApplications.
ACISP'03,pp.
350–356.
[20]T.
ElGamal.
APublic-KeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms.
Crypto'84,pp.
469–472.
[21]M.
FellowsandN.
Koblitz.
Combinatorialcryptosystemsgalore!
ContemporaryMathematics,v.
168ofFiniteFields:Theory,Applications,andAlgorithms,FQ2,pp.
51–61,1993.
[22]S.
GoldwasserandD.
Kharchenko.
ProofofplaintextknowledgefortheAjtai-Dworkcryptosystem.
TCC2005,pp.
529–555.
[23]S.
GoldwasserandS.
Micali.
Probabilisticencryptionandhowtoplaymentalpokerkeepingsecretallpartialinformation.
STOC'82,pp.
365–377.
[24]S.
HaleviandH.
Krawczyk.
Securityunderkey-dependentinputs.
ACMCCS'07.
[25]J.
Hostein,J.
Silverman,andJ.
Pipher.
NTRU:ARingBasedPublicKeyCryptosystem.
InProc.
ofANTS'98,LNCS1423,pages267–288.
[26]Y.
IshaiandA.
Paskin.
EvaluatingBranchingProgramsonEncryptedData.
TCC'07.
[27]A.
Kawachi,K.
Tanaka,K.
Xagawa.
Multi-bitcryptosystemsbasedonlatticeproblems.
PKC'07,pp.
315–329.
[28]A.
K.
Lenstra,H.
W.
Lenstra,L.
Lovasz.
Factoringpolynomialswithrationalcoecients.
Math.
Ann.
261(4)(1982)515–534.
[29]F.
Levy-dit-VehelandL.
Perret.
APollyCrackersystembasedonsatisability.
InCoding,Crypt.
andComb.
,Prog.
inComp.
Sci.
andApp.
Logic,v.
23,pp.
177–192.
[30]L.
Ly.
Apublic-keycryptosystembasedonPollyCracker,Ph.
D.
thesis,Ruhr-Universit¨atBochum,Germany,2002.
[31]L.
Ly.
Pollytwo–anewalgebraicpolynomial-basedpublic-keyscheme.
AAECC,17(3-4),2006.
[32]V.
LyubashevskyandD.
Micciancio.
Generalizedcompactknapsacksarecollisionresistant.
ICALP'06.
[33]V.
LyubashevkyandD.
Micciancio.
Asymptoticallyecientlattice-baseddigitalsignatures.
TCC'08.
[34]T.
Matsumoto,K.
Kato,andH.
Imai.
Speedingupsecretcomputationswithinsecureauxiliarydevices.
Crypto'88,pp.
497–506.
[35]U.
MaurerandD.
Raub.
Black-BoxExtensionFieldsandtheInexistenceofField-HomomorphicOne-WayPermutations.
Asiacrypt'07,pp.
427–443.
[36]C.
A.
Melchor,G.
Castagnos,andP.
Gaborit.
Lattice-basedhomomorphicencryptionofvectorspaces.
ISIT'08,pp.
1858–1862.
[37]C.
A.
Melchor,P.
Gaborit,andJ.
Herranz.
AdditiveHomomorphicEncryptionwitht-OperandMultiplications.
Eprint2008/378.
[38]J.
Merkle.
Multi-roundpassiveattacksonserver-aidedRSAprotocols.
ACMCCS'00,pp.
102–107.
[39]D.
Micciancio.
ImprovingLatticeBasedCryptosystemsUsingtheHermiteNormalForm.
CaLC'01,pp.
126–145.
[40]D.
Micciancio.
Improvedcryptographichashfunctionswithworst-case/average-caseconnection.
STOC'02,pp.
609–618.
[41]D.
Micciancio.
Generalizedcompactknapsacks,cycliclattices,andecientone-wayfunctionsfromworst-casecomplexityassumptions.
FOCS'02,pp.
356–365.
[42]D.
NaccacheandJ.
Stern.
ANewPublic-KeyCryptosystemBasedonHigherResidues.
ACMCCS'98.
[43]P.
Q.
NguyenandI.
Shparlinski.
OntheInsecurityofSomeServer-AidedRSAProtocol.
Asiacrypt'01,pp.
21–35.
[44]P.
Q.
NguyenandJ.
Stern.
TheBeguin-Quisquaterserver-aidedRSAprotocolfromCrypto'95isnotsecure.
Asiacrypt'98,pp.
372–379.
[45]A.
M.
Odlyzko.
Theriseandfallofknapsackcryptosystems.
InCrypt.
andComp.
Num.
Th.
,Proc.
Sympos.
Appl.
Math.
,vol.
42,AMS,1990,pp.
75–88.
[46]T.
OkamotoandUchiyama.
ANewPublic-KeyCryptosystemasSecureasFactoring.
Eurocrypt'98,pp.
308–318.
[47]P.
Paillier.
Public-KeyCryptosystemsBasedonCompositeDegreeResiduosityClasses.
Eurocrypt'99,pp.
223–238.
[48]C.
PeikertandA.
Rosen.
Ecientcollision-resistanthashingfromworst-caseassumptionsoncycliclattices.
TCC'06,pp.
145–166.
[49]C.
PeikertandA.
Rosen.
LatticesthatAdmitLogarithmicWorst-CasetoAverage-CaseConnectionFactors.
STOC'07,pp.
478–487.
[50]C.
PeikertandB.
Waters.
LossyTrapdoorFunctionsandTheirApplications.
STOC'08,pp.
187–196.
[51]B.
PtzmannandM.
Waidner.
Attacksonprotocolsforserver-aidedRSAcomputation.
Eurocrypt'92,pp.
153–162.
[52]M.
PrabhakaranandM.
Rosulek.
HomomorphicEncryptionwithCCASecurity.
ICALP'08.
[53]O.
Regev.
OnLattices,LearningwithErrors,RandomLinearCodes,andCryptography.
STOC'05,pp.
84–93.
[54]R.
Rivest,L.
Adleman,andM.
Dertouzos.
Ondatabanksandprivacyhomomorphisms.
InFoundationsofSecureComputation,pp.
169–180,1978.
[55]R.
Rivest,A.
Shamir,andL.
Adleman.
Amethodforobtainingdigitalsignaturesandpublic-keycryptosystems.
InComm.
oftheACM,21:2,pages120–126,1978.
[56]T.
Sander,A.
Young,andM.
Yung.
Non-interactivecryptocomputingforNC1.
FOCS'99,pp.
554–567,1999.
[57]C.
P.
Schnorr.
AHierarchyofPolynomialTimeLatticeBasisReductionAlgorithms.
TheoreticalComputerScience,53(2-3):201–224,1987.
[58]D.
R.
Stinson.
Somebaby-stepgiant-stepalgorithmsforthelowhammingweightdiscretelogarithmproblem.
MathematicsofComputation,vol.
71,no.
237,pages379–391,2001.