密码算法与协议3-密钥的确认

2023/11/251Chapter3.

CommitmentSchemes2023/11/252IntroductionThefunctionalityofacommitmentschemeiscommonlyintroducedbymeansofthefollowinganalogy.Supposeyouneedtocommittoacertainvalue,butyoudon’twanttorevealitrightaway.Forexample,thecommittedvalueisasealedbidinsomeauctionscheme.Onewaytodothisistowritethevalueonapieceofpaper,putitinabox,andlocktheboxwithapadlock.Thelockedboxisthengiventotheotherparty,butyoukeepthekey.Atalatertime,youpresentthekeytotheotherpartywhomaythenopenthebox,andcheckitscontents.2023/11/253CoinFlippingovertheTelephoneAnimmediateapplicationofcommitmentschemesisknownas“coinflippingoverthetelephone”oras“coinflippingintoawell”.Twoparties,sayAandB,determineamutuallyrandombitasfollows.PartyAcommitstoarandombitvaluebA

R{0,1}bysendingacommitmentonbAtopartyB.PartyBthenrepliesbysendingabitvaluebB

R{0,1}toA.Finally,partyAopensthecommitmentandsendsbAtoB.Bothpartiestakeb=bA

bBasthecommonrandombit.Ifatleastoneofthepartiesishonest,theresultingbitbisdistributeduniformlyatrandom,assumingthatAandBcannotcheatwhenrevealingtheirbits.2023/11/254ApplicationofCommitmentNotethatpartyBseesthecommitmentofAbeforechoosingitsbitbB,sonoinformationonbitbAshouldleakfromthecommitmentonbA.Similarly,partyAcouldtrytoinfluencethevalueoftheresultingbitb(afterseeingthebitbB)byopeningthecommitmentonbAasacommitmenton1-bA.Clearly,partyAshouldnotbeableto“changeitsmind”insuchaway!Generatingmutuallyrandombitsisabasicpartofmanyprotocols.Commitmentsareusedasanauxiliarytoolinmanycryptographicapplications,suchaszero-knowledgeproofsandsecuremulti-partycomputation.2023/11/255CommitmentSchemeAcommitmentschemeconsistsoftwoprotocols,calledcommit

andreveal,betweentwoparties,usuallycalledthesenderandthereceiver.Inmanycases,theprotocolscommitandrevealcanbedefinedintermsofasinglealgorithm,requiringnointeractionbetweenthesenderandreceiveratall.Suchcommitmentschemesarenon-interactive.2023/11/256

ReceiverCommitPhaseRevealPhaseSenderReceiverXCommitmentProtocol

Receivercanverify

X

wasthevalueintheboxSenderisboundtoXXSender2023/11/257BitCommitment:LockingaBitinaSecureBoxf:{0,1}XYisbitcommitmentschemeifforarandomlychosenxfromXConcealing:forabitb

{0,1},Verifier(Receiver)cannotdeterminethevaluebfromf(b,x),theblobBinding:Prover(Sender)canlateropentheblobbyrevealingthevalueofx.TheProvershouldnotbeabletoopentheblobasboth0or12023/11/258FollowingCommitPhaseReceivershouldnothavegainedanyinformationaboutXInformationtheoretic?Computationally?SendershouldbeboundtoXNotwodifferentandvalidopeningsexistItiscomputationallyinfeasibletofindtwodifferentvalidopenings2023/11/259BitCommitmentbyEncryption(Example1)LetK=(n=pq,e,d)beanRSAkeyTocommitabitb,wecoulddothefollowingChoosearandomxsuchthatxisevenifb=0xisoddifb=1Letblob(b)=xemodnToopenblob(b),justreviewx,usetheencryptiontocheck!Concealing:b不参与其中运算Binding:不存在x1(odd),x2(even),x1e=x2emodn2023/11/2510BitCommitmentbyEncryption(Example2)LetK=(n=pq,p,qprimes,),(n,m)publishedTocommitabitb,wecoulddothefollowingChoosearandomxsuchthatY=f(b,x)=mbx2modnToopenblob(b),justreviewbandx,usetheencryptiontoverify:y=f(b,x)=mbx2modnConcealing:如果平方剩余问题不可解，noinformationonbwillberevealedBinding:ifnot,thenexistx1,x2,commit(x1,,1)=commit(x2,,0),mx12=x22modn,thenm=(x2x1-1)2(modn),itiscontradictiontothecondition.2023/11/2511DefinitionLetcommit:{0,1}k×{0,1}*

