资源描述：
《can alice and bob be random a study on human playing zero knowledge protocols》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、CanAliceandBobberandom:astudyonhumanplayingzeroknowledgeprotocols.KAMILKULESZA1DepartmentofAppliedMathematicsandTheoreticalPhysics,UniversityofCambridge,Cambridge,UK,InstituteofFundamentalTechnologicalResearch,PolishAcademyofSciences,Warsaw,Poland,e-mails:K.Kulesza@damtp.cam.ac.uk,Kamil.Ku
2、lesza@ippt.gov.plExtendedabstract.TheresearchdescribedinthisabstractwasinitiatedbydiscussionsbetweentheauthorandGiovanniDiCrescenzoinBarcelonainearly2004.ItwasduringAdvancedCourseonContemporaryCryptologythatDiCrescenzogaveacourseonzeroknowledgeprotocols(ZKP),see[1].Afterthatcoursewestarted
3、toplaywithunorthodoxideasforbreakingZKP,especiallyonebasedongraph3-coloring.Itwaschosenforinvestigationbecauseitisbeingconsideredasa“benchmark”ZKP,see[2],[3].Atthispointwebrieflyrecallsuchaprotocol’sdescription.Graph3-coloring(3COL)basedZKPInput:graphGAlice(Prover)wantstoprovetoBob(Verifie
4、r)sheknowsassignmentofcolorsfromtheset{1,2,3},suchthatitisapropervertex3-coloringofG.Inaddition,letm=E.Oneroundoftheprotocol:1.Alicefindsarandompermutationϕoftheset{1,2,3},whichsheappliestothecoloringofG.Alicecommitsseparatelytocoloringofeachvertexandsendscommitmentstogetherwiththemappingi
5、ntoG’sverticestoBob.2.BobselectsatrandomanedgefromGandsendstoittoAlice.3.AlicerespondswithopeningcommitmentsattheendsoftheedgeselectedbyBob.4.Bobcheckswhethertheverticesattheendsoftheedgehavedifferentcolorsfromtheset{1,2,3}.IfresultispositiveBobacceptstheroundoftheprotocol,otherwisewholepr
6、otocolisterminatedanditsresultisnegative.2Theprotocolisexecutedformrounds.Discussion.IfAliceknows3-coloringofG,shecanconvinceBobineveryroundoftheprotocol.Ifshe1doesnotknow3-coloring,sheconvincesBobwithprobability1−,sinceforeveryroundmthatmustbeatleastoneedgethatverticeshavesamecolor(oroneo
7、fthecolorsisfrom2outsidetheset{1,2,3}).AftermroundsprobabilityofAliceconvincingBobism2⎛1⎞−m⎜1−⎟≈e.Graph3-coloringZKPisacomputationalzero-knowledgeproof,see[4].<⎝m⎠AZKPisusuallyperformedbetweenthemachines.Oneofinterestingquestionsiswhathappensifahumanismadepart
