[硕士论文精品]密码算法与协议简化设计

山东大学博士学位论文密码算法与协议简化设计魏普文山东大学数学学院密码技术与信息安全教育部重点实验室摘要从古至今，密码设计者与密码分析者之间的竞争从未停止过。特别是自二战以来电子计算机的产生从根本上增强了双方的实力，使竞争进一步升级。考虑到计算能力的限制，人们更加关心破解一个密码方案需要多长时间，或者说，一个密码方案究竟有多安全。在现代密码学中，一种被称为安全性证明的方法通过使用严格的数学工具来度量密码方案的安全性，提高人们对该方案安全性的信心。虽然安全性证明为密码设计者在与分析者之间的竞争中赢得了优势，但是，效率与安全性证明之间此消彼长的关系又成为密码设计的一个不利因素。为了提供严格的安全证明，通常将冗余信息添加到密码方案的设计中，致使密码方案的运行效率降低。因此，密码设计的一个基本问题是如何在不降低安全性的前提下，简化方案设计，提高运行效率。为了解决该问题，密码学家在过去的几十年里相继提出各种设计简化技术。在本论文中，我们主要探讨公钥加密，数字签名与零知识这三个领域的简化设计技术。公钥加密公钥密码学最早FLTDIFTIE和HELLMAN42提出。随后，RIVEST，SHAMIR和ADLEMAN82】与MERKLE和HELLMANL69分别给出了具体的公钥加密方案。但是广泛使用的加密安全概念一选择密文安全则是NAOR和YUNG75】提出的。此后，RACKOFF乘LSIMONS0提出了更强的安全概念一自适应选择密文攻击下的不可区分性ENDCCA2。现在，自适应选择密文安全已经成为证明公钥加密方案安全性的标准概念。早期的自适应选择密文安全的加密方案，例如，文献【州，因为基于非交互零知识证明，所以相应的构造方案并不实用。为了构造有效且自适应选择密文安全的加密方案，随机谕示模型下的加密技术大量涌现【15】【48】【L41。然QQ个性签名HTTP/WWWQQOOKCOM山东大学博士学位论文而，随机谕示模型却是密码学界备受争议的问题之一。其中以CANETTI，GOLDREICH与HALEVI25】的反对观点最为著名。他们指出存在这样的方案在随机谕示模型下，这些方案可以被证明是安全的，而在随机谕示实例化后却是不安全的。近来，LEURENT与NGUYENL67】证明了现有满域HASH函数随机谕示实例化后潜在的不安全性。为了解决因随机谕示的引入而带来的问题，一个直接的方法是设计安全性证明上不依赖于随机谕示的自适应选择密文安全的公钥加密方案。在该方向的研究中，CRAMER和SHOUP35提出了第一个标准模型下自适应选择密文安全且实用的加密方案。此后，该方案被频繁引用，更多有关技术相继提出。其中，CRAMER和SHOUP89】【36】提出的混杂加密KEMDEM引起了密码学界的广泛关注。其中，KUROSAWA和DESMEDTT661通过使用非自适应选择密文安全的KEM构造出更为有效的混杂加密方案。近年来，KILTZ，PIETRZAK，STAM和YUNG【鲫改进了KUROSAWADESMEDT技术，提出了一种新的非随机谕示模型下自适应选择密文安全的混杂加密方案。其主要技术是通过使用4WISEINDEPENDENTHASH函数有效的将1UNIVERSALHASH证明系统转化为2UNIVERSALHASH证明系统。另一项重要的研究进展是HOFHEINZ和瞄HZ【删做出的。在标准模型下，HOFHEINZ乖IKILTZ设计的基于因子分解的公钥加密方案对于加密仅需要约两次幂运算，而解密需要约一次幂运算。但关于非随机谕示模型下基于离散对数问题的加密方案，DHIES2】当属最为有效的方案之一，尽管其安全性证明依赖的是非标准假设。然而，标准模型或标准假设下的加密方案都有一个共同的弱点其计算量往往是随机谕示模型下同类方案的几倍，从而严重影响方案在实际中的应用。相反，随机谕示模型下方案的优点正在于其简单的设计与低廉的计算消耗。为了保持这种简单性的同时使安全性证明不依赖于随机谕示，密码研究人员已经开始探讨新的计算困难假设。最近，PANDEY，PASS和VAIKUNTANATHAN77通过抽象随机谕示的具体性质，提出了多种复杂性理论新假设。基于这些假设，他们成功的解决了一系列公开问题，其中包括构造非交互式并发不可延展的串委托协议。这些研究成果为设计无随机谕示模型下有效而可证安全的密码方案指出了一个有趣的方向。我们注意到，尽管这些新假设强于传统密码学困难性假设，但是仍然不失合理性。类似于DDH假设的发展，此类假设将会得到密码学界更加广泛的认同与深入的探讨。山东大学博士学位论文通过抽象随机谕示的具体性质，我们进步研究TPANDCY等人的假设并提出了其变形假设一自适应DDH假设。在该假设基础上，我们证明了修改后的ZHENGSEBERRY力I密方案在无随机谕示模型下是自适应选择密文安全的。ZHENG和SEBERRY991提出三种使公钥加密抵抗选择密文攻击的方案。三种方案的本质是相同的对密文附加一个与明文相关的标签。基于GAPDIFLIEHELLMAN假设GDH，BAEKJIZHENG7在随机谕示模型下证明了第一个方案ZHENGSEBERRYLWH的安全性。而另外两个方案的安全性证明一直作为公开问题存留至今。我们工作的重点是适当修改ZHENGSEBERRY的第二个方案ZHENGSEBERRYLIJL，从而可以利用自适应DDH假设证明其自适应选择密文安全。ZHENGSEBERRY砌方案至今仍然具有研究价值，这是因为第一，ZHENGSEBERRY曲通过使用UNIVERSALHASH函数使其能够抵抗自适应选择密文攻击，同时避免了使用非标准输出的单向HASH函数，从而成功的克服了【67】所指出的潜在危险。第二，明文长度是任意的，而密文冗余是常数。所以，当明文长度增加时，密文明文长度的比值将趋于1。与飚LTZ等人的方案【64】其安全性依赖于DDH和AEOT安全对称加密相比，修改后的ZHENGSEBERRYLIJL方案在设计上更为简单且只依赖于自适应DDH。更重要的是，修改后的ZHENGSEBERRYUH计算量低于LILTZ等人的方案。与DHIES其安全性依赖于ORACLEDIFLIEHELLMANODH，对称密码和消息认证码相比，修改后的ZHENGSEBERRYUH安全性依赖于自适应DDH且同样保留TZHENGSEBERRY|LJL计算上的有效性。但是，公平的说，DHIES与修改后的ZHENGSEBERRYHH在安全假设方面各有千秋。DHIES安全性依赖于三个假设一对称密码，MAC和ODH，实现符合这三种假设的候选函数相对容易。而我们的方案所依赖的自适应DDH假设则稍强于ODH假设。环签名公钥签名的概念最早由DIFFIE和HELLMAN42提出，而早期具体的实现方案则是RIVEST，SHAMIR和ADLEMANT821提出的。关于数字签名安全性的相关概念，文献【56】做出了全面深入的讨论。众所周知，签名的目的是提供对消息来源的认证，同时保证消息在传送过程中未被修改。然而在某些应用中，我们需要隐藏签名者的身份。正是由于这种实际需求，数字签名中出现了群签名与环签名的概念。环签名最早由RIVEST，SHAMIR和TAUMAN83L提出，目的是为签名者提供匿名性。但是与群签名不同，环QQ个性签名HTTP/WWWQQOOKCOM山东大学博士学位论文签名中没有群管理员，不需预设群成员，不需进行群成员的设置、删除等操作。关于环签名的许多工作随后相继被提出，例如【4】、【581、【20】、【43】等。大部分环签名方案是在随机谕示模型下证明安全的。部分方案给出了标准模型下的证明，但是，这些方案也存在一些不尽如人意的地方XU，ZHANG禾JFENG94J给出一种标准模型下的环签名方案，然而其证明存在缺陷；CHOW，LIU，WEI和YUEN的方案32】基于新的假设；BENDER，KATZ和MORSEUI的方案【17】基于陷门置换，但是他们的方案因为使用了针对NP的一般性ZAPS，故其方案并不实用。不过，IT71对环签名的安全模型做出了细致且全面的讨论。近年来，SHACHAM和WATERS87】与BOYEN2L】分别提出了无随机谕示的有效环签名方案。特别是文献【87】中，SHACHAMWATERS方案是第一个基于标准假设的无随机谕示下的有效环签名。具体来说，在公共随机串模型下，基于计算DIFFIEHELLMAN假设和子群判定假设，SHACHAM矛HWATERS构造出线性大小的环签名。对于具有Z个成员的环，签名大小为2Z2个群元素，而验证则需要2ZAM配对运算。并且，方案的安全性是在BENDER,KATZ币HMORSELLI17】所提出的最强环签名安全模型下证明的。当考虑具体的应用环境时，我们指出，基于【43】的基本思想，SHACHAMWATERS环签名方案【87】可以更为有效的使用。在文献【43】中，DODIS，KIAYIAS，NICOLOSI和SHOUP通过使用单向域累加器引入环签名的群公钥的概念环中任何成员都可以计算该群公钥。这种构造方法使一个群公钥对应多个环成员的密钥。正是由于该群公钥，他们指出在某些特殊情况下，例如，环成员在较长时间内保持不变，环签名的大小可以为常数。我们注意至LJSHACHAMWATERS方案同样可以生成“群公钥”，且该群公钥能够成为提供可链接性的标签，所以我们进一步将DODIS等人的构造方法应用于SHACHAMWATERS方案。可以考虑以下应用环境，签名者A需要长时间作为某个环的成员，并且，A需要经常发送她的环签名给接受者B，同时让B确信他每次所收到的签名全部由环中某个固定的成员签署。对于以上应用环境，我们改造后的SHACHAMWATERS方案比传统的无随机谕示环签名方案更为有效。因为在该方案中签名者可以决定是否提供可链接性，所以我们将这种特殊的SHACHAMWATER方案称为自主可链接的环签名。并发统计零知识论据GOLDWASSER，MICALI和RACKOFFT55】提出的零知识证明山东大学博士学位论文是一种交互式证明方法。在该证明中，一方可以向另一方证明个命题为真，同时不泄露任何其他信息。提供证明的一方被称为证明者，而验证证明的一方被称为验证者。不像传统数学证明中证明者提供固定的一系列共同认可的证据，零知识证明更加强调证明者与验证者之间的交互。并发零知识的概念最早由DWORK，NAOR和SAHAI45】提出。并发零知识要求即使协议的多个证明复本在异步环境例如，因特网下运行，协议仍然保持零知识性。CANETTI，KILIAN，PETRANK和ROSENL26J证明了在标准模型不使用公钥基础设施P下，BPP之外的语言不存在常数轮的黑箱并发零知识证明协议，同时对此类协议他们给出了一个轮数下界O109NLOGLOG咒。RICHARDSON与KILIANL81】第一次对于所有NP语言给出了并发零知识证明协议，并且指出多项式轮数对于并发零知识协议是足够的。随后，PRABHAKARAN，ROSEN和SAHAIT78】改进了之前的分析并证明OD109N轮已经足够。正如MICCIANCIO和PETRANK71】所指出的，尽管标准模型下的并发零知识协议不如PKI模型下的协议有效，但是标准模型可以应用在无PKI的环境，或设置公钥基础设施与公共随机串。例如，标准模型的协议可以用来向证书授权方注册公钥和引导系统。在DDH假设下，MICCIANCIO和PETRANK7L】提供了一种可以将任何公开抛币的诚实验证者零知识证明系统HVZK有效的转化为并发零知识证明系统的方法。但是，他们的转化并不保持统计零知识性。最近，GOYAL，MORIARTY，OSTROVSKY和SAHAIE57】第一次利用任意单向函数构造出针对所有NP语言的并发统计零知识论据。具体来说，他们给出了从任意诚实验证者统计零知识论据到并发统计零知识论据的一般转化方法，再将该转化应用于NGUYEN，ONG和VADHAN的统计零知识论据协议，从而得到由任意单向函数构造的针对所有NP语言的并发统计零知识论据。GOYAL等人使用了修改后的PRS前导【78】，且该前导需要02个委托其中Z表示前导的轮数。协议中，验证者采用了计算零知识证明和抛币协议产生的随机数。关于安全证明，GOYAL等人所克服的最困难的问题在于合理性证明。因为验证者所使用的委托是统计绑定的计算隐藏，证明者可能会趁机欺骗验证者，因此，合理性证明并非显然。但是，通过使用计算零知识证明和混杂论据的讨论方法，GOYAL等人成功克服了这一难题。通过进一步分析GOYAL等人的并发统计零知识论据协议【571，我们指出，利用证据不可区分协议，协议【57】可以进一步简化为更加实际的方案。具体来QQ个性签名HTTP/WWWQQOOKCOM山东大学博士学位论文说，GOYAL等人协议中的部分计算零知识证明可以用EOR协议证据不可区分知识证明WIPOK替代，而WLPOK协议足以用来证明并发统计零知识论据协议的合理性。并且，我们利用RICHARDSON和KILIAN的前导81】替代PRS前导，从而将委托个数降为DD。这些以“并行”方式运行的WLPOK不但起到前导的作用而且移除TGOYAL等人协议中的部分计算零知识证明。此外，因为WIPOK协议并非零知识的，所以简化后协议的合理性证明要比原协议的合理性证明更加微妙。关键词公钥密码学，加密，签名，零知识ABSTRACTSIMPLIFIEDDESIGNFORCRYPTOGRAPHICALGORITHMSANDPROTOCOLSWEIPUWENKEYLABORATORYOFCRYPTOLOGICTECHNOLOGYINFORMATIONSECURITY,MINISTRYOFEDUCATIONSCHOOLOFMATHEMATICS，SHANDONGUNIVERSITY,JINAN250100，ERCHINAABSTRACTTHECOMPETITIONBETWEENCRYPTOGRAPHICSCHEMEDESIGNERSANDCRYPTANALYSTSHASNEVERSTOPPEDSINCETHEANCIENTTIMESESPECIALLY,THEADVENTOFELECTRONICCOMPUTERSSINCEWORLDWARIIHASFUNDAMENTALLYINCREASEDTHEPOWEROFTHETWOBELLIGERENTSANDESCALATEDTHECOMPETITIONVQLENCONSIDERINGTHECOMPUTATIONALPOWER,PEOPLECAREMOREABOUTHOWLONGITTAKESTOBREAKACRYPTOGRAPHICSCHEMEORHOWSECUREACRYPTOGRAPHICSCHEMEISINMODEMCRYPTOGRAPHY,ONEAPPROACH，CALLEDSECURITYPROOF,ISAPPLIEDTOMEASURETHESECURITYOFASCHEMEUSINGRIGOROUSMATHEMATICALTOOLS，ANDITAIMSTOPROVIDEPEOPLECONFIDENCEFORTHERESULTINGSCHEMESECURITYPROOFGIVESDESIGNERSTHEADVANTAGEINTHEWAROFMODEMCRYPTOGRAPHYAGAINSTCRYPTANALYSTSBUTTHEBADNEWSFORTHEDESIGNERISTHETRADEOFFBETWEENTHEEFFICIENCYANDTHESECURITYPROOFGENERALLY,INORDERTOPROVIDESECURITYPROOF,ADDITIONALREDUNDANCYHASTOBEADDEDINTOCRYPTOGRAPHICSCHEMESWHICHRESULTSINEFFICIENCYLOSSTHEREFORE，ABASICPROBLEMINTHEDESIGNOFCRYPTOGRAPHYISHOWTOSIMPLIFYACRYPTOGRAPHICSCHEMETOIMPROVEITSEFFICIENCYWITHOUTUNDERMININGITSDESIREDSECURITYTOSOLVETHISPROBLEM，DIFFERENTTYPESOFTECHNIQUESFORSIMPLIFIEDDESIGNHAVEBEENPROVIDEDDURINGTHEPASTDECADESINTHISTHESIS，WEFOCUSOILTHESIMPLIFICATIONOFTHREESCHEMESINPUBLICKEYENCRYPTION，DIGITALSIGNATUREANDZEROKNOWLEDGEPUBLICKEYENCRYPTIONPUBLICKEYCRYPTOGRAPHYWASFIRSTINTRODUCEDBYDIFFIEANDHELLMAN【421THEFIRSTCONCRETEPUBLICKEYENCRYPTIONSCHEMESWERELATERPROPOSEDBYRIVEST，SHAMIRANDADLEMANT821ANDBYMERLDEANDHELLMANT69BUTTHEMOSTQQ个性签名HTTP/WWWQQOOKCOMABSTRACTWIDELYUSEDSECURITYNOTIONFORENCRYPTION，KNOWNASCHOSENCIPHERTEXTSECURITY,WASINTRODUCEDBYNAORANDYUNGT751AFTERWARDSRACKOFFANDSIMONT80PROVIDEDASTRONGERNOTIONCALLEDINDISTINGUISHABILITYUNDERADAPTIVECHOSENCIPHERTEXTATTACKINDCCA2SOFARADAPTIVECHOSENCIPHERTEXTSECURITYHASBECOMEASTANDARDNOTIONFORTHESECURITYOFPUBHCKEYENCRYPTIONTHEEARLYCONSTRUCTIONSOFADAPTIVECHOSENCIPHERTEXTSECUREENCRYPTION，SUCHAS，WEREBASEDONNONINTERACTIVEZEROKNOWLEDGEPROOFSWHICHARENOTQUITEPRACTICALINREALWORLDAPPLICATIONSTOCONSTRUCTALLEFFICIENTANDADAPTIVECHOSENCIPHERTEXTSECUREENCRYPTIONSCHEME，MANYENCRYPTIONTECHNIQUESHAVEBEENPROPOSEDINTHESOCALLEDRANDOMORACLEMODELTL5】【48】【141THERANDOMORACLEMODELHOWEVER,ISONEOFTHEMOSTCONTROVERSIALISSUESINCRYPTOGRAPHYANOTABLEARGUMENTAGAINSTTHERANDOMORACLEMODELWASMADEBYCANERIGOLDREICHANDHALEVI【25】WHODEMONSTRATEDTHATTHEREEXISTEDCRYPTOGRAPHICSCHEMESTHATWERESECUREINTHERANDOMORACLEMODELBUTINSECUREFORANYINSTANTIATIONOFMERANDOMORACLERECENTLY,LEURENTANDNGUYENT67】SHOWEDTHATINSTANTIATIONSOFFULLDOMAINHASHFUNCTIONSRANDOMORACLESPROPOSEDINTHELITERATUREAREINSECURETOADDRESSTHECONCERNOVERRANDOMORACLES，ANOBVIOUSAPPROACHISTODESIGNANADAPTIVECHOSENCIPHERTEXTSECUREPUBLICKEYENCRYPTIONSCHEMETHATDOESNOTRELYONARANDOMORACLETHEOFTENCITEDADAPTIVECHOSENCIPHERTEXTSECUREENCRYPTIONSCHEMEPROPOSEDBYCRAMERANDSHOUPT35】REPRESENTSTHEFIRSTCONCRETERESULTINTHISLINEOFRESEARCHAMULTIPLENUMBEROFTECHNIQUESHAVESINCEBEENPROPOSEDANDSTUDIEDBYMANYCRYPTOGRAPHERSESPECIALLY,THEHYBRIDENCRYPTIONKEMDEM，WHICHWASFIRSTGENERALIZEDBYCRAMERANDSHOUPT8911361ATTRACTSALOTOFARENTIONFROMTHECRYPTOGRAPHYCOMMUNITYKUROSAWAANDDESMEDTT66PRESENTEDAMOREEFFICIENTHYBRIDENCRYPTIONSCHEMEBYUSINGAKEMWHICHISNOTNECESSARILYADAPTIVECHOSENCIPHERTEXTSECUREMORERECENFLYKILTZ，PIETRZAK，STAMANDYUNG【删IMPROVEDONTHEKUROSAWADESMEDTTECHNIQUEANDPROPOSEDANEWAPPROACHTODESIGNADAPTIVECHOSENCIPHERTEXTSECUREHYBRIDENCRYPTIONSCHEMESWITHOUTARANDOMORACLETHEIRMAINTECHNIQUEEMPLOYSANEFFICIENTTRANSFORMATIONFROMA1UNIVERSALHASHPROOFSYSTEMTOA2UNIVERSALHASHPROOFSYSTEM，USINGA4WISEINDEPENDENTHASHFUNCTIONANOTHERABS。I。RACTIMPORTANTPROGRESSWASMADEBYHOFHEINZANDKILTZ160THEYPROPOSEDANEWPUBLICKEYENCRYPTIONSCHEMEBASEDONFACTORINGTHEIRSCHEMEREQUIRESONLYROUGHLYTWOEXPONENTIATIONSINENCRYPFIONANDROUGHLYONEEXPONENTIATIONINDECRYPTIONFORTHEENCRYPTIONSCHEMESBASEDONDISCRETELOGARITHM，DHIES2】ISONEOFTHEMOSTEFLICIENTSCHEMESWITHOUTRANDOMORACLE，ALTHOUGHITISNOTPROVENUNDERTHESTANDARDASSUMPTIONNOTICETHATMOSTOFTHESEENCRYPTIONSCHEMESINTHESTANDARDMODELORSTAILDARDASSUMPTIONS，HOWEVELSHAREACOMMONDRAWBACKTHATIMPEDESTHEIRPOSSIBLEADOPTIONINPRACTICE，THATIS，THEYGENERALLYREQUIREATLEASTAFEWTIMESMORECOMPUTATIONTHANTHEIRRANDOMORACLEBASEDCOUNTERPARTSAMAJORADVANTAGEOFARANDOMORACLEBASEDSCHEMELIESINITSSIMPLICITYTOPRESERVETHESIMPLICITYWHILENOTRELYINGONARAILDOMORACLEFORSECURITYPROOFS，NEWCOMPUTATIONALASSUMPTIONSHAVEBEENEXAMINEDONESUCHEFFORTISMADEBYPANDEY,PASSANDVAIKUNTANATHANT771WHOINTRDDUCEDAF色WCOMPLEXITYTHEORETICALHARDNESSASSUMPTIONSTHATABSTRACTOUTCONCRETEPROPERTIESOFARANDOMORACLEBASEDONTHESEASSUMPTIONS，THEYAREABLETOSOLVEANUMBEROFOPENPROBLEMS，INCLUDINGTHECONSTRUCTIONOFANONINTERACTIVECONCURRENTLYNONMALLEABLESTRINGCOMMITMENTTHEIRRESULTSPOINTTOALLINTERESTINGAPPROACHTOWARDSDESIGNINGEFFICIENTANDPROVABLYSECURECRYPTOGRAPHICSCHEMESWITHOUTRANDOMORACLESWENOTETHATALTHOUGHTHESEASSUMPTIONSARESTRONGERTHANTRADITIONALCRYPTOGRAPHICHARDNESSASSUMPTIONS，THEYSEEMQUITEREASONABLEANDITISCONCEIVABLETHAT，LIKEMANYOTHERASSUMPTIONSINTHEFIELDSUCHASTHEDECISIONALDIFLIEHELLMANASSUMPTION，THISTYPEOFNEWASSUMPTIONSMAYGAINWIDERACCEPTANCEAFTERFURTHERSCREENINGBYPEERSINTHEFIELDBYABSTRACTINGCONCRETEPROPERTIESOFTHERANDOMORACLEMODEL，WEEXAMINEAVARIANTOFPANDEYETA1SASSUMPTION77，CALLEDTHEADAPTIVEDDHASSUMPTIONBASEDONTHEADAPTIVEDDHASSUMPTION，AMODIFIEDVERSIONOFZHENGANDSEBERRY，SENCRYPTIONSCHEMEPROPOSEDIN【991ISPROVEDTOBEADAPTIVECHOSENCIPHERTEXTSECUREWITHOUTARANDOMORACLEZHENGANDSEBERRY99PROPOSEDTHREESIMPLEMETHODSFORIMMUNIZMGPUBLICKEYCRYPTOSYSTEMSAGAINSTCHOSENCIPHERTEXTATTACKSTHENATUREOFTHETHREEMETHODSISTHESAMETHEYIMMUNIZEDAPUBLICKEYCRYPTOSYSTEMBYAPPENDINGTOEACHQQ个性签名HTTP/WWWQQOOKCOMABSTRACTCIPHERTEXTATAGTHATISCORRELATEDTOTHEMESSAGETOBEENCRYPTEDBASEDONTHEGAPDIFFIEHELLMANASSUMPTIONGDH，BAEKANDZHENGT7】PROVIDEDASECURITYPROOFFORTHEFIRSTSCHEME，DENOTEDBYZHENGSEBERRYLWH，INTHERANDOMORACLEMODEL，LEAVINGASALLOPENPROBLEMPROOFSF研THEOTHERTWOSCHEMESTHEFOCUSOFOURWORKISTOMODIFYTHESECONDSCHEMEIN091，DENOTEDBYZHENGSEBERRY砌，SOTHATTHERESULTANTSCHEMEISADAPTIVECHOSENCIPHERTEXTSECURETHESCHEMEZHENGSEBERRYUHISWORTHSTUDYINGFORTHEFOLLOWINGREASONSFIRST，THESCHEMEIMMUNIZESPUBLICKEYENCRYPTIONAGAINSTADAPTIVECHOSENCIPHERTEXTATTACKSWITHTHEHELPOFAUNIVERSALHASHFUNCTIONTHISALLOWSTHESCHEMETOSTEERCLEAROFAONEWAYHASHFUNCTIONWITHNONSTANDARDOUTPUTSIZEWHEREBYSUCCESSFULLYAVERTINGPOTENTIALRISKSRECENTLYDISCOVEREDIN【67JSECOND，THEINPUTLENGTHOFAPLAINTEXTCANBEARBITRARY,WHILETHEOVERHEADOFTHECORRESPONDINGCIPHERTEXTISACONSTANTASARESULT，THERATIOBETWEENTHELENGTHOFTHECIPHERTEXTANDTHATOFTHEPLAINTEXTCANBECLOSETO1ASTHELENGTHOFTHEPLAINTEXTINCREASESCOMPAREDWITHKILTZETA1SCONCRETESCHEME641WHICHRELIESONTHEDDHASSUMPTIONANDAEOTSECURESYMMETRICENCRYPTION，OURMODIFIEDZHENG。SEBERRYLIJLSCHEMEISCONCEPTUALLYMUCHSIMPLERANDRETIESONLYONTHEADAPTIVEDDHASSUMP。DONMOREIMPORTANT，THISNEWLYMODIFIEDSCHEMEREQUIRESSIGNIFICANTLYLESSCOMPUTA。TIONTIMETHANKILTZETA1SCOMPAREDWITHDHIESWHICHRELIESONTHEORACLEDIFFIEHELLMANODHASSUMPTIONTOGETHERWITHTHESECURITYOFSYMMETRICENCRYPTIONANDAMESSAGEAUTHENTICATIONCODE，OURMODIFIEDSCHEMERELIESONLYONTHEADAPTIVEDDHASSUMPTIONANDPRESERVESTHECOMPUTATIONALEFFICIENCYOFZHENGSEBERRYJ11HOWEVELITISFAIRTOSAYTHATOURMODIFIEDZHENGSEBERRYSCHEMEANDDHIESARECOMPARABLE，EACHHAVINGITSOWNPROSANDCONSINPRACTICEWITHDHIES，ALLTHREEASSUMPTIONSONSYMMETRICENCRYPTION，MACANDODHARERESPONSIBLEFORTHESECURITYOFDHIESANDITISRELATIVELYEASYTOSELECTPROPERCANDIDATESTOREALIZEEACHFUNCTIONOFTHEASSUMPTIONWITHOURMODIFIEDZHENGSEBERRYSCHEME，THEADAPTIVEDDHASSUMPTIONWHICHISSOLELYRESPONSIBLEFORTLLESECURITYOFTHESCHEMEISSLIGHTLYSTRONGERTHANTHEODHASSUMPTIONREQUIREDBYDHIESABSTRACTRINGSIGNATURESTHENOTIONOFPUBLICKEYDIGITALSIGNATUREWASINTRODUCEDBYDIFFIEANDHELLMANT42JANDTHEEARLYCONCRETEIMPLEMENTATIONSWEREPROPOSEDBYRIVESTSHAMIRANDADLEMANT821FORTHESECURITYNOTIONSOFDIGITALSIGNATURE，ACOMPREHENSIVEWORKWASPRESENTEDBYT561ASWEKNOW,THEAIMOFSIGNATURESISTOAUTHENTICATETHESOURCEOFAMESSAGEANDPOSSIBLYTOENSURETHATAMESSAGEHASNOTBEENALTEREDDUNNGTRANSMISSIONINSOMEAPPLICATIONS，WENEEDTOHIDETHEIDENTITYOFASIGNER,WHICHRESUKSINTHEINVENTIONOFGROUPSIGNATURESANDRINGSIGNATURESRINGSIGNATURE，INTRODUCEDBYRIVEST，SHAMIRANDTAUMANL83，ISUSEDTOPROVIDEANONYMITYFORTHESIGNERITISCLOSELYRELATEDTOTHENOTIONOFGROUPSIGNATURE，WHICHALSOPROVIDESANONYMITYFORTHESIGNERBUTUNLIKEGROUPSIGNATURES，THEREISNOCENTRALGROUPMANAGER,PREARRANGEDGROUPOFUSERSORPROCEDURESFORSETTING，CHANGINGOFDELETINGGROUPSINRINGSIGNATURESCHEMEMANYWORKSABOUTRINGSIGNATURESARESUBSEQUENTLYPROPOSED，SUCHAS【4】，【581，【20】，【431，ETC。MOSTOFTHEWORKSAREPROVENSECUREINTHERANDOMORACLEMODELSOMEWORKSAREPROPOSEDINTHESTANDARDMODEL，BUTTHOSEWORKSARENOTSOSATISFACTORYXU，ZHANGANDFENG941PROVIDEDARINGSIGNATURESCHEMEINTHESTANDARDMODEL，BUTTHEIRPROOFISFLAWED；CHOW，LIU，WEIANDYUENSSCHEME1321ISBASEDONANEWASSUMPTION；BENDER,KATZANDMORSELLISSCHEMET171ISBASEDONTRAPDOORPERMUTATIONS，BUTTHEIRSCHEMEUSESGENERICZAPSFORNP,WHICHISIMPRACTICALHOWEVER,17】GAVEADETAILEDDISCUSSIONOFSECURITYMODELSFORRINGSIGNATURESRECENTYEARS，TWOEFFICIENTRINGSIGNATURESCHEMESWITHOUTRANDOMORACLESHAVEBEENPROPOSEDBYSHACHAMANDWATERST87】ANDBOYEN211ESPECIALLY871，ITISTHEFIRSTEFFICIENTRINGSIGNATURESCHEMEWITHOUTRANDOMORACLESBASEDONSTANDARDASSUMPTIONSIIL【871SHACHAMANDWATERSCONSTRUCTALINEARSIZERINGSIGNATUREINCOMMONRANDOMSTRINGMODELBASEDONCOMPUTATIONALDIFFIEHELLMANANDDECISIONALSUBGROUPASSUMP。TIONSFORLMEMBERSOFARING，THEIRSCHEMEHASTHESIZEOF212GROUPELEMENTS，ANDREQUIRES213PAIRINGSTOVERIFYTHEYSHOWTHATTHEIRSCHEMEISPROVABLYSECUREINTHESTRONGESTSECURITYMODELPROPOSEDBYBENDER,KATZANDMORSELLI【L71WITHRESPECTTOACONCRETEAPPLICATIONENVIRONMENT，WESHOWTHATTHERINGSIGNATURESCHEMETS7LCALLBEUSEDINAMOREEFFICIENTWAY,BASEDONTHEIDEAOFT31QQ个性签名HTTP/WWWQQOOKCOMABSTRACTIN431，DODIS，KIAYIAS，NICOLOSIANDSHOUPINTRODUCEDAGROUPPUBLICKEYFORTHERINGSIGNATURETHROUGHTHEACCUMULATORSWITHONEWAYDOMAIN，WHICHCANBECOMPUTEDBYANYMEMBERINTHERINGSUCHKINDOFSTRUCTUREOFRINGSIGNATURESALLOWSONEGROUPPUBLICKEYTOCORRESPONDTOMANYRINGMEMBERSSECRETKEYSTHANKSTOTHEGROUPPUBLICKEYFORTHERING，MEYPOINTEDOUTTHATTHESIZEOFTHERINGSIGNATURECANBECONSTANTINSOMECASES，EG，THERINGSTAYSTHESAMEFORALONGPERIODOFTIMEWESHOWTHATWECANAPPLYDODISETA1SSTRUCTURETOSHACHAMANDWATERSSCHEME，ASITCANPRODUCE“GROUPPUBSCKEY”FORTHERINGANDSUCH“GROUPPUBLICKEYCANPLAYTHEROLEOFTAGFORLINKINGCONSIDERTHECASETHATSIGNERASTAYSINARINGFORALONGTIME，ANDSHEUSUALLYNEEDSTOSENDHERRINGSIGNATURETORECEIVERB，WHILEAWANTSTOASSUREBTHATTHESESIGNATURESAREPRODUCEDBYTHESAMEMEMBERINTHERINGOURMODIFIEDSCHEMEISMOREEFFICIENTTHANCONVENTIONALRINGSIGNATUREWITHOUTRANDOMORACLESWHENAPPLIEDTOTHEABOVECASEASTHESIGNERCANDECIDEWHETHERTOPROVIDELINKABILITYBYHERSELF,WECALLTHESPECIALSHACHAMANDWATERSSCHEMESELFLINKABLERINGSIGNATURECONCURRENTSTATISTICALZEROKNOWLEDGEARGUMENTSZEROKNOWLEDGEPROOF,INTRODUCEDBYGOLDWASSER,MICALIANDRACKOFFT551，ISANINTERACTIVEMETHODFORONEPARTYTOPROVETOANOTHERPARTYTHATASTATEMENTISTRUE，WITHOUTREVEALINGANYTHINGOTHERTHANTHEVALIDITYOFTHESTATEMENTTHEPARTYWHOPROVIDESTHEPROOFISCALLEDTHEPROVERANDTHEPARTYWHOVERIFIESTHEPROOFISCALLEDTHEVERIFIERUNLIKETHETRADITIONALMATHEMATICALPROOFSWHICHISAFIXEDSEQUENCECONSISTINGOFEVIDENCETHATARECOMMONLYAGREED，ZEROKNOWLEDGEPROOFEMPHASIZESTHEINTERACTIONBETWEENTHEPROVERANDTHEVERIFIERTHENOTIONOFTHECONCURRENTZKFIRSTINTRODUCEDBYDWORK，NAORANDSAHAI145REQUIRESTHATTHEPROTOCOLREMAINSZKEVENMANYCOPIESOFTHEPROOFARERUNINANASYNCHRONOUSENVIRONMENT，SUCHASTHEINTERACTCANETTI，KILIAN，PETRANK,ANDROSEN261SHOWEDTHATNOLANGUAGESBESIDEBPPHAVECONSTANTROUNDBLACKBOXCONCURRENTZKPROOFSINTHESTANDARDMODELWHERENOPUBLICKEYINFRASTRUCTUREISAVAILABLE，ANDTHEYALSOGAVEAO109NLOGLOG，11LOWERBOUNDONTHENUMBEROFROUNDSFORSUCHPROTOCOLSRICHARDSONANDKILIANT8L】FIRSTPRESENTEDAFAMILYOFCONCURRENTZKPROTOCOLSABSTRACTFBRALLLANGUAGESINNPTHEIRANALYSISWASIMPROVEDBYKILIANANDPETRANK621WHOSHOWEDTHATAPOLYLOGARITHMICNUMBEROFROUNDSISSUFFICIENTFORTHECONCURRENTZKPROTOC01SUBSEQUENTLY,PRABHAKARANETA1178IMPROVEDTHEIRANALYSISTOPROVETHATTO109NROUNDSAREENOUGHASMICCIANCIOANDPETRANKT711POINTEDOUTALTHOUGHTHECONCURRENTZEROKNOWLEDGEPROTOCOLINTHESTANDARDMODELISLESSEFFICIENTTHANTHATINTHEPKIMODEL，THESTANDARDMODELCANBEUSEDWHEREAPKIISNOTPOSSIBLE，ORTOSETUPAPUBLICKEYINFRASTRUCTUREORESTABLISHCOMMONRANDOMSTRINGSFORINSTANCE，THESTANDARDPROTOCOLCANBEUSEDTOREGISTERPUBLICKEYSWITHACERTIFICATIONAUTHORITYANDBOOTSTRAPTHESYSTEMMICCIANCIOANDPETRANK7L】PROVIDEDANEFFICIENTMETHODFORCONVERTINGANYPUBLICCOINHVZKPROOFSYSTEMTOACONCURRENTZKPROOFSYSTEMBASEDONTHEDECISIONALDIFFIEHELLMANDDHASSUMPTION