{0,1}*beadeterministicpolynomialtimealgorithm,wherekisasecurityparameter.A(noninteractive)commitmentschemeconsistsoftwoprotocolsbetweenasenderandareceiver:Commitprotocol:Tocommittoavaluex

{0,1}*,thesendercomputesC=commit(r,x),wherer

R{0,1}k,andsendsCtothereceiver.Revealprotocol:ToopencommitmentC=commit(r,x),thesendersendsrandxtothereceiver.Thereceivercomputescommit(r,x)andverifiesthatitisequaltothepreviouslyreceivedcommitment.Inthespecialcasethatthecommittedvalueisabit,thatis,x

{0,1},onespeaksofabitcommitmentscheme.2023/11/2512SecurityRequirementsThesecurityrequirementsforabitcommitmentschemearethefollowing.Thecommitmentmustbebinding,i.e.,foranyadversaryA,theprobabilityofgeneratingr,r’

{0,1}ksatisfyingcommit(r,0)=commit(r’,1)shouldbenegligible(asafunctionofk).Furthermore,thecommitmentmustbehiding,i.e.,thedistributionsinducedbycommit(r,0)andcommit(r,1)(withr

R{0,1}k)areindistinguishable.2023/11/2513SomedistinctionsAcommitmentschemeiscalledcomputationallybinding

iftheadversaryAisrestrictedtobeap.p.t.algorithm.theschemeiscalledinformationtheoreticallybinding

ifnosuchrestrictionismade(inotherwords,theadversarymaybeunlimitedpowerful).Similarly,theschemeiscalledcomputationallyhiding

ifthedistributionsinducedbycommit(r,0)andcommit(r,1)arepolynomiallyindistinguishableandtheschemeiscalledinformation-theoreticallyhiding

ifthesedistributionsarestatisticallyindistinguishable.2023/11/2514SecurityPropertiesThesecuritypropertiesareeasilyextendedtothecasethatxisanarbitrarystring.Notethattheabovesecurityrequirementsonlycoverattacksbyeitherthesenderorthereceiver.Forexample,supposepartyAactsasthesenderandpartyBactsasthereceiver,andAsendsacommitmentCtoB.ThenthereisnoguaranteethatBwillnoticeifanattackerreplacesCbyacommitmentC’=commit(r’,x’)duringthecommitprotocol,andreplacesr,xbyr’,x’duringtherevealprotocol.SuchattacksmaybestoppedbyusinganauthenticatedchannelbetweenAandB.2023/11/2515CommitmentUsingaHashFunctionGivenacryptographichashfunctionHoneobtainsabitcommitmentschemesimplybysettingcommit0(r,b)=H(r,b),whereb

{0,1}andr

R{0,1}k.ThepreimageresistanceofHguaranteesthatthevalueofbremainshidden(aswellasthevalueofr).Theschemeisthereforehiding.Collision-resistanceofHguaranteesthatthecommittercannotpreparer,bandr’,1-bwithH(r,b)=H(r’,1-b).Hence,theschemeisbindingaswell.Moreprecisely,weconcludethattheschemeiscomputationallybindingandcomputationallyhiding.Canwedobetter?2023/11/2516BitCommitment-Suggestion1AliceBob1SHA-101001CommitmentAliceBob1Unveiling2023/11/2517BitCommitment-Suggestion2AliceBob1101110100SHA-101001CommitmentAliceBob1101110100Unveiling2023/11/2518BitCommitment-AssumptionsHashisonewayandcollision-freeAliceiscomputationallyboundedHashdoesn’t“leak”informationExampleofa“leaky”hash:1101110100SHA-1100112023/11/2519CommitmentUsingaDiscreteLogSettingLetG=<g>beagroupofordern,wherenisalargeprime.Leth

RG\{1}denotearandomgroupelement(suchthatlogghisnotknowntoanyparty).Wedefinethefollowingbitcommitmentscheme(knownas“Pedersen’scommitmentscheme”):commit1(r,b)=grhb,wherer

RZn.Thisschemeiscomputationallybinding(undertheDLassumption),whichcanbeseenasfollows.Supposeitiscomputationallyfeasibletocomputer,r’

Znsuchthatcommit1(r,b)=commit1(r’,1-b).Thatmeansthatgrhb=gr’h1-b,hencethatloggh=(r-r’)/(1-2b).Sincer,r’,andbareallknown,thismeansthatthediscretelogofhwithrespecttogwouldbecomputed.2023/11/2520CommitmentUsingaDiscreteLog(cont.)Ontheotherhand,theschemeisinformation-theoreticallyhiding,sincethedistributionofgrhbisstatisticallyindependentofthevalueofb.（相当于gr和gr’的分布是统计不可区分的）

