《陷门承诺、陷门hash函数及其应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
陷门承诺、陷f-]hash函数及其应用研究摘要每个消息计算相应的陷f]hash和签名，计算和存储开销仍过大。本文利用无密钥泄露的陷f]hash函数，提出了一个新颖有效的在线／离线门限签名方案，由于陷f]hash值可以重复使用，从而大大降低了计算和存储复杂度。3．为了提高聚合签名的响应速度，本文提出在线／离线聚合签名的新概念。然而，如果直接利用密钥泄露的陷f-]hashi函数构造在线／离线聚合签名方案，仍然存在计算和通信开销过大的问题。本文利用无密钥泄露的陷f]hash函数，构造了一类有效的在线／离线聚合签名方案，从而在突发性的聚合签名需求中有较好的应用。4．最后，我们讨论了陷门承诺在无收据电子投票／电子拍卖中的应用，指出一类采用密钥泄露的陷门承诺构造的电子投票和电子拍卖方案并不满足其声称的无收据性。同时，我们提出指定验证者可链接环签名的新概念，利用陷门承诺构造了一个具体的方案，并基于此签名构造了一个新的无收据电子投票方案。关键词：陷门承诺、陷f]hash函数、变色龙hash函数、基于ID的陷门承诺、非延展、无密钥泄露、在线／离线签名、电子商务·II． 陷门承诺、陷f-]hash函数及其应用研究AbstractTitle：Major：Name：TrapdoorCommitment，TrapdoorHashandTheirApplicationsComputerSoftwareandTheoryChunhui、VUSupervisor：ProfessorDongyangLONGandAssociateProfessorXiaofengCHENAbstractCommitmentisanimportantcryptographicprimitive，itprovidestwobasicproper-tiesashidingandbinding．Commitmentmakesupanimportantbuildingblockformanyschemesandapplicationsinmoderncryptography,suchaszero-knowledgeproof，digitalsignature，identification，E-voting，E-auctionandSOon．Acommitmentschemecanbedividedintotwophasesascommitmentphaseandopeningphase．Afterthesendercoin-mittingtoamessage，themessagekeepshidinguntilheopensit，SOthereceivercangetnothingfromthecommitment．Ontheotherhand，thesendercannotbreakthebindingpropertyintheopeningphase，thatis，hecannotchangehismessagecommittedprevi—ously．Trapdoorcommitmentisacommitmentschemewithspecialproperties，thatis，onewiththetrapdoorkeycanopenhiscommitmentindifferentways，inotherwords，giventhetrapdoorkey,thistrapdoorcommitmentdonotsatisfythebindingpropertyastraditionalcommitmentschemes．Trapdoorhashisanotioncloselyrelatedtotrapdoorcommitment．Itcomputesahashvalueforsomegiveninformation，anddifferentopeningsintrapdoorcommitmentcorrespondingtocollisionsintrapdoorhash．ThisthesisinvolvesoursystematicresearchinID—basedtrapdoorcommitment，thenon-malleabilityofcom-mitment，thekey-exposureproblemoftrapdoorhash，andtheapplicationsoftrapdoorhashandtrapdoorcommitmentindigitalsignaturesandE-Commerce(suchasE-votingandE-auction)．Ourcontributionsinclude：1．Basedontheresearchofsecuritydefinition，securitymodelandadversarymodelintrapdoorcommitments，wedefineanewnotionnamedID—basednon-malleableIII 陷门承诺、陷f-]hash函数及其应用研究Abstracttrapdoorcommitmentandproposetwoefficientschemes．ThedefinitionofID—basedtrapdoorcommitmentinpreviousworksisforonespecificIDonly,whichcannotsatisfytherequirementofID·basedcryptsystem，SOwemodifythisdefinition．Thenweusetheideaofconstructingmulti—trapdoorcommitmentandnon-malleablecom-mitmenttoconstructthefirsttwoefficientID—basednon-malleabletrapdoorcom-mitmentschemesbasedondiscretelogarithm(DL)system，with／withoutrandomoraclerespectively．2．Previouson-line／off-linethresholdsignatureschemesalwayshavethekey-exposureproblem，andwehavetocomputeatrapdoorhashandthecorrespondingsignatureforeverysignedmessage，SOthecomputationandstoragecostarealittlemoreoverload．Weconstructanewefficienton—line／off-linethresholdsignatureschemeusingkey-exposurefreetrapdoorhash，whichreducesthecomputationandstoragecostevidently,becausethetrapdoorhashcanbereusedandtreatedaspublickey．3．Inordertoimprovetheresponseefficiencyofaggregatesignatures，weproposeanewnotionofon-line／off-hneaggregatesignature．However，ifusingkey-exposuretrapdoorhashtoconstructtheschemedirectly,thecomputationandstoragecostarealsooverload．Weconstructanefficientschemeusingkey-exposurefreetrapdoorhash．Soithasimportantapplicationsinaggregatesignatureswithburstytraffic．4．Wediscusstheapplicationsoftrapdoorcommitmentsinconstructingreceipt—freevotingandauctionschemes．Wepointoutthatsometypesofvotingandauc-tionschemesconstructedbykey-exposurefreetrapdoorcommitmentsarenotreallyreceipt．free．Inaddition，weproposeanewnotionoflinkableringsignature‘fordesignatedverifiersandconstructaconcreteschemeusingtrapdoorcommitment，thenweconstructanewreceipt-freevotingschemebasedonthissignature．KeyWords：trapdoorcommitment；trapdoorhash；chameleonhash；ID—basedtrapdoorcommitment；non-malleable；key-exposurefree；on-line／off-linesignature；e-commerceIV． 论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：焦盔堡日期：型lQ：6：3学位论文使用授权声明本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。学位论文作者签名：伍各晖日期：20lo年6月弓曰导师签名：态鎏黔盯日期：乙p【u年6月；日 陷门承诺、陷f]hash函数及其应用研究第1章引言承诺(commitment)是一个重要的密码原型，它提供隐藏性和绑定性两个基本性质，成为现代密码学许多协议和应用的重要构造元素，如零知识证明、数字签名、身份鉴别、电子投票、电子拍卖等。1．1课题背景直观上看，我们可以把承诺方案描述为一个带锁的铁盒子。在承诺阶段，发送者把消息放进盒子里，锁上之后交给接收者。一方面，接收者不能打开盒子以取得消息；另一方面，发送者也不能改变消息。前一个性质称为隐藏性，后一个性质称为绑定性。在打开阶段中，发送者把盒子的钥匙交给接收者，从而接收者可以打开盒子揭开原始消息。更严格的说，一个承诺方案是两个概率多项式时间的算法(发送方和接收方)之间所进行的一个交互式的协议，它包括两个阶段：1、在承诺阶段，发送方输入消息m和冗余值r，计算对消息m的承诺值C并将C发送给接收方。2、在打开阶段，发送方泄露消息m和冗余值r给接收方，使得接收方相信C确实是对消息m的承诺。根据发送方(接收方)是否具有无限计算能力，承诺方案可以分为无条件绑定(隐藏)和基于计算假设的绑定(隐藏)。一个承诺方案不能同时满足无条件绑定和无条件隐藏。陷门承诺(trapdoorcommitment)是一种特殊的承诺方案，该概念由Brassard等人[1]于1988年首先提出。陷门承诺方案一个特有的性质是它允许知道陷门信息的人以不同的方式打开承诺，即在给定陷门信息的条件下，陷门承诺方案不满足传统承诺方案的绑定性，所以也称为变色龙承诺(chameleoncommitment)。在陷门承诺的基础上，Krawczyk等人于2000年首次提出了陷f]hash函数[2】(也称为变色龙hash函数)的概念。这两个概念的主要区别在于陷门承诺方案分为“承诺’’和“打开"两个阶段，而陷f]hash函数使用一些特定的信息来产生一个固定的hash值。然而，这两个概念又密切相关，正女IlKrawczyk等人所指出，一个陷门承诺方案在非交互的承诺阶段自然诱导一个陷f-]hash函数，反之亦然。而且，陷门承诺方案中不同的打开方式恰好对应了陷一1一 陷门承诺、陷f]hash函数及其应用研究第1章引言f]hash函数不同的碰撞。陷门承诺和陷f-]hash函数在现代密码学的许多领域中有着重要的应用。首先，陷门承诺方案可以用来构造零知识证明协议，而Brassard等人提出陷门承诺的概念最初就是为了用于零知识证明系统中。在此之后，许多学者利用陷门承诺方案设计了各种用途的零知识证明协议[娜】。最初的研究只考虑单个证明者和验证者之间的协议，在分布式计算环境中Dwork等人[7]首先提出了同时零知识(concurrentzero-knowledge)的概念，它允许验证者并行地与多个证明者交互。DiCrescenzo等人[8]利用陷门承诺方案提出了一个高效的同时零知识证明协议。Canetti等人提出重置零知识(resettablezero-knowledge)[9]的概念，允许验证者把证明者重置到之前的某一步。类似的，Bellare等人f10】通过陷门承诺实现了安全的重置身份鉴别协议。随后进一步的研究直接导致了一些陷门承诺新概念的提出如多陷门承诺[111(multi-trapdoorcommitment)、混和承诺[121(hybridcommitment)等，而这些承诺方案反过来又促进了零知识证明技术的发展。Damgard[13]对承诺方案和零知识证明协议之间的关系和研究进展给出了一个很好的综述。他们之间的一个等价关系见[141。陷门承诺在设计非延展的承诺方案中有重要的应用。Dolev等人[151于1991年首次提出了非延展的承诺的概念，而且基于单向函数给出了一个非延展的承诺方案。然而，该方案需要复杂的交互式的零知识证明，因此不实用。在公用随机串模型下，DiCrescenzo等人『161给出了第一个非交互式的非延展的承诺方案。但是该方案的效率也只具有理论上的价值。在公用参数模型下，Fischlin等人[17]首次给出了交互式的基于标准假设(如RSA假设、离散对数假设)的非延展的承诺方案。随后，DiCrescenzo等人【18]给出了非交互式的基于标准假设的非延展的承诺方案。近来，对于非延展承诺所依赖的密码学基础，学者们进行了深入的研究。『19]i正日月在单向函数存在的假设下，同时非延展承诺方案存在。f201证明在单向函数存在的假设下，统计上隐藏的非延展承诺方案存在。陷门承诺和陷f-]hash函数在构造某些安全的数字签名中有着重要的作用。他们在设计无需随机预言假设的签名方案中有重要的作用[21，22】。另外，陷f]hash函数可以用于构造变色龙签名f2]。变色龙签名可以看作是一个非交互的不可否认签名，可以更简单和更有效的实现不可传递性和不可否认性，从而在版权保护、匿一2一 陷门承诺、‘陷f]hash函数及其应用研究第1章引言名信用证书[23—251中有着更广泛的应用。陷f]hash函数还可以用来构造在线．离线签名f26，271。在线一离线签名将一个签名过程分为两个阶段：1、离线阶段，在签名消息给出前就进行预计算；2、在线阶段，即在签名消息给出后，计算对应的签名。由于在线阶段一般只需要1次模乘(modularmultiplication)运算，所以即使在一个较弱的处理器(如智能卡)下也可以非常快的完成签名运算。目前，智能卡已广泛地应用在移动电话、PDA、银行卡等设备中，所以在线一离线签名在现实中有着非常重要的应用价值。然而，传统的陷门承诺方案和陷f]hash函数一般都存在所谓的密钥泄漏问题f28】，因此限制了它在实际中的进一步应用。陈晓峰等人[29]基于GapDiffie-Hellman群于2004年给出了第一个完全的无密钥泄露的陷f]hash函数和对应的变色龙签名方案。后来Ateniese等人f301对此工作进行了推广。同理，在线一离线签名中也存在密钥泄漏的问题，该问题由陈晓峰等人[31]在2007年首次提出并解决。近来，在线一离线签名一个新的安全模型被提出【32，33]。，陷门承诺在安全电子商务协议中也有重要的应用。例如，密封式标价拍卖中要求竞标结束前拍卖行不能知道投标者的标价，同时竞标结束后投标者不能改变其标价。普通承诺方案的隐藏性和绑定性刚好满足此应用，而陷门承诺方案的特性使得它可以进一步用来设计无收据的电子投票和电子拍卖协议[34—36】。由于投票者(投标者)可以利用陷门信息任意的打开承诺，从而无法构造一个证据来证明他提交了特定的选票(标价)，这样就防止了协议中的犯罪行为如买卖选票(串标)、强迫选举(强迫投标)等。此外，陷门承诺方案在合同签署协议[37，38]中也有着重要的作用。此外，陷门承诺在安全多方计算[39】中也有着重要的应用。Jakobsson等人[40]应用陷门承诺设计指定验证者证明系统，使证明者在向验证者证明某一陈述时，验证者无法传递这一证明使其他人相信这一陈述。Canetti和Fischlin[41】以及D锄gard和Nielsen[42]应用陷门承诺构造了广义可复合承诺方案，即此承诺方案可以和其他安全的方案安全地复合。1．2研究内容本文主要研究陷门承诺、陷f]hash函数及其在数字签名与安全电子商务协议中的应用。一3一 陷门承诺、陷f-]hash函数及其应用研究第1章引言·在研究承诺方案的安全定义、安全模型及敌手模型的基础上，提出基于ID的非延展陷门承诺的新概念并构造了两个有效的方案。[43]中定义的基于ID的陷门承诺‘只针对某一个特定的ID，即其公开参数与某一特定的ID相关，不满足基于ID的密码系统的要求，我们修正了这一定义。结合构造多陷门承诺的思想[1l，44]和构造非延展承诺的技术【l7]，我们首次提出了两个基于离散对数系统的有效的基于ID的非延展陷门承诺方案，分别基于随机预言模型和标准模型。·以往的在线／离线门限签名方案[45]往往存在密钥泄露问题，从而在离线阶段必须．为每个消息计算相应的陷f]hash和签名，计算和存储开销仍过大。本文利用『311中无密钥泄露的陷f]hash函数，提出了一个新颖有效的在线／离线门限签名方案，由于陷f]hash值可以重复使用，从而与[45]中的方案相比，大大降低了计算和存储复杂度。·为了提高聚合签名的响应速度，本文提出在线／离线聚合签名的新概念。然而，如果直接利用密钥泄露的陷门hash函数构造在线／离线聚合签名方案，仍然存在计算和通信开销过大的问题。本文利用[46]中无密钥泄露的陷门hash函数，构造了一类有效的在线／离线聚合签名方案，从而在突发性的聚合签名需求中有较好的应用。·最后，我们讨论了陷门承诺在无收据电子投票／电子拍卖中的应用j指出一类采用密钥泄露的陷门承诺构造的电子投票[36]署fl电子拍卖[35]方案并不满足其声称的无收据性；我们还提出了指定验证者可链接环签名的新概念，利用陷门承诺构造了一个具体的方案，并基于此签名构造了一个新的无收据电子投票方案。1．3论文结构本文的结构安排如下：在第2章中，参考[43]和[47】的方法，我们给出了文中要用到的基本密码学定义及承诺、陷门承诺、基于ID的陷门承诺和陷f]hash函数的有关定义。其中第2．6节给出了完全的基于ID陷门承诺的定义，与[43]中的定义不同，此定义更加符合基于ID密码系一4一 陷门承诺、陷f]hash函数及其应用研究第1章引言统的要求，从而为第3章基于ID的非延展陷门承诺方案的提出做好了铺垫。在第2．8节中，我们介绍了基于具体数论假设的几个基本的陷门承诺方案，如基于离散对数假设、RSA假设和整数分解假设的方案，这些基本方案是后文构造具有更多更好性质的承诺方案的基础。在第2．9节中，我们还介绍了基于复杂性理论构造的陷门承诺方案，如基于一般密码学假设一一单向函数存在的方案，这是理论密码学的重要研究方向，旨在研究承诺所依赖的密码学基础，也是我们今后要进一步研究的方向。第2．10节研究了无密钥泄露陷f-]hash函数的构造思路，我们定义的完全的基于ID陷门承诺可以转换为无密钥泄露陷f-]hash函数。无密钥泄露陷f-Jhash函数在第4章构造有效的在线／离线签名中具有重要作用。在第3章中，我们提出基于ID的非延展陷门承诺的新概念，结合构造多陷门承诺的思想『11，44】和构造非延展承诺的技术【17】，首次提出了两个基于离散对数系统的有效的基于ID的非延展陷门承诺方案，分别基于随机预言模型和标准模型证明了其安全性。我们将进一步研究基于其他具体数论假设的方案以及非交互的方案。在第4章中，我们研究了无密钥泄露的陷f]hash函数在在线／离线签名中的应用。本章主要讨论基于群体的在线／离线签名。我们构造了一个新颖有效的在线／离线门限签名方案。从介绍利用无密钥泄露陷f]hash函数【31]构造在线／离线签名方案开始，利用可验证秘密分享技术，把其扩展为一个门限方案。我们分析了方案的安全性并与[45]方案的效率做了比较。通过比较可知，本文的方案大大降低了计算和存储复杂度。在该章中，我们还提出了在线／离线聚合签名的新概念，此类签名在具有集中性聚合签名需求的应用或在资源受限的应用中具有重要作用。我们利用一个变形的无密钥泄露的陷I'-]hash函数构造了一个具体的方案，并对方案的安全性和效率进行了分析。在第5章中，我们研究陷门承诺在电子商务中的应用，研究电子投票／电子拍卖方案的无收据性，指出一类利用密钥泄露陷门承诺构造的电子投票／电子拍卖方案并不满足其声称的无收据性。我们还提出了指定验证者可链接环签名的新概念，利用陷门承诺构造了一个具体的方案，并基于此签名构造了一个新的无收据电子投票方案。第6章是总结和展望，对本文已完成的工作进行了总结，并提出了进一步的研究计划。一5． 陷门承诺、陷f]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造在这一章中，前七小节介绍密码学的一些基本概念和文中使用的符号，然后给出承诺和陷门承诺的形式化定义。我们只给出与陷门承诺有关的密码学基础，如单向函数、离散对数假设、RSA假设、整数分解假设以及承诺的概念，更全面的介绍请参考『471。后三小节在相关定义的基础上，介绍了陷门承诺以及无密钥泄露陷f-]hash函数(变色龙hash函数)的几个经典构造。第8节介绍基于具体数论假设的陷门承诺方案的构造，如基于离散对数假设、RSA假设和整数分解假设的构造，分析这些构造有利于我们构造新的陷门承诺方案；第9节介绍基于复杂性理论的陷门承诺方案的构造，如基于一般密码学假设一一单向函数存在的构造，旨在研究承诺所依赖的密码学基础；第10节给出了几个无密钥泄露陷f]hash函数的构造，可以看出其与基本陷门承诺方案的紧密联系。2．1一些符号令A是一个概率算法，更准确地说，A是一个有随机输入带的图灵机，如果存在一个多项式p(他)，使得对于长度为n的输入，A在p(n)步内完成，则我们说A是概率多项式时间(PPT：probablepolynomial-time)算法。如果A对于其内部的随机硬币，平均在多项式时间完成，则A平均在多项式时间完成。对于确定性算法A，记a卜A0)为输入z时算法A的输出a。如果A是概率算法，贝3JA(x)为输入z时，描述算法A的输出的随机变量。其概率空间是由A内部的随机硬币决定的。在这种情况下，记陋@)】为输入z时Am支集，记a-A(z)为输,kz时，从算法A的输出随机变量A(z)中取出样本am过程。为了简化表示，常常把概率多项式时间算法看成确定性算法，并把随机硬币作为输入的一部分，即为A(x，r)。在本文中，只讨论上述的图灵计算模型。记⋯为一个串z∈．[o，1)+的长度，记1n为n个‘1’组成的串，记z∈R．[o，1)几为均匀选择的一个佗一比特串z。如果不特别说明，任何均匀选择都是独立于其他选择的。函数5：N_R+称为可忽略的(negligible)(关于n)，如果它比任何多项式的倒一7一 陷门承诺、陷f-]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造数都下降得快。更形式化地描述为，占是可忽略的，如果对任意多项式p：N—R+，存在nO∈N，使得对所有n≥no，有6(礼)<1／p(n)成立。在后文中，把“存在no∈N，使得对所有礼≥几o⋯"简述为“对所有足够大的佗"。函数J(礼)是显著的(noticeable)(关于扎)，如果它不是可忽略的；而把6(n)称为是压倒性的(overwhelming)，如果1—6(n)是可忽略的。。举例来说，存在一个函数(数列)，既不是可忽略的(即为显著的)，也不是压倒性的，如：1，；，1，石1，⋯，从而显著的不一定是压倒性的，而反之压倒性的一定是显著的。函数6(n)=2咄是可忽略的。容易看出，乘积艿(佗)·p(佗)也是可忽略的，其中p(扎)是任意的正多项式；如果6(n)是可忽略的，，(佗)是显著的，则‘厂(礼)一6(佗)也是显．著的。对于一个随机变量序列X=(％)n∈N，记z卜K为从随机变量％中取的一个样本z。序列x称为是可有效取样的，如果存在概率多项式时间算法A使得．k与A(1n)对所有的n是同分布的。算法A的输入1几表示允许4的运行时间为输入长度11nI=n的多项式。两个随机变量序列x=(％)礼∈N和Y=(K)n∈N称为计算上不可区分(computationallyindistinguishable)(X毛y)，如果对任意概率多项式时间算法D，其优势Advx'y=lProb[D(1",z)=1】-Prob[D(1n,Y)=1】I是可忽略的，其中的概率由D的随机硬币，和随机选择z卜％和Y卜K分别决定。算法D在输入z和∥时，其输出在可忽略的情况下是一致的，也就是说，不存在多项式时间算法区分两个随机变量K和碥。两个随机变量序列X=(X。)n∈N和Y=(K)n∈N称为是统计上不可区分(statisticallyindistingusishable)(X毛Y)，如果‘专·∑IFrob[Xn=s卜P础陬=s】I。sES．是可忽略的，其中&是K与K的支集的交集。如果上式为0，则说明X与y是同分布的，记为X兰y。显然，同分布涵含统计上不可区分，统计上不可区分涵含计算上不可区分，反之则不然。-8- 陷门承诺、陷f-]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造2．2密码学假设我们从一般的单向函数的定义开始，介绍与陷门承诺有关的密码学假设。简单地说，单向函数即为正向计算容易，而对随机输入反向求逆困难的函数。单向函数存在是密码方案存在的必要条件。定义2．1(单向函数)．一个函数，：．【o，1)+一．[o，1)+是单向函数，如果下面两个条件成立：·有效计算：存在多项式时间算法Eval，使得对所有X∈．[o，1)+，有Eval(x)=，(z)。·单向性：对任意概率多项式时间算法A，求逆成功的概率lnv二(n)=Prob[A(1n，，(z))∈f-,(，(z))】关于佗是可忽略的，其概率由z∈R．[o，1)n和A的随机硬币决定。另外的，如果对于所有n∈N，有，(．[o，1)n)={o，1)n，则，为单向置换。在此定义中，需要附加输入1n，这是因为如果IXf》If(x)l，使得求逆算法仅仅因为函数剧烈地压缩输入，而无法在关于I，(z)I的多项式时间内输出函数的逆，这种情况不能视为单向函数，必需排除在外。附加输入1n使得求逆算法可以在关于IXl的多项式时间内输出结果，从而排除了上述没有足够的时间输出逆的情况。以长度函数f(x)=H为例说明，因为I，(z)I=l092⋯，即使存在一个明显的求逆算法在关于例的多项式时间内求得，@)的逆(如输出逆为o㈦)，也没有算法能在关于I，@)i的多项式时间内输出逆。下面介绍几个单向函数的候选，一个是广为人知的粥A函数『481。给定整数N=p口和整数e，其中p、g为两个不相等t拘n／2一比特长素数，e与欧拉函数妒(Ⅳ)=∞一1)(g一1)互素，对于输A．x∈z知，其函数值)}-JRSAN，。(z)=X8modN。注意到这是z知上的置换；并且在不知道Ⅳ的分解的情况下，给定r∈Z≈和多项式有界的e，可以有效地计算逆r一1∈Z≈和幂r8∈Z知。一9一 陷门承诺、陷f-]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造RSA函数并不符合定义2．1，因为定义2．1只针对单个函数．厂，而RSA函数是由指标Ⅳ和e定义的函数集合，并且定义域和值域Z≈都依赖于指标。然而，我们并不严格讨论这种带指标的单向函数(indexedone-wayfunctions，也即，collectionsofone-wayfunctions)，因为其形式化定义更加复杂；而是对定义2．1作一个基本的处理，即增加一个指标生成函数输出一个随机的指标i(如这里输出随机的Ⅳ和e)，而A(1n，i，五(z))求逆的概率则由随机选择的指标i，定义域中随机选择的z和A的随机硬币决定。我们形式化地说明RSA函数是单向函数。为此，如上所述，假设存在有效算法IndexGen(1n)输出指标Ⅳ和e，而不详细说明算法如何做到这一点，如得到安全素鳓=纠+1，q=2q7+1，其中p，、g，为素数；又或者需要多大的e等等。这些讨论超出了本文的范围，而对于把RSA函数作为“黑盒”用于构造密码方案也是无益的。定义2．2(RSA假设)．对任意概率多项式时间算法A，其求逆成功的概率：InvARsA(n)=Prob[A(1n，N，e，z8roodN)=z]关于n是可忽略的，其中，概率由(N，e)卜IndexGen(1n)，z∈RZ≈和A的随机硬币决定。RSA函数是单向函数的好的候选，其中一个原因是它有random-self-reducibility性质[49]。简单地说，这意味着计算任意剪的e次方根与计算随机的可的e次方根是同样难度的。更形式化地描述为，假设存在概率多项式时间算法以概率6(n)对随机的Y=z8roodN求逆，其中(Ⅳ，e)卜IndexGen(1n)，其概率Fh(N，e)、笫和随机硬币决定。则存在有效算法在相当的时间内以相同的概率6(礼)对任意Y∈ZⅣ求逆，其中(N，e)卜IndexGen(1n)，其概率由(N，e)和随机硬币决定。后面算法随机选择7'∈冗ZⅣ，计算矿=yr6modN，并把(秒7，Ⅳ，e)输入到前面算法中。其中，秒7在ZN中均匀分布。如果前面算法输出Ⅳ7的逆z7，则z=z7r一1roodⅣ即为Y的逆。显然，RSA假设蕴涵整数分解问题是困难的；否则可以很简单地计算出汐(Ⅳ)和d=eomod妒(Ⅳ)，从而得到z=(Xe)dmodN。反之则不确定(一些迹象表明其不成立)。一10- 陷门承诺、陷f-Jhash函数及其应用研究第2章陷门承诺的相关定义和基本构造为了形式化地说明整数分解假设，类似地，假设存在有效算法IndexGen(1n)，输出一个随机的模数N=Pq，其中p和q为佗／2．比特长素数。定义2．3(整数分解假设)．对任意概率多项式时间算法A，其求逆成功的概率：Inv二口d(n)=Prob[A(1n，N)=∞，口)】关于礼是可忽略的，其中，概率由Ⅳ=Pq卜IndexGen(1n)和A的随机硬币决定。，虽然RSA问题已经提出三十多年了，它始终没有被攻破。另一个抵抗了至今为止所有算法攻击的单向函数的候选是群Z：或椭圆曲线群上的离散对数。我们简化并只考虑群Z：的素数阶子群上的离散对数问题。除非明确地指出，否则下文中所有的假设和结论都可以推广到其他素数阶群如椭圆曲线群中。再次假设存在有效算法IndexGen(1n)，输出一个随机的素数P，一个n一比特素数q满足qlp一1，以及z；的子群Gq的生成元9，同样地，忽略这个过程的细节。离散对数的单向性指的是给定夕和旷计算离散对数z是困难的。定义2．4(离散对数假设)．对任意概率多项式时间算法A，其求逆成功的概率：InvDL(n)=Prob[A(1n,P，q，夕，gzmodP)=z]关于n是可忽略的，其中，概率由仞，q，夕),-IndexGen(1n)，z∈RZq和A的随机硬币决定。类似于RSA，离散对数问题也有random-self-reducibility性质，给定P，q，夕和可∈纬，随机选择7．∈兄zg，令矿=Yg’(则y’是随机的)，则由随机元素∥7的离散对数z7=l099矿可以得到任意元素可的离散对数z=loggy=z7一rmodq。2．3交互式协议在这一节中我们介绍联合计算模型。我们避开[47]中交互式图灵机的技术细节，而采用了【43】中对交互式算法的更为直观的描述，这些算法相互连接并能交换信息。一11— 陷门承诺、陷门hash函数及其应用研究’第2章陷门承诺的相关定义和基本构造在一个两方运行的交互式协议中，Alice和Bob两方交替地运行。每一方都可能得到一个秘密的输出。令W为Alice和Bob的公共输入，z和Y分别为他们的秘密输入。假设Alice开始协议的运行：记Alice发送的第一个消息为a1，Bob的回复为b2，Alice发送给Bob的第二个消息为a2等等。注意到n1，b1，a2，62，⋯为随机变量(来源于Alice和Bob的随机硬币Q和p)，并由输入和之前收到的消息决定。因此我们记al=Alice(w，z，a)，bz=Bob(w，Y，∥，口1)，a2=Alice(w，书，Ol，a1，b1)，⋯。从而al卜Alice(w，z)，bl卜Bob(w，Y，a1)，a2卜Alice(w，z，al，b1)，⋯是一个有序的取样过程，即用户生成的一系列消息采用了相同的随机硬币。记viewAz妇($)，Sob(F)(伽)为包含了五个元组的随机变量：在分别输／kW，z和W，可的情况下两方传递的信息，各方生成的随机数，以及各方的秘密输出。我们称此随机变量的一个取样V=(Vm艰，Vmd，Alice，Vrnd，BD6，％ut'Az妇，％ut’B06)卜vieWAU∞(z)，Bob(掣)(叫)为一个扩大的视图(augmentedview)。敌手可以假冒一方，例如假Alice以欺骗Bob。在这种情况下我们用星号来标记被敌手控制的用户，例如，Alice+，以及viewAz池·(2)，Bob(掣)(伽)，Vrnd，刎池·，Vout，Allce。等等。在某些情况下，我们允许某个第三方Carrol参与一个预处理过程并为用户生成另外的公共输入仃，记为盯卜Carrol(w，名)，其中Z为Carrol的秘密输入1。例如Carrol可能在输入1n的条件下，随机选择一个m比特RSA模数Ⅳ并放入盯中。公共参数盯被加入扩大的视图中。此种情况下的概率空间由三方的随机硬币决定。在典型的情况下，Carrol被称为可信第三方丁，从而不被破坏。公共参数盯被称为公共串(publicstring)、公共访问串(comnlonreferencestring)或公共参数(publicparameter)，而相应的模型称为公共访问串模型(commonreferencestringmodel)或公共参数模型(publicparametermodel)。有了上述符号，我们画出承诺方案的运行视图如图2．1所示。1z可以为公共参数的陷门，例如在第4章基于ID的陷门承诺中，z为主私钥MSK。w为三方Alice，Bob和Carrol所共知，例如安全参数1竹。一12— 陷门承诺、陷f-]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造图2-1承诺方案的运行视图2．4承诺方案的隐藏性和绑定性在前言中，我们把承诺比作带锁的盒子，在这一节中，将给出承诺的形式化定义。当然，这里只给出承诺方案的最小定义，即满足隐藏性(hiding)和绑定性(binding)的承诺方案。在后文中，当考虑到协议运行中的相互影响时，将给出更复杂的定义，如非延展性(non-malleable)。从最小定义开始，一方面是遵循从简单到复杂的原则，基本定义易于使我们对承诺有一个直观的理解：另一方面是因为满足基本定义的承诺在某些应用中是足够的，例如我们可以用满足基本定义的承诺方案来构造非延展的承诺方案。承诺是两方参与的交互协议，一方是发送者S，拥有消息m；另一方是接收者冗。在一些承诺协议中，有一个可信第三方在协议运行之前帮助建立公开参数；发送者和接收者都可以访问公开参数。整个协议分为承诺阶段和打开阶段。在承诺阶段中，发送者给接收者一条关于消一】3一 陷门承诺、陷fJhash函数及其应用研究第2章陷门承诺的相关定义和基本构造息m杂乱信息(承诺值)，从而一方面，恶意的接收者冗+不能得到关于消息m的任何信息(隐藏性)；另一方面，恶意的发送者S+不能对之前的承诺值有不同于原承诺消息的另外的打开(绑定性)。’在打开阶段中，发送者给接收者发送用于打开杂乱承诺值的密钥，即发送原始消息m和承诺值确实包含此消息的一个证据。通常，此证据为发送者在承诺阶段中选择的随机数，因为接收者可以根据消息m和该随机数重新计算承诺值以确定承诺的正确性。当然也有一些方案，发送者采用其他方式计算证据。由隐藏性和绑定性，可以把承诺方案分成两种基本类型：·统计上绑定(statisticallybinding)和计算上隐藏(computationallyhiding)的承诺方案．任意具有无穷计算能力的恶意发送者5+计算异于原承诺消息的打开的概率是可忽略的(统计上绑定)；并且对于任意概率多项式时间的(恶意的)冗+，两个承诺值是计算上不可区分的(计算上隐藏)。更进一步，如果绑定性是无条件的而不仅仅以较高的概率达到，即具有无穷计算能力的恶意发送者S+计算异于原承诺消息的打开的概率是0，则这样的方案称为是无条件绑定的(unconditionallybinding)或完美绑定的(perfectlybinding)。·计算上绑定(computationallybinding)和统计上隐藏(statisticallyhiding)的承诺方案．任意概率多项式时间的恶意发送者5+对于一个承诺不能有两个不同的打开，否则与某个密码学假设相矛盾(计算上绑定)；并且对于任意具有无穷计算能力的佗+，承诺值的分布是统计上不可区分的(统计上隐藏)。更进一步，如果对于具有无穷计算能力的冗+，任何消息的承诺值的分布是相同的，则这样的方案称为是无条件隐藏的(unconditinallyhiding)或完美隐藏的(perfectlyhiding)。不难看出，一个承诺方案不能同时达到统计上绑定和统计上隐藏，从而也不能同时达到完美绑定和完美隐藏。对于后者，我们给出一个易于理解的说明。根据定义可知，完美绑定意味着任何承诺只能有一个打开，即消息和承诺值是一一对应的；这与完美隐藏相矛盾，因为完美隐藏意味着一个承诺值可以打开为任意消息。对于前者结论，其证明更为复杂些，这里不给出严格的证明。由于统计上绑定和统计上隐藏不能一】4一 陷门承诺、陷I'lhash函‘数及其应用研究第2章陷门承诺的相关定义和基本构造同时达到，我们只需要说一个承诺方案达到了统计上绑定或统计上隐藏(完美安全性也是如此)，则其另一个安全性自然只能达到计算上的安全。当然，还有一类承诺是计算上绑定和计算上隐藏的，其是否具有更为简单的构造和特殊的应用需要进一步研究。2．4．1统计上绑定的承诺方案下面我们给出统计上绑定的承诺方案的定义。可信第三方丁在协议运行之前提供公共参数盯。如果不需要可信第三方，则让他空闲并让盯为空。承诺协议的消息空间为一个序列M=(地)n∈N，其中集合％∈{o，1)’，礼为安全参数。假设消息长度的上界是关于n的多项式，即存在多项式p(礼)使得对任意序7U(mn)n∈N，mn∈％，有ITFtnI≤p(n)。如果协议的安全参数为礼，则发送者可以承诺任意消息m∈％。例如对于比特承诺，对于所有的竹，有坛={o，1)，则这里的安全参数凡只决定了绑定性和隐藏性的程度，因为消息固定为1．比特长。使用『43]1拘符号，给出统计上绑定的承诺方案的定义如下：定义2．5(统计上绑定的承诺方案)．一个三元组(S，冗，丁)被称为是统计上绑定的肛承诺方案，其中S，7已和丁为概率多项式时间算法，如果以下条件成立：·完备性．对所有的n∈N，任意消息mn∈％，任意augmentedviewu∈[views(∞mm，m。)，冗(comm)，7(1n)]有T已(decom，1n，Va，VmSg，Vrnd，冗，mtI，"md，s)=accept．·计算上隐藏性．对任意序列(mn)n∈N，(m：)n∈N，其中m佗，m：∈％，和任意概率多项式时间算法冗+，如下两个随机变量和由u卜[views(∞mm，m。)，彤(comm，m。，m乞)，7(1n)]定义的um锯由口÷一[views(comm，m乞)，冗·(∞mm，m。，m鲁)，T(1n)]定义的u二。g一15— 陷门承诺、陷f]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造计算上不可区分。·统计上绑定性．对任意具有无限计算能力的S+和augmentedviewV卜[views·(∞mm)，冗(comm)，丁(1n)]，5+输出如下结果(mn，m：l，r，r7)=5+(decom，1n，％，Vm锫，Vmd，s·)使得冗(decom，1n，％，‰锯，‰d，冗，mn，7．)=冗(decorn，1n，Ua，Ymsg，"Urnd，R，m：，，)=accept成立的概率(由所有参与者抛掷的随机硬币决定)是可忽略的，其中‰，m：l∈％是两个不同的消息，r和r7是伪造的随机数。如果此概率为0，则称方案为完美绑定的。由上述定义可知，对恶意的接收者，承诺方案仍然是隐藏的，即使他知道承诺的消息是mn或m：其中之一，并且他可以任意地违背协议，当然，恶意的接收者产生的view必须和诚实的接收者计算上不可区分，否则发送者发现不当行为时就会终止协议的执行。对绑定性的攻击描述为，让恶意的发送者首先与诚实的接收者执行承诺阶段，然后计算不同的合法打开以欺骗接收者。注意到，虽然S’结合了承诺阶段和打开阶段两个算法，如果我们给S+提供承诺阶段的样本％，Vm；g，Vrnd，5。并在模式decom下运行∥，则我们给S+(decom，·)提供了其在模式comm下能收集到的所有信息。2．4．2统计上隐藏的承诺方案统计上隐藏的承诺方案可以采用类似定义2．5的定义方法，只是在考虑信息论安全时，针对的是隐藏性而非绑定性。定义2．6(统计上隐藏的承诺方案)．一个三元组@，冗，丁)被称为是统计上隐藏的M一承诺方案，其中S，冗和丁为概率多项式时间算法，如果以下条件成立：·完备性．对所有的n∈N，任意消息mn∈％，任意augmentedview口∈[views(comm，竹h)，冗(comm)，丁(1n)]有冗(decom，1n，Va，Vm艰，Vrnd，冗，仇n，Vrnd，s)=accept．一】6一 陷门承诺、陷门hash函数及其应用研究第2章陷门承诺的相关定义和基本构造·统计上隐藏性．对任意序列(‰)n∈N，(m：)n∈N，其中mn，m：∈地，和任意具有无限计算能力的冗。，如下两个随机变量知由u卜[views(comm，‰)，形(∞mm，m。，m么)，T(1n)]定义的um铭由"+一[views(∞mm，m乞)，形(comm，m。，mo)，7(1n)】定义的u二sg统计上不可区分。如果他们是相同分布的，则称方案为完美隐藏的。·计算上绑定性．对任意概率多项式时间算法S+和augmented访ew钐卜[views·(。。mm)，冗(comm)，7(1n)】，5+输出如下结果(m竹，m：l，r，r7)=F(decom，1n，Va，Vm铭，um郴-)使得冗(decom，1n，％，VmSg，Vrnd，冗，mn，r)=冗(decom，1n，Va，"m铭，Vrnd，冗，m：，r7)=accept成立的概率(由所有参与者抛掷的随机硬币决定)是可忽略的，其中mn，m：∈％是两个不同的消息，r和r7是伪造的随机数。2．4．3一个基于离散对数的承诺的例子我们给出基于离散对数假设的完美隐藏和计算上绑定的承诺的例子【50】。这对于我们理解后文要定义的陷门承诺都是有好处的。假设有一个可信第三方生成公共参数如下：选择大素蜘，q，其中gI(p一1)；令g是g阶子群G口cz；的生成元；随机选择X∈RZ口，令h=旷(^≠1，则^也是Gq的生成元)。在承诺阶段，S对消息m∈Z口计算承诺值C=gmh7modP，其中r∈RZ口，并发送给冗。冗可以简单验证是否有C∈G。，即验证C∈Z：和口=1modp；在打开阶段，S发送m，r给接收者，接收者验证m，r∈Zg和C=夕m∥modP。方案是完美隐藏的。因为h’在信息论意义上隐藏了扩，即承诺值是一个与消息无关的随机数，所以即使冗+有无限计算能力，也不能区分两个承诺值。·17— 陷门承诺、陷门hash函数及其应用研究第2章陷门承诺的相关定义和基本构造方案是计算上绑定的。如果恶意发送者能找到某个承诺C的两个不同打开m，7_∈Zq和m7，r7∈Z口，即9mhr=C=9m7hr。modP，从而有夕m—m7=h7’一roodP，进而得Nh关于夕的离散对数为z=(m—m，)(7’7—7')-1rood口(因为仇≠m7，所以r≠r’，从而(r’一r)modg的逆(r7—7．)_1rood口存在)。也就是说，不同的打开蕴涵着离散对数问题的解决。然而，我们假设离散对数问题是困难的，所以∥计算不同打开的概率是可忽略的，即方案是计算上绑定的。2．5陷门承诺承诺中陷门的概念可以参照零知识的概念[47]来定义：存在一个有效的模拟器，使得对承诺阶段的模拟与诚实参与者的执行是不可区分的；同时，模拟器还能输出一个附加的陷门信息，使得承诺可以打开为任意消息。这个不可区分性意味着模拟器可以模拟发送者或第三方，与诚实参与者掺合在一起执行，使得不诚实的接收者不能区分协议是在真实世界中(与第三方和发送者)执行，还是在模拟环境中(与模拟者)执行。这正是我们在安全性证明中想要的，如果敌手攻击一个包含承诺的密码方案，而把真实承诺替换为模拟承诺，敌手无法区分，即敌手无法区分证明过程中的真实协议运行和模拟协议运行，从而证明中的模拟是有效的。在协议的真实执行中，承诺满足绑定性；而在模拟执行中，我们可以任意打开承诺，这给了我们更多的能力从而可能证明更复杂协议的安全性。在上述基于离散对数的承诺的例子中，存在着陷门信息。让模拟器代替可信第三方选择素数P，gIp一1)和子群G口∈Zp的生成元夕(阶为素数g)，模拟器生成h=旷modP，其中z∈RZ：，并公开这些参数。则z即为陷门信息。如果模拟器代替发送者承诺消息蛳，即发送C=夕mohr0roodP，其中怕∈RZq，则模拟器利用陷门信息z可以把承诺打开为任意消息m∈Z口，即计算r=r0一(m—mo)z～roodq，显然有C=夕丌均^70=gmoh7+(7n一仃阳)z一1=9mo^-夕’n—mo=夕m^rmodP注意到，即使对于不诚实的接收者，模拟器的行为与诚实参与者的行为也是不可区分的：公共参数的分布相同，承诺C和承诺打开m，7．的分布也相同(注意Nr是均匀分布的，因为％是均匀分布的)。这就是完美可模拟的陷门承诺的例子。-】8一 陷门承诺、陷f]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造参照[43]的定义，给出陷门承诺的定义如下：定义2．7(陷门承诺方案)．令@，冗，丁)是一个肛承诺方案。则此方案称为’陷门M．承诺方案，如果对任意概率多项式时间算法佗+存在平均多项式时间算"法Sim，使得对任意消息序列(mn)n∈N，mn∈心，有如下成立：称陷门承诺是输2＼(comm，1n)，模拟器Sire输出一个元组(W盯，Wmsg，W，。d，形，Wout，Sim)卜Sim(comm，1佗)使得给定-Wout,Sim和消息mn模拟器返回(Wrnd，s，Wout，s，ZLTout,冗-)+一Sim(decom，1n，"2n，Z／Jout,Sim)并且(叫口，Wm蹈，Wrnd，5，Wrnd，彤，Wout,s，Z／Jout,冗·)与views(∞mm，m。)，弦(comm)，丁(1n)的分布是不可区分的。·完美可模拟的，如果分布是相同的，·统计上可模拟的，如果分布是统计上不可区分的，·计算上可模拟的，如果分布是计算上不可区分的。把模拟器的输出叫out．Sim称为陷门。2．6基于ID的陷门承诺f431给出非交互的基于ID陷门承诺的定义，然而，其定义的并不是一个完全的基于ID的承诺，因为公开参数的生成与某个特定的ido有关；而在基于ID的密码体制中，有一对主密钥(MSK，MPK)，由主私钥为每一个id生成相应的用户私钥。在【43]的基于ID的承诺中，无法模拟预言机Extract(．)。我们按照基于ID的密码体制的思想，参考【511，给出完全的基于ID陷门承诺的定义。此定义更具一般性，并且把基于ID的承诺与无密钥泄露的陷f3hash函数联系起来，因为其无密钥泄露性允许敌手询问一个类似于此处Extract(．)的预言机，我们将在下节中清楚地看到这一点。一】9一 陷门承诺、陷f]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造定义2．8(基于ID陷门承诺方案)．令p，冗，丁)是一个基于ID的(，D，M)一承诺方案，其中主密钥对为(MSK，MPK)。则此方案称为基于ID的陷门(JD，M)一承诺方案，如果对任意概率多项式时间算法冗+存在平均多项式时间算法Sim，使得对任意消息序列(‰)竹∈N，mn∈眠，在冗+得知主私钥MSK的情况下，有如下成立：输)x．(comm，1n，idl)，其中idi∈儿k，模拟器Sim输出一个元组(W盯，Wm铭，z也，Wo浊ut,Sim)卜Sim(comm，1n，{成)使得给定缸盛．S．m，弛和消息mn模拟器返回(Wrnd，s，Wout，s)卜Sim(decom，ln，弛，‰，‘ww。idut．1sim＼J并且(叫盯，Wmsg，idi，Wmd，s，Wout，5)与views(∞mm，‰)，彤(∞mm)，丁(1n)的分布是不可区分的。称陷门承诺是·完美可模拟的，如果分布是相同的，·统计上可模拟的，如果分布是统计上不可区分的，·计算上可模拟的，如果分布是计算上不可区分的。把模拟器的输出叫缘’S．m称为对应于身份t幺的陷门。更进一步，方案p，冗，丁)称为计算上绑定的，如果以下成立：对任意概率多项式时间算法S+和Sim(comm，1n，弛)的输出w口，Wm铭，{也，叫。idut．isim)，其中idt∈RID．，i=1，2，⋯，poly(·)，有(mn，m：I，r，r7，‰铭，{厶)卜s+(decom，1n，W盯，Wm艰，弛，Wo池ut．S．m)。其中mn，喊∈螈且‰≠m么，idn∈IDn．Ekidn≠idt，i=1，2，⋯，poly(·)，使得T已(decom，W盯，Vmsg，idn，mn，r)=7已(decom，Wa，Vmsgid．，m：，r7)=accept成立的概率是可忽略的(由所有参与者抛掷的随机硬币决定)，其中咄．S．m为预言)6『乙Extract(·)对碱的回答，∥可以询问此预言机多项式poly(·)次．一20· 陷门承诺、陷门haSh函数及其应用研究第2章陷门承诺的相关定义和基本构造具体地说，基于ID的陷门承诺方案包含如下五个概率多项式时间算法(KeyGen，Extract，Corn，DCom，Eqv)：·KeyGen：输入安全参数A，输出一个随机的主私钥MSK∈R．[o，1)A和一个主公钥MPK。·Extract：输A(ID，MSK)，输出身份，D对应的陷门T所D。·Com．-输入(MPK，ID，m，r)，输出身份，D下对消息m的承诺c，其中r为随机数。我们把算"法Com(MPK，ID，m，r)简-i．己为Com／o(m，r)。·DCom：输入承诺C，输m(m，r)作为其打开，满足：COmlo(m，7’)=C。·Eqv-输／入,(MPK，ID，T尬D，C，m，r，m，)，输mr7满足Comzo(m7，r7)=COmlD(m，r)。即在得知身份ID所对应的陷门T所D的情况下，打破承诺的绑定性是容易的。2．7陷f"]hash函数陷f3hash函数又称为变色龙hash函数(chameleonhash)，F{日Krawczyk和P谂bin首先提出[2】。“变色龙”形象地说明了陷门的拥有者可以任意计算变色龙hash函数的碰撞。陷f-]hash函数最初是为了设计变色龙签名而提出的，变色龙签名同时达到了不可否认性和不可传递性，类似于不可否认签名[52]的性质，然而前者是非交互的，其实现更为有效；并且采用“hash-and-sign’’的标准构造模式，可以把任何签名转化为变色龙签名，从而更具一般性。陷f-]hash还可用于构造在线／离线签名，采用‘‘hash-sign-sWitch”的构造模式[27]，可以把任何签名转化为在线／离线签名。在变色龙签名中，陷门由接收者掌握；而在在线／离线签名中，陷门由签名者掌握。本文将详细描述陷门hash函数在在线／离线签名中的应用。一个非交互的陷门承诺方案可以诱导出一个陷f-]hash函数，其承诺值即为陷f-]hash值，其不同的打开对应着陷f-]hash的碰撞。上述陷门承诺的定义采用交互式协议的描述方法，而此处对陷f-]hash函数采用另外的描述方法。我们将在其后说明这两个概念的联系。一21· 陷门承诺、陷门hash函数及其应用研究第2章陷门承诺的相关定义和基本构造定义2．9(陷I'1hash族：)．一个陷门hash族由二元组(Z，咒)组成：·Z是一个概率多项式时间的密钥生成算法，输入1七，输出hash／陷门密钥对(日K，TK)，使得日K，TK的长度是k的多项式。·咒是随机的hash函数族。咒中的每一个函数关联着一个hash'密钥日K，其作用于消息空间M中的一个消息和有限空间R中的一个随机数。Hash函$史HHK的输出与TK无关。一个l'-]hashi函数族(z，咒)满足如下性质：·有效计算：给定hash'密钥日K和一对(仇，r)∈M×R，H日K(m，r)在多项式时间内可算。·抗碰撞：不存在多项式时间的算法4，在只输入日K的情况下，以不可忽略的概率得到两个对(m1，7．1)，(m2，r2)∈M×R满足m1≠m2FtHHK(m1，r1)=HHK(m2，r2)(其概率与HK有关，在这里(日K，丁K)卜z(1七)，且与算法4投掷的随机硬币有关)。·陷门碰撞：存在一个概率多项式时间的算法，输A(HK，TK)卜Z(1七)，一对(m1，?-1)∈M×R，和消息m2∈M，输出r2∈R满足：HHK(ml，?_1)=HHK(m2，r2)。·语义安全：在给定消息m的陷f]hash值c的情况下，m的条件熵H[mlq等于m的熵日[仇】。换句话说，就是消息m的陷门hash值c没有泄露任何关于m的信息。由上述定义可知，任何不依赖于状态的非交互的陷门承诺方案都可以诱导出一个陷f-]hash方案，其中陷门承诺值对应于陷f]hash值，陷门承诺的绑定性对应于陷f]hash的抗碰撞性，陷门承诺的隐藏性和可模拟性对应于陷f]hash的语义安全性和陷门碰撞性。[30]把陷门承诺分为四类，某些类具有的特性适合于构造性质优良的陷f]hash。一22— 陷门承诺、陷f]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造『281首先指出了陷f-]hash的密钥泄露问题，即一对碰撞会导致陷门密钥的泄露。在变色龙签名中，如果陷f-]hash存在密钥泄露问题，则会影响不可传递性的实现。因为变色龙签名中的不可传递性是由接收者能够任意伪造签名(计算陷f]hash的碰撞)来实现的，如果接收者计算碰撞会导致其陷门信息的泄露，则接收者不敢伪造签名；在在线／离线签名中，如果陷f]hash存在密钥泄露问题，则陷f-]hash值只能使用一次，否则陷门信息的泄露将导致任何人都能伪造签名。从而离线阶段需要计算大量的陷f]hash及对应的签名，大大增加了离线阶段的计算量和存储量，以及在线阶段的通信量。虽然[28]中基于ID的陷f]hash可以认为部分解决了变色龙签名中的密钥泄露问题，但是每次签名都更新接收者的公私钥给密钥管理带来极大的麻烦，是一个平凡的解决办法，完全不适用。陈等人[29]给出了第一个无密钥泄露陷f]hash的完全构造(基于Gap群)，之后，Ateniese和deMedeiros[30]给出了两个基于RSA假设和一个基于Gap群的构造。．无密钥泄露的陷f-]hash函数的构造思想来源于基于ID的陷f-]hash函数，其hash的计算引入了一个标签(或者称为定制身份“customizedidentity”)1，碰撞只泄露一次性胳f’了(通常为对标签的一个签名)，而不泄露长期陷f’了。因此，无密钥泄露陷f]hash函数包含两个陷门，而双陷门承诺常常用于设计无密钥泄露的陷f-Jhash函数或基于ID的陷f-]hash函数。Ateniese和deMedeiros[30]提出是否存在基于ID的无密钥泄露的陷f-]hash函数的公开问题，此问题被陈等人『53]解决。[53]1驹方案包含三个陷门，两个长期陷门为主密钥和ID的私钥，一个一次性陷门为用ID的私钥对标签的签名，同样碰撞只泄露一次性陷门。一个无密钥泄露的陷f-]hash函数包含如下四个有效算法：·KeyGen：输入安全参数1知，输出hash／陷门密钥对(日K，-TK)。·CH：输入hash密钥HK，标签厶消息m和随机数r，输出～个固定长度的比特串C，记为C卜CH(HK，Lm，r)。·UF：输入陷门密钥丁K，标签厶消息m，随机数r和消息m7，输出r7，满足CH(HK，L，仇，r)=C=CH(HK，L，m7，r’)，记为r’卜UF(rK，L，m，r，m7)。1定制身份按照约定的方式每次变化，如三=日(儿‰。de，ff加Re。。池，ff，所，∽。础i。)。一23． 陷门承诺、陷f-]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造·IF：输／k．(HK，L，m，r，m7，7’，)，其中C=CH(HK，L，rn，r)=CH(HK，L，m7，r，)，输出另一对碰撞(mⅣ，∥)，满足C=CH(HK，L，mⅣ，∥)，记为(mⅣ，，)卜IF(HK，L，m，7_，m7，r，)o’无密钥泄露陷f]hash函数除了具有陷f-]hash函数的基本性质之外，还具有无密钥泄露性。在变色龙签名中，一个附加的性质一一原消息隐藏性，将在否认协议中提供对原始签名消息的保护。．·无密钥泄露：对于标签厶如果接收者没有计算陷f-]hashCH(HK，L，仇，r)的碰撞，则不存在有效算法计算其碰撞。即使允许敌手询问预言机UF(TK，·，·，·，．)对(厶，mt，n)的回答多项式次，其中厶≠L。·原消息隐藏：在变色龙签名中，如果接收者用UF(TK，Lm，r’．)计算了一个碰撞(m7，7．7)(伪造签名)，使得CH(HK，L，m，r)=CH(HK，L，m7，r，)，其中m是原始签名消息。则签名者由一对碰撞(m，r)和(m7，r，)，利用IF(HK，L，m，7-，m7，r7)可以计算出第三个碰撞(m，，，，)，从而只需向法官提供(彬，∥)就可以否认对m，的签名，而不需要提供原始签名消息m。更进一步地，原始消息(m，r)的条件熵日[(m，r)IC】并不会因碰撞(m7，r7)和(mⅣ，r，，)的揭露而减小，即：日[(m，r)lC，(m7，，)，(mⅣ，∥)】=日[(m，r)lq。2．8基于具体数论假设的陷门承诺方案的构造本节介绍几个经典实用的基于具体数论假设的陷门承诺，它们是后文构造无密钥泄露的陷f-]hash函数的基础。2．8．1基于离散对数假设的构造在2．4．3节介绍的完美隐藏和计算上绑定的Pedersen承诺的基础上，进一步指出其陷门所在。在2．4．3节中，采用的是公共参数模型，即由可信第三方生成公共参数。在本节中，公共参数采用交互的方式生成，无需可信第三方。接收者运行IndexGen(1忆)实例化·24· 陷门承诺、陷f-]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造一个随机的群砟，并得到一个g阶子群Gg∈殇，生成元为夕，其中弘g为素数，ql(p一1)。接收者选择一个秘密z∈Rz：，计算h=旷，并把公共参数妇，g，夕，^)发送给发送者。‘发送者检查参数的正确性(p，q为素数，ql(P一1)，g，h∈z：一．[1)，gq=hq=1roodp)。在承诺阶段，发送者随机选择r∈RZ。，计算对消息m∈呱∈Z。的承诺为C=gmhr。在打开阶段，发送者传送m，r给接收者，接收者验证m，r∈Zg以及C=gmh’，如果成立，则接收者接受此承诺。方案是计算上绑定的，由两个不同的打开m，r∈Zq和m7，r7∈Zq可以得到^关于夕的离散对数：logoh=(m—m，)(7．7一r)～。反之，离散对数lo岛九即为陷门密钥，拥有陷门，承诺C=gmhr可以打开为任意消息m7：，=r+(1099尼)一1(m—m，)roodq容易验证，(仇7，r7)为承诺C的合法打开。下面看看模拟器如何得知陷门密钥(^关于夕的离散对数z)。在公共参数模型中，模型器可以冒充可信第三方生成参数，随机选择z∈RZ：，计算h=旷。而且模拟器生成的参数与可信第三方生成的参数是同分布的。如果采用交互方式生成参数，z由接收者选择，则可以让模拟器与接收者执行一个交互的零知识证明，模拟器可以中止并重置零知识协议的运行，从而能在多项式时间内抽取出z；而由于零知识性，不诚实的发送者不能得到z，因为其不允许重置零知识协议的执行。2．8．2基于RSA假设的构造Okamoto提出了一个基二于=RSA假设的一般承诺方案[541，我们指出其陷门所在。可信第三方运行IndexGen(1n)，输出一个F／,一比特的RSA模数N=加以及素数指数e≥2(n+1)1。可信第三方随机选择z∈冗z知，计算g=z8roodN，公开(Ⅳ，e，夕)为公共参数2。1选择e≥2(n+1)的目的是使指数e与妒(Ⅳ)<2(n+1)互素，并且在不知Ⅳ的分解的情况下也可以验证这一事实。2若由接收者生成上述参数，则发送者可以作如下验证：e为素数，e>2¨1，且夕∈Z≈。一25— 陷门承诺、陷f-]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造在承诺阶段，发送者随机选择r∈RZ≈，计算对消息m∈％∈Z。的承诺为C=gmr8modⅣ；在打开阶段，发送者传送m，r给接收者，接收者验证m∈Z。，r∈ZⅣ，以及C=g,nremodN，如果成立，则接收者接受此承诺。此承诺是完美隐藏的。因为e与妒(Ⅳ)互素，元素的e次方是z≈上的置换，所以承诺值C在ZⅣ上均匀分布，不会泄露任何关于m的信息。此承诺是计算上绑定的。若能找到一对碰撞(m，r)和(m，，r7)(m≠仇7，l仇一m7I∈z：)则：gm一删=(r'／r)e从而得到夕的e次方根z为：z=98～=ga(r7／r)6，其中n，6满足ne+6(m—m7)=1。a，嗵过扩展的Euclidean算法易得。因此在RSA假设下，方案是绑定的。反之，陷门密钥即为g的e次方根z，拥有陷门，承诺C=gmr8可以打开为任意消息m7：r7：rzm—m7roodN容易验证，(m7，r7)为承诺C的合法打开。看看模拟器如何得到陷门密钥(夕∈Z≈的e次方根z)。类似的，在公共参数模型中，模拟器可以冒充可信第三方生成公共参数_[Ⅳ，e，夕)-，随机选择z∈Rz≈，计算g=z8roodN，从而可以完美地模拟发送者。如果采用交互方式生成参数，则可以让接收者提供一个零知识证明，从而模拟器能从中抽取出陷门密钥。2．8．3基于整数分解假设的构造最初的基于整数分解假设的一般承诺方案的构由Damgard[55]提出，一个更详细的讨论见[56】。我们指出其陷门所在。首先我们给出所需的数论结论。令N=舶为礼-比特的RSA模，叼∈．[1，2，⋯，他)是满足77f0—1)Rr／十(q一1)的最小整数，则平方是群Z2”Iz∈Z≈)上的置换。更一般地，平方是群Z2“Iz∈z≈)上的置换，其中Ⅳ是一个佗-比特奇数，而无需是RSA模。·26- 陷门承诺、陷f-lhash函数及其应用研究第2章陷门承诺的相关定义和基本构造令t≥1是可承诺的消息长度的上界。可信第三方生成一个随机的n-LL特RSA模N=册，计算叩一1的上界丁，随机选择X∈Rz≈并计算g=z2件‘roodN，公开(Ⅳ，t，7．，9)为公共参数。。在承诺阶段，发送者随机选择r∈RZ≈，计算对消，gm∈‰∈Z2t的承诺为C=gmr2件。modN；在打开阶段，发送者传送m，7’给接收者，接收者验证m∈Z2t，r∈ZⅣ以及C=gmr2件‘roodN，如果成立，则接收者接受此承诺。此承诺是完美隐藏的。因为7-+t≥77，并且平方是群Q=．【z21IZ∈Rz≈)上的置换，如果r是随机选取的，则承诺值C=gmr2什‘roodN在群Q上均匀分布，所以不会泄露任何关于m的信息。此承诺是计算上绑定的。若能找到一对碰撞(m，r)和(m7，r，)，则：(r7／r)27村=夕(m—m’)=(夕2。)‘m—m7)／2。其中{<亡是满足2‘I(m—m7)的最大整数。因为指数27+。与(m—m’)／2‘是互素的，用上节中的技术，可以得到92。的2r+。次根。由丁+t—i≥7．+1≥叩我们得Ng的2印次根Y。如果生成参数为g=z2”而非夕=z2件‘，则由可和z至少可有1／2的概率分解Ⅳ。反之，陷门密钥即为夕的2(r+t)次根X，拥有陷门，承诺C可以打开为任意消息m7：r，=7-zm—m_，modN容易验证，(m7，r7)为承诺C的合法打开。隐藏性要求g∈Q，上述由可信第三方生成公共参数可以满足此要求，若在平坦模型中由接收者生成公共参数，则发送者可以计算承诺为C=(92“)仇r2件件“roodN(发送者可以检验N是否为奇数)。因为对于任意伽比特奇数Ⅳ，平方是群Q上的置换，所以承诺值C的分布与m无关，完美隐藏性得到保证而无需对参数Ⅳ，7．，g的选择作限定，详见[57]。对绑定性的分析与上述情况类似。看看模拟器如何得到陷门密钥(夕的2下+t次根z)。类似地，在公共参数模型中，模拟器可以冒充可信第三方生成公共参数(Ⅳ，t，7．，9)，随机选择z∈Rz≈，计算g=z2件2modN，从而可以完美地模拟发送者。在平坦模型中，接收者选择公共参数(Ⅳ，t，7．，夕)，则我们首先把夕升为原来的2n次幂，然后增加关于夕的27+‘次根z的零知识证明，从而模拟器能从中抽取出陷门密钥。-27— 陷门承诺、陷f]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造2．9基于一般密码学假设的陷门承诺方案的构造在这一节中，我们将讨论基于更一般假设一一单向函数的陷门承诺方案的构造。我们分别介绍公共参数模型下和平坦模型下的构造。下面介绍的方案都是计算上可模拟的，即陷门模拟器与诚实实体的执行计算上不可区分。与上节中基于具体数论假设的构造不同，上节中的方案都是完美可模拟的。2．9．1公共参数模型．[43]给出了基于Naor比特承诺方案[58]的陷门承诺，其思想来源于[16】。Naorl比特承诺方案假设伪随机发生器存在，而伪随机发生器存在当且仅当单向函数存在[59]。伪随机发生器是一个有效的确定性算法，把短的随机种子扩展为长的输出；而其输出与相同长度的真随机数是计算上不可区分的。令G是一个伪随机发生器，把m比特输入扩展为3佗一比特输出；可信第三方选择一个3n一比特的随机串盯。则公共参数为(G，盯)。在承诺阶段，发送者随机选择种子r∈冗．[o，1)n，计算对比特b的承诺为：c=㈣。盯拦在打开阶段，发送者传送(6，r)给接收者，接收者验证之前的承诺值。，此承诺是计算上隐藏的。由伪随机发生器的伪随机性，接收者无法区分对b=0和对b=1的承诺。此承诺是统计上绑定的。若能找到一对碰撞(o，r)和(1，rI)，贝Ua(r)=a(r7)o盯。但是由于集合∑={G(r)oG(7’，)17’，r’∈{o，1)礼)至多有22n个元素，随机串盯∈fo，1}3竹落入集合∑的概率最多为2一，从而方案是统计上绑定的1。我们看看此承诺的陷门所在。模拟器随机选择ro，r1∈{o，1}n，设置公共参数仃=G(ro)oa(r1)。则陷门信息(ro，r1)。拥有陷门，承诺C=G(绚)可以打开1陷门承诺不一定只存在于计算上绑定的承诺方案中。统计上绑定的承诺方案在某些参数设置下也可能打破绑定性。此处即为一个例子，盯只要落入集合∑中就存在陷门。·28· 陷门承诺、陷f]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造为0或1，即若要打开为0则发送(0，ro)，若要打开为1则发送(1，r1)；前者是显然的，对于后者’，接收者计算G(7．1)oo=C(r1)oC(ro)oG(r1)=G(ro)，与之前的承诺值C相等。与上节中基于具体数论假设的构造不同，一方面，’模拟器的输出与诚实实体的执行是计算上不可区分的(陷门承诺计算上可模拟)，因为随机数盯与伪随机数G(ro)0G(n)计算上不可区分。而上节中的构造都是完美可模拟的；另一方面，公共参数盯只能使用一次。而上节中的构造，公共参数可以重复使用。2．9．2平坦模型上节中的方案也可运行于平坦模型中。在平坦模型中，没有可信第三方生成公共参数。f81提出了对应于[16]中陷门承诺的一个交互式版本，无需可信第三方参与。即采用如下的掷币协议，接收者首先承诺一个3礼．比特长的随机串Q；接着发送者公开一个随机串p∈R．【0，1)3n；最后接收者打开第一步中的承诺为Ol。则公共参数仃被定义为盯：=ao口，从而承诺方案可按上节中运行。陷门模拟器代替发送者按上述步骤执行交互，在接收者打开承诺为Q之后，模拟器可以把协议的执行返回到第一步接收者作出承诺之后，这时，模拟器发送卢=口oC(ro)oC(r1)，卢与随机数是不可区分的；由于接收者的承诺是绑定的，接收者将再次把其打开为Q，此时，盯=Qo矽=G(ro)oG(r1)，从而按照上节所述，承诺G(ro)可以打开为0或1。2．10无密钥泄露陷f-]hash函数的构造正如2．6节中所指出，【43]提出非完全的基于ID的陷门承诺的概念，其公共参数的生成与某个特定的ido有关，从而陷门信息也与特定的ido绑定，拥有陷门，可以任意打开关于ido的承诺；然而，此陷门无法对不同于ido的zd打破绑定性。非完全的基于ID的陷门承诺不符合基于ID的密码系统的要求，无法模拟预言机Extract(．)。从而，非完全的基于ID的陷门承诺不能直接改造为基于ID的陷f-]hash函数[28]，从下面的方案中可以看出他们之间的差别。根据我们在2．6节中对完全的基于ID的陷门承诺的定义，我们把基于ID的陷门承诺与无密钥泄露的陷f-]hash函数联系起来。无密钥泄露的陷f-]hash函一29． 陷门承诺、陷f]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造数与基于ID的陷f]hashi函数类似，可以把ID看成其标签。我们还将指出无密钥泄露陷f]hash函数的构造思路。双陷门的承诺可以用于构造无密钥泄露的陷f]hash函数或基于ID的陷门hash函数，陈等人[53】构造了基于ID的无密钥泄露的陷门hash函数，从而解决TAteniese和deMedeiros【30]提出的公开问题。2．10．1密钥泄露的基于ID的陷门承诺[43]中给出了非完全的基于ID的陷门承诺的形式化定义，类似于陷f3hash函数中采用的名词，我们可以称其为密钥泄露的基于ID的陷门承诺。我们将在本小节的第二部分中看出这一称呼的来源。引入ID，可以把上述基本的陷门承诺方案改造为密钥泄露的基于ID的陷门承诺方案，分别基于离散对数假设、RSA假设和整数分解假设；同时，【43]还给出了基于单向函数的构造。基于离散对数假设的构造我们只给出基于离散对数假设的密钥泄露的基于ID的陷门承诺的例子，基于其他数论假设的构造都具有类似的形式，请参考[43]。‘在参数生成阶段，模拟器选择阶为素数q的群G口∈Z；，并随机选择生成元夕1，93。对某个特定的z如∈Zq，模拟器随机选择z∈RZ口，计算92=行ido鲧。则公共参数为切，q，G口，gl，92，93}。对于m∈‰关于id∈z。的承诺计算为c=(井仍)m踮。其中，由夕产92=鳐，则z=log卯(夕ildoy2，为,对应于i而的陷门密钥，因为关于id0的承诺可以任意打开为r7=r+x(m—m7)modq。．此基于ID的陷门承诺是完美可模拟的，因为由上述，通过陷门密钥z，承诺可以打开为任意值。此基于ID的陷门承诺是计算上绑定的，即使给出陷门信息(id0，X)，也无法找到关于承诺C=(9产92)m9§的碰撞(m，r)和(m7，r，)，其中试≠ido。因为这将推出(夕产夕2)m鲳=C=(9产夕2)m7夕；7，从而贫d一嫱)(m—m7)=毋’+m，)．‘件册)。因为id—td0，仇一mI≠0modq，容易求得夕l关于卯的离散对数lo993gl，这与离散对数假设相矛盾。一30- 陷门承诺、陷f]hash函数及其应用研究第2章陷门承诺的相关定义和基本构造基于ID的陷门承诺的密钥泄露问题上述基于ID的陷门承诺不能直接转换为基于ID的陷f]hash函数，因为其存在密钥泄露问题。我们把对应于z比的陷门密钥记为鼢=log。。(夕}92)，如果敌手得到了对应于idl和zd2的两个陷门密钥，则他可以求出对应于{d3的陷门密钥。由夕idl92=鳝1和夕}292=菇2，两式相除可得夕}1_记2=鳝1吖2，从而得到夕3关于夕1的离散对数，记为乜=l099，93=(ida—id2)(xl—z2)～。从而夕}1仍=鳝1=夕；3朝，进而求得92关于夕1的离散对数，记为k2=logg，92=‰z1一idl。至此，敌手得到了长期陷门密钥TK=(k2，k3)，从而可以计算出对应于任意zd3的陷门密钥z3=logg。(s『_ild392)=(ida+k2)圬1，进而打破对应于其他ID的绑定性。无密钥泄露的陷f-]hash函数(以及基于ID的陷f]hash函数)采用长期陷门和一次性陷门的构造思路。其中，一次性陷门与某个标签L对应，通常为长期陷门对标签L的签名。这样，签名的不可伪造性对应于陷f3hash函数的抗碰撞性；签名抗击适应性选择消息攻击不可伪造性．(UF-CMA)对应于陷f]hash函数的无密钥泄露性，这是因为在无密钥泄露的证明中，敌手可以询问预言机UF(．)，得到异于挑战标签的多项式个签名，但其仍然无法计算关于挑战标签的签名。2．10．2无密钥泄露的陷I'-Jhash函数基于离散对数系统的构造目前没有基于离散对数假设的UF．CMA安全的签名方案，也没有基于离散对数假设的无密钥泄露陷f-]hash函数。陈等人[29]提出了第一个完全的无密钥泄露陷f]hash函数，基于CDHP假设。[30]提出了基于强Diffie-HeUman(SDH)假设[60]的无密钥泄露陷f]hash函数，由多陷门承诺[11]改造而来。陈等人[44]提出了另外两个基于CDHP假设的无密钥泄露陷f]hash函数，分别基于GDH群和非GDH群。下面我们给出f441中基于GDH群构造的无密钥泄露陷f-]hash函数作为例子。·KeyGen：令G是一个阶为q的GDH群，9是群G的一个生成元。令日：{o，1)+一G+是一个抗碰撞的hash函数。随机选择z∈冗殇，计算y=gz。算法输出hash密钥．31． ‘陷门承诺、陷门haSh函数及其应用研究第2章陷门承诺的相关定义和基本构造为日K={G，q，g，H，箩)，长期陷门密钥为TK=z。·CH：输入hash密钥日K，标签L，消息m∈Z口和随机数口∈冗‰，计算7．亏(g口，y。)，输h刍f]hash值为C=CH(HK，L，仇，r)=矿^m，其中^=H(y，L)。·UF：输入长期陷门密钥rK，标签L，消息m∈Z口，随机数r=(g口，旷)和消息m7∈Z口，计算r’=(g∥，∥口，)，其中夕。’=9n^m—m，，Y口7=旷铲(m一竹t，)o容易验证C日(日K，L，m，r)=CHCHK，L，m7，r，)，并且
此文档下载收益归作者所有
