; TeX output 1991.03.14:1156 F5 ~I u>K`y p cmr10QuanltumBitCommitment tandCoinTEossingProto }cols$ I4K`y ff cmr10GillesBrassard=!", cmsy10 ="K`y 3 cmr10D#Cepartemen!tfd'informatiqueetdeR.O.EUniv!ersit#CefdeMontr#CealK5C.Pe.f6128succ.\A"#Mon!tr#Ceal,fQuebMecfI- 3 cmcsc10ICanadaH3C3J7+ȔClaudeCr32epfgeau=y vLabMoratoirefdeRec!herchefenInformatique(]Univ!ersit#CefdeParis-Sud@|aB^fatimen!tf490-991405fOrsa!yIFrance {<"V G cmbx101ZInrtro Oduction!+K`y cmr10Inthelate1960'saphysicist,StephenWiesner,hadtheideathattheuncertaintyprinciplecould bUVe?usedforcryptography(thoughhepublishedhisresultmuchlater[Wie83! ]).DHisideawasthatitwouldbUVepossibletotransmitthevUUaluesoftwopiecesofinformationusingbeamsofphotonsinaM]waythatwouldmakeonlyoneofthemreadableatthereceiver'schoUVosing.=lThisnotion,`whichhecalled\multiplexing"isremarkUUablysimilartothe\one-out-of-twoObliviousTransfer"tobUVereinventedmanyyearslater[EGL83%[].Adecadeafterhisoriginalinvention,7CharlesH.BennettandGilles`BrassardbroughtWiesner'sideabacktolifeinaJ- cmcsc10JCr32ypto'82talk.5 Subsequently,theyusedquantum1cryptographicprinciplestoimplementbasiccryptographicprotoUVcols,>suchassecretkeyexchangeandcoin ippingbytelephone[BB84 ].ITherehasbUVeenveryrecentlyrenewedinterestinquantumjcryptographybUVecauseaworkingprototypUVeofthequantumkeyexchangechannelhasbUVeensuccessfully builtattheIBMT. J.WatsonResearchLabUVoratory,YorktownHeights[BBBSS902`].In4recenttimes, theimpUVortanceofcryptographicprimitiveshasbUVeenbroughttolightbytheworkofmanyresearcherswhosegoalistocharacterizepreciselytheprimitivessucientfortheimplementationzofvUUariouscryptographicprotoUVcols. oOneoftheseprimitivesisaBitCommit-mentScheme.TheimpUVortanceandusefulnessofsuchaprimitiveisenlightenedbytheworkof[GMW86,,BCC88%\] tomentionjustafew.Whilesuchprimitivesareusuallybuiltundercomputationalcomplexityassumptions,?itissometimesppUVossibletobuildsuchthingsbasedonassumptionsofadierentnatureaspUVointedoutby^theworkmentionedearlierof[Wie83! ,BB84 ].7tThecurrentpapUVerpresentsthestate-of-the-artintheCctechnologyofbuildingabitcommitmentschemeonaquantummechanicalassumption.~Theapplications arenumerous,includingsecuretwo-partycomputation.֟ ff Q g^ O! cmsy7 K`y cmr10SuppGortedUUinpartbyCanadaNSERCgrantA4107. X^y SuppGortedinpartbyNSERCPostgraduateandPostdoGctorateScholarships.[ThisresearchwaspGerformedinpart whileUUtheauthorwasagraduatestudentatM.I.T.andwhilevisitingtheIBMAlmadenResearchCenter. 1 *F5 ~A9 Pcb"V cmbx10FigureT1:qTheUUbGehaviourofaphotonpassingthroughaW*allastonprism 2ZPhrysicsbackground!Foracompletecoverageofthephysicsofquantumcryptography,pleaseconsult[BB84 ]. The linearfpUVolarizationofphotonsisaquantumstate.kIngeneral,I?thevUUalueofthisvariablecannotbUVe}mdeterminedexactly.͝Accordingtoquantummechanics,althoughthevUUalueofthepUVolarizationcanQ_bUVeanyangleinthe(real)intervUUal[02K cmsy8,b> cmmi10;1802),onlyQ_abUVooleanQ_(twostates)predicatecanbUVemeasuredabUVoutthisvUUariable.ifMoreover,H\onlyonesuchmeasurementcanbUVeperformedonanygivenphotonbUVecausethemeasurementitselfnecessarilydestroystheinformation.>Forinstance,letpbUVethepolarizationofaphoton.Assumingthatitisknown. ': cmti10apriorithatiseither02 0or902,thepredicate\IsUR=02?";canbUVemeasuredaccuratelyforthesetwoquantumstates.;Ontheotherzfhand,evenifisknowntobUVeeither02:jor452,thennomeasuringapparatuscandistinguishbUVetween3thesetwo3stateswithcertainty,ҏalthough3someprobabilisticinformationcanbeobtained.IfwehavenoconstrainonthesetofpUVossiblevUUaluesforthenanswering\IsUR=02?"Cwillresultin| aprobabilisticanswerdeterminedbythevUUalueof:\itwillalwaysbUVe\yes"ifUR=02,qotherwiseit willbUVe\no"withaprobabilitythatrangesfrom0to1asrangesfrom02to902.Itisnotamatteroftechnology,itisnotthatnoonehasagoUVodenoughdevicetogureout;quantumtheoryclaimsthatitis0"V cmbx10impb"ossibletodeterminethisvUUaluewithcertainty.Inasense,the vUUaluedoUVesnotreallyexist:UUitisjustaprobabilitydistribution.However,iitispUVossibletobuildadevicethatalwayssays\yes"ifUR=02vandalwayssays\no"when"\=902.Ingeneral,+withsuchadevice,Prob(device says\yes"Y-!", cmsy10j)\=coso2 |{Y cmr82`s().ThiscanbUVeobtainedTbycombiningaWallastonprismwithtwophotomultipliers(photondetectors).9Seegure1.5>ConsideraWallastonprismsetfordistinguishingpUVolarizationangles'from'+902.AphotonpUVolarizedatanglewillcomeoutofthisWallastonprismontherightsidewithprobabilitycos22\( ')(andwillthenbUVerepolarizedatangle')andontheleftsidewithcomplementprobabilitysin'2D(0 ')(andwillthenbUVerepolarizedatangle'0+902).&Accordingtoquantummechanics, thisdeviceisthebUVestthatcanbebuiltwithrespecttomeasuring. 2 ֠F5 ~ 3ZReviewofearlierquanrtumproto Ocols!7"V ff cmbx103.1DAbitcommitmen=tschemeConsiderݛtwoparties:D"SLeandR #.IAssumethatShasabitbinmind,|towhichshewouldliketobUVe committedtowardR n.+LThatis,SGwishestoprovideR/Twithapieceofevidencethatshehasabitinmind)andthatshecannotchangeit.Meanwhile,4HRshouldnotbUVeabletotellfromthatevidencewhat bis.TherstquantumbitcommitmentschemeeverpropUVosedisduetoBennettandBrassard[BB84 ](actually,ytheaprotoUVcoltheydescribeisonlyclaimedtoimplementcointossing,ybutitisobvioushowtomoUVdifyitinordertoimplementbitcommitment).PLetusbrie yreviewthisprotoUVcolanditsMmainweaknessbUVeforedescribingournewschemeinSection4.AssumethatSwishestocommitto bitbtoward R+.UULet sbUVeasecurityparameter.[M֟҉ ffൠ [ [ ffӍҍ Protob"col3.1(BB-commit(b)) !f`1:2"$!", 3 cmsy10S=<8c!hoMosesfavector#b> 3 cmmi10BK= (bz1;1bz2;:::;bz2 cmmi8sn<)fofsrandombits !f`2:2"R?7c!hoMosesfavector =('z1;1'z2;:::;'zsn<)fofsrandom'zio2 f0;45g!f`3:|9s M2"'"V 3 cmbx10DO4`i=1HbST sendsfaphotonwithpMolarizationbn45.+bzi90fjthatfRreadsfatangle'zid.g- R9#setsfb0|io Cu cmex10C(.0#8ifphotoncameoutontherigh!t 1#8ifphotoncameoutontheleftH!f`4:2"R?7k!eepsfandB 0e= (b0g1;1b0g2;:::;b0Asn<)fsecret!f`5:2"S=<8k!eepsfbandB3 secretuntil(andif )decommittal [ ffff ffൎUMNoticethatsinceb̹i $gischosenatrandom,/pthereceivedbitb20RAi $grevealsnoinformationabUVoutb.%Therefore5receivingB !20 =R(b20RA1;b20RA2;:::;b20RAsn<)5revealsnothingabUVoutb.%Infact,lBamuchstrongerstatement0canbUVeproved:quantummechanicstellsusthatnomeasuringapparatuscandistinguishaJ`commitmentto0fromacommitmentto1unlessitispUVossibletocommunicateinformationfasterthan thespUVeedoflight.UUButwhyisS*committed?To opUVenhercommitment,S*initiatesthefollowingprotoUVcolwithR+.5֟˗Q ffൟb^ b^ ffїQחQ Protob"col3.2(BB-decommit((B !;b);(B20hZ;))) !f`1:2"S=<8rev!ealsfbandB3 toR !f`2:|9s M2"DO4`i=1HbRUԀc!hecksfthatb0|io= bzi@whenev!er'zi= bn45M!f`3:2"if2thisfconditionissatisedforallithenR outputs\accept"elseR outputs\reject" b^ ffff ffൎ/FirstnotethatifSOishonestthentheconditionisalwayssatised.,NowsuppUVosethatacheatingSxtriesto\commit"inawaythatwillenablehertoopUVenBwasborUp-*bZatherlaterchoice.IInorderto3achievethis,shemustndtwostringsB !20 0XandB !21suchthatB !2b 0satisestheconditionabUVovewhentryingtoopUVenasbX2f0;1g.(Thisimpliesthatb20RAi =Xb20RAi whenever'̹i=02 [andthatb21RAi =b20RAiwhenever '̹i,=UR452.WhenSbUVothSNandR.arehonest,(S*#knowsthatProbk(b̹i5=1b20RAid)=Fud3d콉 fe @'4v.OWhenSonlyRishonest,thevmaximuminformationthatShmaygetabUVouteachb20RAiۺisbysendingherbitsb̹iۺusingangle22Fu33133콉 fe @'2jIM#+b̹i!902,"whichgivesherProb5(b̹iC=ib20RAid)=cos|22T(22Fu33133콉 fe @'2jIMfn)85%(itisaneasyexercisetogureout8^thatthisisSc'soptimalstrategy).nStill,FuS{willalways8^haveaprobabilityofsin'2 (22Fu33133콉 fe @'2jIMfn)C15% 3 F5 ~ of guessingb20RAidincorrectly. NowZXforalltheindicesiwhereb20RAi=b21RAi,pShasatleastprobabilitysin'2(22Fu33133콉 fe @'2jIMfn)thatb20RAi6=b20RAi2andb21RAiD6='@b20RAid.6When}b20RAi6=b21RAi =it}isevenworsesinceoneofb20RAi =orb21RAiisnecessarilywrong.6BecauseS&hasno informationabUVout'̹id,(shehasnoinformationaboutwhichofb20RAiorb21RAisheshouldsetas0or1.ThereforevherprobabilityoffailureinthissecondcaseisFu,1,콉 fe @'2c.?Weconcludethattheprobabilityofsuccess thatS*buildssuchB̸0andB̸1isatmost(cos22(22Fu33133콉 fe @'2jIMfn))2sn<."ʨ3.2DCointossingBennettandBrassardusedthisbitcommitmentschemeinordertoimplementaprotoUVcolforcointossing by(quantum!)UU\telephone"[Blu81]asfollows:>֟ow ffൟu! u! ffoxow Protob"col3.3(BB-cointoss) !f`1:2"S=<8c!hoMosesfarandombitbz0fjandusesBB-commit(bz0)withR !f`2:2"R?7c!hoMosesfarandombitbz1fjandsendsittoS!f`3:2"S=<8runsfBB-decommit(bz0)withR!f`4:2"R?7winsfthecointossifandonlyifbz1ʫ= bz0 u! ffff ffൎ8The resultingprotoUVcolcanbebrokenexactlyifthebitcommitmentschemecanbUVebroken.3.3DTheproblemofdepuendenceAsJmentionedin[BB84 ]thebitcommitmentschemeofsection3.1andtheresultingcointossingprotoUVcolcanbedefeatedintheoryusingtheconsequencesoftheEinstein-Podolsky-Rosen\para-dox". hxThe[interestedreadercanconsulttheirpapUVerforamoredetailedexplanation. hxWecallthisp@problem\depUVendence"becauseE-P-Rp#isbasedonthefactthatitispossibletocreatepairsof[photonswithadepUVendencerelationbetween[theirpolarizations(itispossibletohave[somecorrelation4_bUVetweenmeasurements).rInpractice,AwthiskindofattackisratherimprobablebUVecausetheCtechnologynecessarytopUVerformitisfarbeyondthecurrentavUUailabletechnology,andbUVecauseeven-asmallfailureinthecheater'stechnologywillresultinlossofhispUVossibilityofcheating.Nevertheless, fromatheoreticalpUVointofview,itisimpUVortanttogetaroundthisdiculty.Inthenextsectionweoerournewbitcommitmentscheme,wwhichcannotbUVebrokenthroughE-P-R. 4 2TF5 ~ 4ZAnewbitcommitmenrtscheme!4.1DHo=wtocommitIn ordertocommittoabitb,S*buildsarandomss bUVooleanmatrix: $ Bs=fVURC0URB URBfiUR@ٍSb̸1;1+5...C3b̸1;sG . .. ,B.0퉟 .53 . J. J.J.>7b̹s;1+5...Cb̹s;sfVXMC1XMC XMCfiXMA\(1)%$with thefollowingpropUVerty:qʍ 81URis [s CM,jv=1sb̹i;j=b]\(2)jand sendsittoR+usingthefollowingprotoUVcol._w֟ ffൠ " " ff Protob"col4.1(BC-commit(b)) !f`1:2"S=<8buildsfarandomsnsfbMooleanmatrixB3 asindicatedabo!ve !f`2:|9s M2"DO4`i=1|Lйs ME?DOGmjv=1\ESgdc!hoMosesfarandom'zi;j2 f0;145gfandRchoMosesarandom'zi;j2 f0;145gwߍ!f`3:|9s M2"DO4`i=1|Lйs ME?DOGmjv=1\ESgdsendsfaphotonwithpMolarization'zi;jD+nbzi;j90fjthatfRreadsfatangle'zi;j X.?- R9#setsfb0|i;j C(.0#8ifphotoncameoutontherigh!t 1#8ifphotoncameoutontheleftH!f`4:2"R?7k!eepsfB 0Cand(seebMelow)secret!f`5:2"S=<8k!eepsfb,B3 and(seebMelow)secretuntil(andif )decommittal " ffff ffൎYwwhere'p2B !0=fVURC0URB URBfiUR@0Sb20RA1;1+5...C3b20RA1;s . .. ,B.0퉟 .53 . J. J.J.>7b20RAs;1+5...Cb20RAs;sfVXMC1XMC XMCfiXMAcL;UR=fVC0B Bfi@ٍS̸1;1,...D̸1;sG . .. ,.1iE .6 . J. J.J.>7̹s;1,...D<̹s;sfVYC1YC YCfiYAd;=fVC0B Bfi@ٍS'̸1;1.Ki...FKg'̸1;sG . .. ..3 .8Kg . N. N.N.>7'̹s;1.Ki...FtK'̹s;sfV^/C1^/C ^/Cfi^/A\(3)*^If bUVothparticipantsarehonest,B !20hZissuchthat X/81URis;1j,s [Prob(b̹i;j=b0ڍi;j X)=ō3Qm fe 4]\(4)UHowever,nifXR8usesXangle'̹i;j=t22Fu33133콉 fe @'2jIMhewillendupgettingmaximuminformationabUVoutB !.Thatis81URis;1j,s [Prob(b̹i;j=b20RAi;j X)=cosfe22&i(22Fu33133콉 fe @'2jIMfn)].Nevertheless,#eventhenthematrixB !20revealsverylittleabUVoutb.9WemeasurethisfactbycomputingProb5(bUR=0jB !20hZ)andProb5(b=1jB !20hZ)for everypUVossibleB !20hZ.UUWearesatisedifthereexistsapositiveconstant`<UR1suchthat jProb(bUR=0jB !0hZ) Prob35(bUR=1jB !0)j_sforaeveryB !20hZ.{SinceProbv(b=0jB !20)+Probt{(b=1jB !20)=1,zdtheafollowingconditionissucientfor this result:xTheorem4.1CyTherbeKexistsapositiveconstant`<UR1suchthatō U1 UQm fe 2 1 _sURProb(bUR=0jB !0hZ)ō1Qm fe 2fa+_s 5 ?eF5 ~ Prboof. Provided inthejournalversionofthepapUVer.UU3Tq lasy102Lemma4.2Fu;P1;P콉 fe @'2Cm s(2p 1)2sÎURProb(bjB !20hZ)URFu1콉 fe @'2d+s(2p 1)2s>Prboof. Let B̹idandB2 !0RAihZbUVethei2thwlineofB!andB !20hZ.UULetb̹i,=os URCMJjv=1qb̹i;j Xanddeneb20RAisimilarly.^UProbx%(bjB !0hZ) yr=ō Prob Ί(B !20hZjb)Prob(b) Qm fe _f@Prob1Ȑ(B !0hZ)\(5) Yy yr=ō GProb(B !20hZjb)Prob(b) Qm fe ks.Prob(b)Prob(B !0hZjb)+Prob35(U3*b&f)Prob(B !0jU3*b)\(6) } yr=ō E^Prob (B !20hZjb) Qm fe ~b.Prob(B !0hZjb)+Prob35(B !0jU3*b&f)\(7);8 yrsince Prob hi(b)UR=Prob(U3*b&f)=ō1Qm fe 24 yr=ō \1 Qm fe Fh"1+fhProbfh(Bdq% cmsy60j㎍lrbܸ)۟ʉ fe /ZProb(Bd0jb)\(8)$\HNow wefoUVcusourattentiononthisratio:ҍōXhProbq;(B !20hZjU3*b&f)XhQm fe 7Prob(B !0hZjb) w=ō Prob ɉ(B !20^U=*b) Qm fe AProb(B !0^b)\(9).ȍ w=wy CX"% NB rOProb (B !0^BD^U=*b) fe iWu32CX"%ƹBqProb)T(B !0^BD^b)\(10)@LЍ w=; ˑݟCX ]ፒ BdjbqAa cmr61*=bq2=:::=b ; cmmi6sǸ=㎍lrb Prob(B !0^B !) u fe h32UCXBdjbq1*=bq2=:::=b sǸ=bGqProba(B !0^B !)\(11)BY w=; ĜICX ]ፒ B8:i,rjb8:i=㎍lrb;1is Prob2](B !0ڍ1j^B̸1^:::^B !0ڍs^B̹sn<) u fe ҡ32CXB8:i,rjb8:i=b;1is9HProbS1(B !0ڍ1j^B̸1^:::^B !0ڍs^B̹sn<)\(12) w=; ĜICX ]ፒ B8:i,rjb8:i=㎍lrb;1is Prob2](B !0ڍ1j^B̸1):::Prob(B !0ڍs^B̹sn<) u fe 32CXB8:i,rjb8:i=b;1is9HProbS1(B !0ڍ1j^B̸1):::Prob(B !0ڍs^B̹sn<)\(13)(fh wsince theseevents areallindepUVendent) w= s JqCY Ui=1; ^CX ]ፒ ܹB8:i,rjb8:i=㎍lrb ¦Prob K3(B !0ڍi^B̹id) ܟu fe h5z32GCXB8:i,rjb8:i=b Prob8W(B !0ڍi^B̹id)\(14) w= s JqCY Ui=1; ^CX ]ፒ ܹB8:i,rjb8:i=㎍lrb ¦Prob K3(B !0ڍihZjB̹id) ܟu fe ^532GCXB8:i,rjb8:i=b Prob8W(B !0ڍihZjB̹id)\(15) 6 RvF5 ~ but thisratiois /F;3CX ]ፑ+ɒB8:i,rjb8:i=㎍lrbJ\ProbdR(B !0ڍihZjB̹id)+ɒu fe ^532GCXB8:i,rjb8:i=b Prob8W(B !0ڍihZjB̹id) 2D= C8 > > > < > > > :fh ]Prob &(anfev!ennumbMeroferrorsoccurred 1) ]ʉ fe 6DProb4Ѹ(anfoMddn!umberfoferrorsoccurred s)if b20RAi,=U*URbnnfh JProb .(anfoMddn!umberfoferrorsoccurred s) ]ʉ fe 6Prob(anfev!ennumbMeroferrorsoccurred 1)if b20RAi,=URb\(16)8r 2D= f\C ō QProb K(anfoMddn!umberfoferrorsoccurred s) zQm fe ǪProb(anfev!ennumbMeroferrorsoccurred 1)zf\C!mm*( 1)b{q0:i,rb\(17)B 2D=fL C0 B B B B B B Bfi @ύ㊍ zϟ b Xs 1 X fe p2 * cv D7CX ٹjv=0 ff\C ō sYy j2jZ+1 f\C! Sps 2jv 1 >(1 p)2jv+1 zϟc fe ~O㊍@ b s9s ^ɟx| fe 2%< cv8CXڹjv=0,f\C ō7}sYy4|2j@f\C!H