r=r’概率为0，因为h不为1，所以x不为0Asacomplementarybitcommitmentscheme,onemayusethefollowingElGamal-likescheme:commit2(r,b)=(gr,hr+b),wherer

RZn.Thisschemeisinformation-theoreticallybinding,sinceitiseasilyseentherecannotevenexistr,r’

Znsuchthatcommit2(r,b)=commit2(r’,1-b),forb

{0,1}.即不能既作为0又作为1来打开承诺2023/11/2521CommitmentUsingaDiscreteLog(cont.)Ontheotherhand,thisschemeiscomputationallyhiding,sincebcanbecomputedasfollows.AssumingthattheDLproblemisfeasible,onemaycomputebfromagivencommitmentcommit2(r,b)=(x,y),usingtheformulab=loghy-loggx.Note,however,thattheDLassumptionisnotsufficienttoguaranteethattheschemeishiding.WeneedtousetheDDHassumptiontoensurethehidingproperty,assolvingforbgivencommit2(r,b)isequivalenttosolvingtheDDHproblem.Bothcommitmentschemesremainsecurewhenusedforb

Zninsteadofb

{0,1}

Zn.2023/11/2522ExampleExample:Analyzethesecuritypropertiesofcommit1andcommit2forthecasethatb

Zn.Solution:Thesamereasoningappliesasbefore,exceptthatforshowingthatcommit1iscomputationallybindingweneedamoregeneralargument.Supposethatitisfeasibletofindr,r’,b,b’withb

b’suchthatcommit1(r,b)=commit1(r’,b’).Thismeansthatgrhb=gr’hb’,hencethatloggh=(r–r’)/(b’-b).Sincer,r’,b,b’areallknown,thismeansthatthediscretelogofhwithrespecttogcanbecomputed,contradictingtheDLassumption.2023/11/2523ExampleExample:Whathappensifthereceiverknowslogghinschemecommit1?Samequestionforschemecommit2.Solution:Sinceschemecommit1isinformation-theoreticallyhiding,thevalueofthecommittedvaluebishiddenevenifthereceiverknowsloggh.Forschemecommit2,thereceiverisabletocomputethevalueofhb=y/xloggh,where(x=gr,y=hr+b)=commit2(r,b).Ifb

{0,1},thenhb

{1,h}andthevalueofbiseasilydetermined.Ifb

Znandnoadditionalinformationonbisknown,thencomputingbfromhbwillbeinfeasible(undertheDLassumption).2023/11/2524ExampleExample:Discussthesecurityofthefollowingcommitmentschemeforvaluesm

<g>:commit(r,m)=grm,wherer

RZn.Isitbinding?Isithiding?Solution:Theschemeisnotusefulasitisnotbinding.Letm’=mgr’,thencommit(r,m)=grm=gr-r’m’=commit(r–r’,m’).So,commitmentcommit(r,m)canbeopenedasacommitmenttoanymessagem’withm’=mgr’.Theschemeisinformation-theoreticallyhiding.Again:相当于gr和gr’的分布是统计不可区分的2023/11/2525ImpossibilityResultAnaturalquestioniswhetherthereexistsacommitmentschemewhichisbothinformation-theoreticallybindingandinformation-theoreticallyhiding.Thefollowinginformalargumentshowsthatsuchaschemecannotexist.Consideranybitcommitmentschemewhichisinformation-theoreticallybinding.Forsuchaschemetherecannotexistanyr,r’suchthatcommit(r,0)=commit(r’,1),becausethenthe(unlimitedpowerful)senderwouldbeabletocomputebothrandr’,andopenthecommitmentatitsliking.However,ifthesendercommitsto0,say,usingC=commit(r,0)forsomer,the(unlimitedpowerful)receiverwillnoticethattheredoesnotexistanyr’withC=commit(r’,1),hencethereceiverknowsthatthecommittedvaluemustbe0.2023/11/2526HomomorphicCommitmentsThebasicsecurityrequirementforacommitmentschemearethatismustbebindingandhiding.Anotherusefulpropertyofacommitmentschemeisthatitmaybehomomorphic.Wewillintroducethehomomorphicpropertybymeansofanexample.ConsiderPedersen’scommitmentscheme,givenbycommit1(r,x)=grhx,wherer

RZnandx

