4.Rings--环上的全同态构造

ChinaSummerSchoolonLatticesandCryptographyCraigGentryandShaiHaleviJune4,2014HomomorphicEncryptionoverPolynomialRingsTheRingLWEProblem(RLWE)RecallLWELWE(traditionalformulation):Hardtodistinguishbetween(A,b=As+e)and(A,b=uniform).LWE(alternativeformulation):HardtodistinguishwhethermatrixB=(b,A)isuniform,orthereexistsavectort=(1,-s)suchthate=B·tisshort.MatricesandvectorsareovertheringZq.Whatifweputthematricesandvectorsoveradifferentring–e.g.,apolynomialring?PolynomialRingsExample:Zq[x]/(xN-1)–polynomialsofdegreeN-1(whichhaveNcoefficients)overZq.Addition:Addthepolynomialsmoduloq.Multiplication:Multiplythe2polynomials,reducetheresultmoduloqandmoduloxN-1,sothatthefinalresulthasdegreeatmostN-1again.a(x)b(x)=Σaj·bk·xj+kmodN.Example:Zq[x]/ФN(x)–polynomialsmoduloqandtheN-thcyclotomicpolynomialE.g.,ФN(x)=(xN/2+1)whenNisapowerof2RLWE:LWEoverPolynomialRingsRLWE:Hardtodistinguishbetween(A,b=As+e)and(A,b=uniform)when:A∈Rmx1,s∈R,ande∈Rmisavectorof“small”R-elementsRisanappropriatepolynomialringAcyclotomicringwhereФN(x)hasdegreen=φ(N)suitablylargerthanthesecurityparameter.RLWE(alternativeformulation):HardtodistinguishwhethermatrixB∈Rmx2isuniform,orthereexistsavectort=(1,-s)∈R2suchthate=B·tisshort,whereRisapolynomialring.“Hardness”comesfromhighdimensionofring,ratherthanhighdimensionofvectors.[LPR10]:Worst-case/average-casereductionfor“ideallattices”ProsandConsofRLWE(vsLWE)Con:SecurityLWEisashardonaverageasworst-caseproblemsovergeneral(any)latticesRLWEisashardonaverageasworst-caseproblemsoverideallattices(aspecialtypeoflattice)Pro:EfficiencyFastFourierTransform(FFT):multiplyingringelementsisfastevenifringhashighdimensionTakesO(nlogn)timeforringsofdimensionnAlso,RLWEpermitssmallerpublickeys,largerplaintexts,andmoreefficienthomomorphiccomputation.Regev’sEncryptionSchemewithRLWEInLWE-Regev,m=O(nlogq).ForRLWE-Regev,m=O(logq).Regev’sEncryptionSchemewithRLWEIfRhasdimensionn,Encryptiontakestimequasilinearinn.(InLWE-Regevwithvectorsofdimn,thetimeisquasi-quadraticinn.)Theplaintextspaceislarger:R2insteadofjust{0,1}.Regev’sEncryptionSchemewithRLWETheNTRUEncryptionSchemeNTRU:EvenSimplerEncryptionUsingPolynomialRingsSecretkey:Singlesmallelements∈R.Ciphertext:cencryptsμ∈{0,1}if:c=(μ+2·small)/smodqSecurityintuition:Inamod-qpolynomialring,ratiosofsmallelementslookrandom.NTRUDetailsNTRUHomomorphicOperationsKeySwitchingfroms1tos2.HomomorphicComputationonEncryptedArrays(SIMDOperations)EncryptedArraysSupposeweuseamod-15plaintextspace(notmod-2)Z15=Z3×Z5.ChineseRemainderTheorem(CRT).Fromone“big”plaintextspaceweget2independent“small”plaintextspaces.Wecallthemtwo“plaintextslots”.Supposetwociphertextscandc’have(r3,r5)and(r3’,r5’)intheirrespectivemod-3andmod-5“plaintextslots”cADD=ADD(c,c’)has(r3+r3’,r5+r5’)initsslots.cMULT=MULT(c,c’)has(r3∙r3’,r5∙r5’)initsslots.Homomorphicopsactcomponent-wise,inparallel,onslots.OurWeirdCyclotomicPlaintextSpaceSWHEinPolynomialRingsPlaintextspaceisR2=Z2[x]/ФN(x).Themessageμ(x)isapolynomialinR2.μhasnbits,wherenisthedegreeofФN(x).NTRUexample:μ=[[c·s]q]2overtheringR.Canwegetmany“plaintextslots”outofR2?Sure…OurWeirdCyclotomicPlaintextSpaceViaCRT,R2decomposesintoaboutN/log(N)plaintextslotsofaboutlog(N)bitsapiece(forwell-chosenN).ADDandMULTworkinparallelacrosstheslots.Viaringautomorphisms,encrypteddatacanbemovedbetweenslots.WehaveADD,MULT,andPERMUTE.Canevaluatebooleancircuitswithciphertexts“packed”.Reducesoverhead.TheplaintextspaceR2=Z2[x]/ФN(x)hasamazingproperties!Muchbetterthanamod-15plaintextspace!ChineseRemainderTheoremforCyclotomicRingsChooseNsothatФN(x)factorsmod2intotfactors.ФN(x)=fi(x)mod2.Degreesoff1,…,ftared=φ(N)/t.ChineseRemainderTheorem(CRT)–polynomialversionZ2[x]/ФN(x)=Z2[x]/f1(x)×…×Z2[x]/ft(x)Ifciphertextscandc’have(r1(x),…,rt(x))and(r1’(x),…,rt’(x))intheirrespectiveplaintextslotscADD=ADD(c,c’)has(r1(x)+r1’(x),…,rt(x)+rt’(x)).cMULT=MULT(c,c’)has(r1(x)∙r1’(x)modf1(x),…,rt(x)∙rt’(x)modft(x)).Homomorphicopsactcomponent-wise,inparallel,onslots.SIMD(SingleInstructionMultipleData):WorkingonDataArrays82093801…4421950736…12n-ADDArrayoflengthn10391431537…56SIMD(SingleInstructionMultipleData):WorkingonDataArrays16204505606…4882093801…4421950736…12n-MULTArrayoflengthnSIMD(SingleInstructionMultipleData):WorkingonDataArrays%%%%%%%%…%%GreatforcomputingsamefunctionFonndifferentinputstrings.WecandoSIMDhomomorphically.82093801…4421950736…12FunctionFArrayoflengthn36334178…85…PermutingEncryptedArraysandRingAutomorphismsBeyondSIMDComputationGoal:Toreduceoverheadforasinglecomputation(ratherthanmultiplecomputationsinparallel):PackallinputbitsinjustafewciphertextsComputewhilekeepingeverythingpackedHowtodothis?AreADDandMULTaCompleteSetofOperations?Yes,forbits.+++++++++++++×××××××××××+++++++++0111x1x2x3x4x5x7x8x9x10x11x12x14x15x16x17x18x19ADDandMULTareacompletesetofoperations.+++++++++++++×××××××××××+++++++++0111x1x2x3x4x5x7x8x9x10x11x12x14x15x16x17x18x19x8x9x10x11x12x14x1x2x3x4x5x7n-ADDandn-MULTareNOTacompletesetofoperations.AreADDandMULTaCompleteSetofOperations?No,forSIMDarra