Zn.Thisschemeishomomorphicinthesensethat:commit1(r,x)commit1(r’,x’)=commit1(r+r’,x+x’),wherethemultiplicationontheleft-handsideisinthegroupGandtheadditionsontheright-handsideareinZn.So,theproductoftwocommitmentsisacommitmenttothesumofthecommittedvalues.Homomorphicpropertiesturnouttobeveryusefulforachievingsecuremultipartycomputation.2023/11/2527HomomorphicPropertyAsaconcreteexample,homomorphiccommitmentscanbeusedasabuildingblockforsecureelectionschemes:veryroughly,duringthevotingstage,votersputtheirvotesintohomomorphiccommitments,andduringthetallyingstage,thevotesarecountedbytakingtheproductofallcommitments).2023/11/2528ExampleLetm=pq.TheQuadraticResiduosity(QR)assumptionstatesthattheQRproblemisinfeasible.Example:Lety

Jmdenoteanon-quadraticresiduemodulom(e.g.,y=-1isanon-quadraticresiduemodulomwhenmisaBluminteger“p=q=3mod4”).Considerthefollowingbitcommitmentscheme:commit(r,b)=ybr2modm,wherer

RZm.Inwhatsenseistheschemebinding?Inwhatsenseistheschemehiding?Inwhatsenseistheschemehomomorphic?2023/11/2529CommitmentusingQuadraticResiduositySolution:Notethatb=0ifandonlyifcommit(r,b)isaquadraticresiduemodulom.Therefore,theschemeisinformation-theoreticallybindingandcomputationallyhiding(why??Animportantexercise).Thehomomorphicpropertyforthisschemeisgivenbycommit(r,b)commit(r’,b’)=commit(rr’,b

b’),hencetheproductoftwocommitmentsisacommitmenttotheXORofthecommittedvalues.Computationallyhiding:如果平方剩余问题可解，那么如果commnit(r,b)为平方剩余则b=0,否则b=1.Information-theoreticallybinding:ifthereexistsr1,r2,commit(r1,,1)=commit(r2,0),thenyr12=r22modn,theny=(r2r1-1)2(modn),itiscontradictiontothecondition.2023/11/2530ApplicationsCoinFlippingAuctionsZeroKnowledge2023/11/2531CoinFlippingbyTelephoneAliceandBobwanttomakesomedecisionbasedonarandomcoin--ifthecoinis“head”Alicegetstherightandifthecoinis“tail”,BobgetstherightAliceisinBeijingBobisinShanghai2023/11/2532UsingCommitmentProtocolAlicechoosearandombitbAlicesendtoBobhercommitmentblobBobguessthevalueofthebitAliceopentheBlobHeadifBobiswrongandtailifBobisright2023/11/2533CoinFlippingProtocol

AselectsrA

R0,1;Commitsto

rA

BsendsbitrB

R0,1CoinisrA

rBIfAdoesn’topen-resultis

IfA’sopeningisinvalid-resultis

2023/11/2534InteractiveProofSystemLetL

{0,1}*bealanguageOneparty,theProverP,wanttoconvincetheotherparty,VerifierVthat

X

LInourcase:bothpartiesarePPTM;exchangemessagesandflipcoinsProverPmayhavesomeextrainformationWAttheendoftheprotocolVerifierVstate

{accept,reject}ForagivenWtheinteractionbetweenVandPinducesadistributionofthetranscriptsProverPVerifierV

2023/11/2535WitnessProtectionProgramsAwitnessindistinguishableproofsystemforX

L

Proverp

VerifierVCompleteness:ifproverPhaswitnessW-canconstructeffectiveproofthatmakesverifierVaccept.Soundness:ifX

L

no

proverP*

cansucceedwithhighprobabilitytomakeverifier

Vaccept.WitnessIndistinguishability:foreveryV*andanywitnessesW1

and

W2:distributionsontranscriptsarecomputationallyindistinguishable.Nopolynomialtimetestcandistinguishthetwo2023/11/2536Example:HamiltonicityCommoninputgraphG=(V,E)ListhelanguageofgraphswithHamiltoniancyclesG=(V,E)

L

ifandonlyifthereisacycleC=(i1,i2,

in)coveringallnodesofVonceand(ij,ij+1)

E2023/11/2537Example:HamiltonicityCommoninputgraphG=(V,E)ListhelanguageofgraphswithHamiltoniancyclesWitness

W–aHamiltonianCycleC=(i1,i2,

in)Protocol:ProverP

selectsarandompermutation

ofthenodesCommitstotheadjacencymatrixof

(G)=(

(V),

(E))foreachentryseparatelyVerifier

V

selectsandsendsabitr

R0,1Ifr=0P

opensallthecommitmentsandsends

Ifr=1P

opensonlythecommitmentscorrespondingtoCentries(

(ij),

(ij+1))Verifier

V

acceptsif:r=0andcommittedgraphisomorphictoG

r=1anda