无证书、高效、安全的有向签名方案

沙特国王大学学报高效安全的无对无证书有向签名方案Gayathri Nemani Bhagyaa，Gowri Thumburb，Krishna Rao Ravva Rama Venkataa，Punugu Vasudeva Reddya，a印度维沙卡帕特南安得拉大学工程数学系b印度维萨卡帕特南GITAM大学电子和通信工程系阿提奇莱因福奥文章历史记录：2017年11月17日收到2018年2月26日修订2018年2月28日接受在线发售2018年保留字：公钥密码学无证书签名随机预言安全模型椭圆曲线离散对数问题A B S T R A C T在一个普通的签名方案中，任何人都可以验证签名者所产生的签名的有效性但在签名消息对签名接收者敏感的应用中，签名的公开可验证性是不可取的，例如医疗记录、税务信息上的签名。为了满足这一要求，引入了有向签名的概念。有向签名方案是一种由签名者控制验证能力的签名方案。在不同的密码体制下，人们提出了许多有向签名方案，其中大部分方案都是利用椭圆曲线上的双线性对。但是双线性对的计算是非常昂贵的。因此，使用配对的方案效率较低，并且在实践中不太适用为了提高计算效率和通信效率，本文提出了一个无配对无证书有向签名方案。在椭圆曲线离散对数问题是困难问题的假设下，在随机预言模型下证明了该方案的安全性。我们比较我们的计划与已知的现有计划和效率分析表明，该计划是更有效的。©2018作者制作和主办：Elsevier B.V.代表沙特国王大学这是一CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍数字签名是一种基本的、实用的密码学原语，它为数字通信提供了认证和不可否认性。为了在实际应用中实现数字签名，需要考虑不同的特征和属性，使它们适合不同的用途。数字签名方案有代理签名、盲签名、多重签名、群签名、环签名等。已经在文献中提出了具有不同密码设置的密码系统，例如传统的公钥基础设施（PKI）（Diffe和Hellman，1976）和基于身份的密码系统（Shamir，1984）。传统PKI的安全性是基于证书的，证书由认证机构（CA）签名公钥和私钥，以及用户但是证书管理会导致额外的存储，*通讯作者。电 子 邮 件 地 址 ： gowri. gitam.edu （ G.Thumbur ） ， vasucrypto@andh-rauniversity.edu.in（P.V. Reddy）。沙特国王大学负责同行审查制作和主办：Elsevier计 算 和 通 信 开 销 大 。 与 传 统 的 PKI 相 比 ， 基 于 身 份 的 密 码 系 统（Identity Based Cryptosystem，IBC）（Shamir，1984）不需要任何证书来保证公钥/私钥对的真实性。在这个系统中，用户的公钥是从用户虽然IBC成功地消除了证书的必要性，但它存在固有的密钥托管问题。后来，Al-Riyami和Paterson（2003）引入了一种新的系统，称为无证书公钥密码学（CL- PKC）。该方案既不存在密钥托管问题，也不需要任何证书，可以看作是介于传统PKI和ID-PKC之间的一种模型。1.1. 相关工作在一个普通的数字签名方案中，任何人都可以使用签名者的公钥来验证签名的有效性。但是，在签名消息对签名接收者敏感的某些应用中，签名的公开可验证性是不可取的，例如，医疗记录上的签名、税务信息等。考虑这种情况：假设医院管理局A以数字签名的形式发布了患者的医疗记录。患者希望在其他人无法检查其有效性的情况下唯一地验证该签名，因为否则，他的健康问题将被暴露。过了一段时间，病人也想证明自己病历的有效性，https://doi.org/10.1016/j.jksuci.2018.02.0161319-1578/©2018作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com226G. Nemani Bhagya等人/沙特国王大学学报●2另一家医院治疗。与此同时，医院A也有能力和责任在患者可能不方便的 情 况 下 验 证 这 些 医 院 记 录 。 诸 如 不 可 否 认 签 名 （ Chaum 和Antwerpen，1990）、有限验证者签名（Araki等人，1999）和具有可验 证 性 限 制 的 指 定 验 证 者 签 名方 案 （ Lguillaumie 和 Vergnaud ，2004）似乎不适合这种情况。为了满足这一要求，Lim和Lee（1992）提出了一种新的签名类型，称为有向签名。 在有向签名方案中，签名者将消息上的签名发送给指定的验证者，只有指定的验证者可以直接验证签名，而其他人在没有签名者或指定的验证者的帮助下对消息的有效性一无所知。在遇到麻烦或必要时，签名人和指定的验证人都可以证明任何第三方的签名。有向签名方案在签名消息对签名接收者敏感的实际应用中非常有用。在 Lim 和 Lee （ 1992 ） 提 出 有 向 签 名 之 后 ， Lal 和 Kumar（ 2004 ） 在 2004 年 提 出 了 一 个 基 于 PKI 的 有 向 签 名 方 案 。Laguillaumie等人（2005）在2005年提出了一个通用可转换的2006年，Lu和Cao（2006）提出了一个基于整数分解问题的有向签名方案，2007年，Ismail和Abu-Hassan（2007）提出了一个基于离散对数问题（DLP）的新方案。2009年，Wei等人（2009）提出了一种基于群密钥初始分布的保密群通信有向签名方案2013年Ramlee和Ismail（2013）提出了一种新的基于混合问题的有向签名方案：离散因子分解和离散对数问题，并对其安全性进行了讨论。所有这些方案都是基于PKI的设置。Sun等人（2008）在随机预言模型下利用双线性对提出了第一个高效的基于身份的有向签名方案（ID-DS）2009年，Zhang等人（2009）提出了一种没有随机预言的ID-DS方案。同年，UmaPrasada Rao等人（2009）提出了一种使用双线性对的高效ID-DS方案。2012年，Ku等人（2012）在超椭圆曲线上提出了一种高效的基于身份的有向签名方案。2011年，Wan（2011）提出了第一个利用对的无证书有向签名方案。1.2. 动机现有的基于身份和基于CL的有向签名方案都是利用椭圆曲线上的双线性对设计的最近，基于椭圆曲线密码（ECC）的方案变得流行，因为它们以较小的密钥提供更高的安全性。例如，根据美国国家标准与技术研究所（NIST）的说法，ECC中的160位私钥提供与1024位RSA私钥相同的安全级别。因此，基于ECC的方案具有较短的密钥大小，并且需要较低的计算和通信成本;因此，使用这些小密钥，时间管理、存储空间和带宽消耗变得非常少。但双线性对的计算量是椭圆曲线群上标量乘的20倍。另外，映射到点的哈希函数也是非常昂贵的密码操作。由于配对操作和映射到点散列函数，许多方案在实践中效率较低。因此，在一般的散列函数下，没有双线性对的方案在同样的安全性下，更能达到高效率。基于此，本文重点研究了无证书环境下无对有向签名方案的设计。1.3. 我们的贡献本文的主要贡献如下。i) 在椭圆曲线上提出了一个不需要双线性对的高效无证书直接签名方案。ii) 我们设计了我们的CLDS方案，而不使用椭圆曲线上的双线性对。据我们所知，这是第一个在无证书设置中解决配对自由环境中的直接性的方案。iii) 提出的CLDS方案具有不可伪造性和不可见性。在随机预言模型（ROM）中，在椭圆曲线离散对数问题（ECDLP）的困难性下证明了它.iv) 我们比较了我们的CLDS方案与现有的有向签名方案的计算和通信的角度来看。v) 效率分析表明，所提出的CLDS方案是有效的比所有其他方案在文献中1.4. 组织本文的其余部分组织如下。我们在第2节中提出了一些问题。我们的CLDS方案的安全性和安全性模型在第3节中介绍。在第4节中给出了建议的CLDS方案及其安全性分析。我们的方案的效率分析在第5节中给出。最后第6节对本文进行了总结。2. 预赛本节简要介绍了椭圆曲线的基本概念和复杂性假设，在此基础上设计了所提出的方案，并达到了预期的安全性。2.1. 椭圆曲线群素数有限域Fp上的椭圆曲线E定义为方程y20g [ f 0 G]为椭圆曲线离散对数问题（ECDLP）：给定一个随机实例P，G和Q的生成元为1/4xP，其中x2Zωq;根据PandQ计算x。从P和Q计算x被假设为通过任何多项式时间有界算法是计算困难的。下表1列出了本文中使用的符号及其说明。3. 安全模型本节介绍我们的无配对CLDS方案的语法和安全模型。3.1. CLDS方案建议CLDS计划的正式模型由六个组件组成，其功能描述如下。设置：KGC通过将nZ作 为输入来运行该算法，并生成主密钥和主公钥，并将公共参数列表作为参数发布。G. Nemani Bhagya等人/沙特国王大学学报2272fg2fg表1符号及其描述。符号描述n;s密钥生成中心的安全参数和主密钥p;q素数Fp上的有限域定义在有限域上的zωq包含元素1，2的群。 . . q-1下的加法模q。生成元为P的素数阶椭圆曲线循环群。KGC密钥生成中心椭圆曲线离散对数问题。CLDS无证书定向签名IDs;IDv分别为签名人H1;H2;H3加密单向哈希函数。Di;SKi;PKi具有身份的用户的部分秘密密钥、秘密密钥和公开密钥ADV1; ADV2分别为I型和II型对手。n：Challenger一种使用对手来解决ECDLP的算法DSTG一种用于区分攻击者自适应选择的消息上的有效签名和从签名空间随机抽取的签名的方法。DSTG1;DSTG2DSTG1是I型酶，DSTG2是II型酶。r消息上的签名L1;L2;L3;LCuser挑战者维护的随机预言机的初始空列表椭圆曲线密码体制EUF-CMA对选择消息攻击是不可伪造的● 部分秘密密钥生成：KGC通过将参数、主秘密密钥、ID作为输入来运行该算法，并生成Di。KGC通过安全信道向用户发送部分秘密密钥Di。● 用户密钥生成：以主公钥、ID、Di作为输入，该算法生成用户● 签名生成：该算法由签名者运行具有身份IDs的签名者在给定消息m2f0; 1gω上通过使用参数，签名者的部分秘密密钥Ds;public和签名者的秘密密钥对PKs;SKs;和验证者的公钥PKv。● 直接验证（D.验证）：指定验证人运行此算法为了验证消息m上的签名r，该算法将参数r、PKs、PKv和IDs、IDv作为输入，并且如果r有效则输出● 公共验证（P. Verify）：为了验证消息m上的签名r，该算法将参数r、PKs、PKv、IDs、IDv和由签名者IDs或指定的验证者IDv提供的Aid作为输入，并且如果r有效则输出3.2. CLDS方案正如Shim（2015）所述，基于潜在的对手行为，我们考虑以下类型的对手。1) I型Advertisement：密钥替换攻击：AdvertisementADV1不能访问主密钥，但能够用用户选择的值替换任何用户的公钥。2) 第二类Adwords：恶意KGC攻击：AdwordsADV2不能替换任何用户的公钥，但能够访问主密钥。CLDS方案的潜在不可伪造性可以通过考虑以下两个博弈来定义：针对类型I和类型II对手的博弈I和博弈II。3.2.1. 游戏我这个游戏在挑战者n和对手ADV1之间执行，如下所示。- 验证阶段：挑战者n运行Setup算法，生成系统参数params、主密钥和主公钥。n通过保持s的秘密将它们交给ADV1。- 查询阶段：在此阶段，ADV1对以下Oracle进行查询.揭示部分秘密密钥Oracle：在从ADV1接收到关于ID的部分秘密密钥查询时;n通过将ID作为输入来计算Di ，并将其提供给ADV1。创建用户Oracle：在接收到来自ADV1的查询时;挑战者n通过将ID作为输入来计算PKi，并将其提供给ADV1。Reveal Secret Key Oracle：在接收到来自ADV1的查询之后;挑战者n通过将ID作为输入来返回SKi。替换公钥Oracle：ADV1可以用所需的PK 0i替换当前PKi。Sign Oracle：当ADV1在对于具有消息m 0 ; 1 ω的输入ID s; IDv，用户ID s ; ID v; mn;n返回由用户ID s ; i的当前公钥/私钥签名的有效签名r。D.验证Oracle：在接收到来自对手AD V 1的查询时，如果r有效，则通过提取ID 0vs私钥Dv;SKv来验证r，并返回1。否则返回0。P.验证Oracle：在收到来自对手AD V1的带有IDs;IDv;m;r;n的查询时，验证签名r并返回？如果r无效，则为ADV1。否则，n以签名者IDs或指定的验证者的名义生成一个Aid。然后将Aid转发给ADV1。- 伪造阶段：最后，ADV1输出IDωs;IDωv;mω;rω作为-gery并赢得游戏，如果(i) 伪造的签名rω是有效的。(ii) IDωs3.2.2. 第二这个游戏在挑战者n和对手ADV2之间执行，如下所示。- 询问阶段：在该阶段中，询问者n运行设置算法以生成系统参数params和主秘密密钥和主公共密钥，并将它们转发到ADV2。- 查询阶段：在这个阶段，ADV2自适应地进行以下查询揭示秘密密钥预言机：在接收到来自ADV2的查询之后;挑战者n通过将ID作为输入来返回SKi。创建用户Oracle：在接收到来自ADV2的查询时;挑战者n通过将ID作为输入来计算PKi，并将其提供给ADV2。Signing Oracle：当ADV2对用户ID s; IDv; mω;n进行签名查询时，通过将ID s;IDv和消息m 0; 1ω作为输入，返回由用户ID s ;的当前公钥/私钥签名的有效签名r。D.验证Oracle：在接收到来自对手AD V 2的查询时，如果r有效，则通过提取ID0vs私钥Dv;S Kv：n来验证签名r的有效性。否则返回0。228G. Nemani Bhagya等人/沙特国王大学学报ðÞ2fg2¼3¼ ðÞ3¼ ðÞ3333P.验证Oracle：在接收到来自对手AD V2的带有IDs;IDv;m;r;n的查询时，验证签名r的有效性并返回？如果r无效，则为ADV2。否则，n代表签名者IDs或指定的验证者IDv;并将其转发到ADV2。-伪造阶段：最后，AD V2输出IDωs;IDωv;mω;rω作为伪造签名。ADV2赢得比赛，如果(i) 伪造的签名rω是有效的。(ii) IDωs定义1（不可伪造性）。CLDS方案是EUF-CMA，如果没有概率多项式时间对手（类型I和类型II）具有不可忽略的概率赢得上述两个游戏。定义2（隐形）。CLDS方案的不可见性可以通过考虑以下针对类型I和类型II对手的游戏III3.2.3. 第三这个游戏是在挑战者n和一个不同的DST G1或DST G2之间执行的，如下所示。第二阶段：与游戏I和游戏II相同。第一阶段：在此阶段，挑战者n响应由挑战者DSTG DSTG1或DSTG2提出的查询就像博弈I和博弈II一样挑战：第一阶段结束后，DSTGDSTG1或DSTG2提交IDωs;IDωv;以及向挑战者发送消息mω，条件是(i) IDωv从未被提交给DSTG 1的部分密钥预言机（如在游戏I中）。(ii) I Dωv尚未提交给DST G 2的密钥Oracle（如在游戏II中）。挑战者然后生成随机比特b0; 1并执行以下操作。(i) 如果b1，则n产生签名rω：(ii) 如果b1/40，则n从签名空间中选择一个随机的rω。最后，n将rω发送到DSTGDSTG1或DSTG2：阶段2：如在阶段1中一样，DSTG、DSTG1或DSTG2再次自适应地执行对挑战者n的若干查询，受到以下条件的限制：DST G1无法在I Dωv;和D上运行部分密钥Oracle。 或P. 验证Oracle上的IDωs;IDωv;mω;rω：DST G2 无法在IDωv;和D.Verifiy或 P上运行Secret Key Oracle。验证Oracle上的IDωs;IDωv;mω;rω：猜猜：终于 DSTG1或DSTG2输出a位● 设置：KGC使用安全参数nZ将其作为输入并执行以下操作。1. KGC选择一组具有素数阶q的椭圆曲线点G; G的生成元P;和散列函数H1;H2;H3：f0;1gω！Zωq：2. KGC选择一个随机的s2Zωq作为主密钥，并将系统的主公钥设置为PPub sP：3. KGC将系统参数发布为params<$fq;G;P;PPub;H1;H2;H3g并秘密保存s。● 部分秘密密钥Gen：通过将IDi和系统参数params作为输入，KGC选择随机数ri2Zωq;计算Ri1/riP;h1/riH1/IDi;Ri;PPub和di1/riH1/modq：最后，KGC将部分秘密密钥Di1/riH1/modq秘密地发送给用户。用户验证等式diP¼Rih1iPPub以检查Di的有效性：● 用户密钥生成：具有身份IDi 的用户随机选择秘密值 xi2Zωq;并计算Xi1/4xiP：将PKi/4XiP设置为公钥，并将SKi/4xiP设置为其秘密密钥。● 签名生成：为一个des签名消息m2 f0; 1gω，身份ID为v的签名验证者;身份ID为s的签名者使用他的秘密值xs;部分秘密密钥Ds和公钥指定验证者PKs;PKv;并如下生成签名rs。1. 签名者选择t1;t22Zωq并计算Us<$t1P;V s<$t2P; W s<$U s <$t2Xv和h2<$H2<$m; ID s; IDv; U s; R s <$m和h3<$H3<$m; ID s; IDv;U s; R s; h2<$m：2. 签名者计算ks<$h2ds<$h3t2<$h2xs modq：现在，消息上的签名是rs<$Ws;Vs;ks<$：● D. 验证：给定消息m上的声称签名rs，其中签名者的身份ID s和他的公钥PK s ; R s;被指定验证者的身份IDv和他公共密钥PKvXv;Rv;指定的验证者如下验证签名。计算Yv 1/4Ws-xvVs/4Us=2Xv-xvVs/4Us：计算h2¼H2m;IDs;IDv;Ys;Rs和h3¼H3m;IDs;IDv;Ys;Rs;h2=验证等式：如果等式成立，验证者接受签名rsWs;Vs;ks; 否则拒绝● P. 验证：给定消息m上的声称签名rs <$W s; V s; k s;，签名者身份ID为s;验证者身份ID为v;，任何第三方都可以在签名者或指定验证者的帮助下验证签名的有效性。具有身份IDs的签名者或具有身份IDv 的 指 定 验 证 者 计 算 Aid <$Us<$Yv; ， 然 后 发 送 给 第 三 方（ TP ） 。 TP 计 算 h2<$H2<$m;IDs;IDv;Aid;Rs<$m 和h3<$H3<$m;IDs;IDv;Aid;Rs;h2<$m，然后检查等式P-R-R-1-1-P-Pub-X-1 -2- 1- 1 - 1-V-S保持不变。 如果是，返回1，b02f0;1g：如果b<$b0：4. 建议的无配对在本节中，我们提出了我们的高效CLDS方案，我们证明了它的安全性。4.1. CLDS方案如3.1节所述，我们的CLDS方案由以下六个算法组成。这些算法的功能如下所示。图1展示了所提出的CLDS方案的过程。否则0.建议方案的正确性：该方案的正确性可以通过以下方式验证。ksP-2018年12月28日，2018年12月282018年12月22日，2018年12月222018年12月21日，2018年12月211/4小时3t2P1/4小时-3¼Vs：1G. Nemani Bhagya等人/沙特国王大学学报229图1.一、CLDS方案的示意图4.2. 我们的CLDS计划下面我们将分析CLDS方案的安全性。我们证明了我们的CLDS方案的不可伪造性和不可见性由以下两个定理。4.2.1. 对I型和II型对手的不可伪造性定理1.所提出的CLDS方案是随机预言模型下的EUF-CMA，假设ECDLP是困难的。我们借助下面的引理1和引理2证明定理1。引理1. 在随机预言机模型中，如果存在一个I型预言机，对于i-1，2，3，q的随机预言机H i，Cuser查询到创建用户请求预言机，qRpsk查询到揭示部分秘密密钥提取预言机，qRsk揭示秘密密钥提取查询和q签名签名查询，qDVerifyD.验证查询和qP验证P。验证查询，然后ECDLP可以解决。证据设n是ECDLP挑战者，并被给定G中ECDLP问题的随机实例，对于随机选择的s2Zωq：其目标是计算s：设AD V1是与n交互的I型对手，如在博弈I中建模的。现在我们证明了n可以用ADV1求解ECDLP：在仿真过程中n需要猜测ADV1的目标身份：不失一般性，n以IDω为目标身份saryADV1谁可以伪造签名后，使qHi查询来在消息mω上的ADV1：230G. Nemani Bhagya等人/沙特国王大学学报3我¼ ðÞ3我¼ ¼ ¼¼我1我1Sv我我我我我1我我 2我3我我我1我我 2我3我- 第 二 阶 段 ： 算 法 n 设 置 PPub<$Q<$s P 并 运 行 Setup 算 法 生 成params：n，然后将params和主公钥交给ADV1并秘密保存s。- 查询阶段：在这个查询阶段，n按照以下方式回答ADV1执行的一系列预言家H1H1IDi;Ri;PPub预言：nmaintainsanini-基本上为空的列表L1，并且具有形式为“IDi;Ri;PPub;l1i”的元组：当 ADV1 对 IDi;Ri;PPub;l1i“ 进 行 H1 查 询 时 ， 将 检 查 元 组IDi;Ri;PPub;l1i”是否在列表中。如果这个元组存在于L1中，则n返回l1i：否则，n随机选择l1i并添加到L1：最后，n返回l1i：在OracleH2H2m;IDs;IDv;Us;Rs：n上，初始空表L2和具有形式的元组签名Oracle：当ADV1使用验证者IDv;n对Oracle ID s ;mi进行此查询 时 ，首 先 对 H1;H2;H3 进 行 查 询 ， 并 分 别 从L1;L2;L3恢复元组ID i ; R i ; P Pub ; l 1ii;m; IDs;IDv;Us;Rs;l2ii;m ;IDs;IDv;Us;Rs;l2i;l 3 ii，以及从L PSK和PSK ID i ; x i ; PK i i; n生成元组Vir1iP-Ril1iPPubXil2il-1;Uir2iXvand Wir2iP：n返回ri 1/4Wi;Vi;ki至ADV1：注意，以这种方式生成的riWi;Vi;ki满足验证方程ki P-D.验证Oracle验证DVID验证码： W母鸡 ADV提交m;IDs;IDv;Us;Rs;l2in ： 当 ADV1 对检 查是 否元 组m;IDs;IDv;Us;Rs;l2iin 是 否 在 列 表 中 。 如 果 这 样 的 元 组m;IDs;IDv;Us;Rs;l2i存在于L2;n中，则返回l2i：否则，n选秀权一随机l2i2Zωq和返回l2i：n添加ID s;IDv;m和 Ri ¼ ðW i；V i；k iÞ到n;n首先恢复从L1列表中检索IDv;Rv;PPub;l1，然后如下进行i)如果I Dv- I D ω，则n计算U i 1/4 x v W i，并从L2和L3列表中恢复条目12 i 1/4 H 2 m ; ID s; ID v ;U i ; R i n和13 i 1/4 H 3 m ; ID s ; ID v ; U i ;R i ; 12 i n。如果这些条目A;IDs;IDv;Us;Rs;l2iA到L2：不存在，n选择l2i;l3i2Zωq 并且限定OracleH3上的查询H3m;IDs;IDv;Us;Rs;l2i：n维护一个初始为空的列表L3，并具有形式为m;ID s;IDv;U s;R s;l2 i;l3 i的元组：当ADV1对m;ID s;IDv;U s;R s;n进行H 3查询时，将检查元组m; ID s; IDv; U s;R s; l2 i; l3 i是否在列表中。 如果元组存在于L3 上，则n给出l3i：否则，n随机选取l3i2Zωq并返回l3 i：最后，n将L 3 im; ID s; IDv; U s;R s; l2 i; l3 ii添加到L3：显示部分秘密密钥预言机 （ Oracle ）PSKi i 否则，如果IDi 并设置di;i; a i，并将ID i;di;R i; i添加到L PSK，并返回di：如果IDi¼IDω;n中止。CreateUserOracle创建用户数据库：Torespond创建用户数据库-cle ID i; n保持初始空列表LCuser，并且具有H2μm;IDs;IDv;Ui;Riμl2i和H3m;IDs;IDv;Ui;Ri;l2i1/3i：n然后验证等式。（1）有ri¼Wi;Vi;ki如果r有效，则返回1;否则返回0。ii)如 果 IDv<$IDω;n 对 所 有可 能对 于 某 些 Ui ， 条 目H2m;IDs;IDv;Ui;Ri和H3m;IDs;IDv;Ui;Ri;l2i：a)对 于 每 个可 能 的 条 目 H2m;IDs;IDv;Ui;Ril2i 和H3m;IDs;IDv;Ui;Ri;l2il3i ，对于某个Ui;n，计算等式（1）并向ADV1返回1（如果ri有效）或0（如果ri无效）：b)如果上述操作没有导致n返回ADV1的答案;n则向ADV1返回0（无效）：P. 验证Oracle OraclePIPV的PIPVID验证：ADV提交PIPVID;ID;m验证和形式为PcIDi;xi;PKii的元组：当ADV1对CuserPcIDi进行查询时，n搜索列表LCuser并输出PKi（如果先前已经进行了查询否则，n如下所示i)如果IDiai;bi;xi2Zωq 且集合Ri<$aiP-biPPu b;H1<$iDi;Ri;PPub <$i1/4 b i andX i/4x i P：n设置PK i/4x iX i;R ii，并将RIDi;R i; P Pub; b i添加到L1，并将RIDi; x i; PK i添加到L Cuser：n将PK i返回到ADV1作为响应。注意，以这种方式生成的Ri;Xi;h1i满足等式diP1Rih1iPPub：Ri 1/4Wi;Vi;ki=n：然后执行相同的过程如D。验证Oracle。唯一的区别是;当n个判断ri 1/2Wi;Vi;ki1有效时 （ 即 ，在 D 中 返 回 1 。 Verify Oracle ） ; 它 将Aid_U_i_r_2_i_X_v_x_v_W_i_v_Y_i_say_t返回给 ADV1 ：当n判断r_i_v_i_W_i;V_i;k_i 在 D 中 返 回 0 。 验 证 Oracle ） ; 它 返 回 ？ADV1：- 伪造： 最 后 ADV1 输 出 IDωs;IDωv;mω;rωi作 为 它 的 伪造， 其 中rωi1/4W ωi;V ωi;kωi：如果I Di- I D ω s ; n停止模拟。否则，n查找LPSKLCuser分离的 令r1 W1;Vi;k1表示riW i;Vi;ki：ii)如果ID i<$IDω;n生成三随机数ai;bi;xi2Zωq与集合Ribi andXi<$$> xi P：n集合PKi<$$>Xi;Ri<$并添加根据分叉引理（Pointcheval和Stern，2000年），如果我们有一个重播n与相同的随机磁带，但不同的选择，H2;H3;ADV1将再推出三个RjWj;V i;kj返回到L1的RIDi;Ri;PPub;bi和LCuser：n的RIDi;xi;PKi我我我2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 19。PK i对ADV1的应答。.kjP-RljPX对于j1; 2; 3; 4：显示密钥Oracle_RSK_ID_i_n：当AD V1对RSK_ID_i_n进行此查询时，如果ID_i_ID_n中止。其他方面，如果I Di- I D ω ; n分别从L Cuser ; L PSK找到元组I D i ; xi; P K i; P I D i ; di; R i i;并且恢复xi; di：n设置SK i; di; xi;并将SK i返回到ADV 1：如果不存在对应的应答元组在L Cuser;L PSK;n让一质疑我们现在用ri;xi;s;vi表示Ri; Xi; P Pu b ; Vi的分别地，即， Rir1iP;XixiP;PPubs P;V iv iP：从由上述方程，我们得到以下四个线性无关的方程。.kj-rljsxljl-1jvij，j1;2;3;4：Cuser_ID_i= i，以生成xi，并且对PSK_ID_i = i进行查询以生成di：n，将这些值分别保存在L_Cuser;L_PSK中。最后n返回SKi：ReplacePublicKeyOracleRRP KI Di替换：当对手对RPKRPKID i进行查询时;n在L Cuser中找到RPKID i;x i;PK i替换P Ki¼P K 0i和xi¼？：从四个方程中，n求解未知的n个值ri;xi;s;vi ，并输出s作为ECDLP的解。引理2. 在随机预言机模型中，如果存在一个第二类攻击者ADV2，他可以在进行q次Hi查询酒我G. Nemani Bhagya等人/沙特国王大学学报2313我¼ ðÞ¼ ¼ ¼¼ðÞ我我我我我我我我我1我我 2我3我Ki - ril1i s al2iQl3i<$viforj< $1; 2;3：对于i-1，2，3，q ，对创建用户请求oracle的Cuser查询，q， Rsk，Reveal，密钥提取查询和q，Sign ，Sign查询，q，DVerifyD.验证查询和q P验证P。验证查询，然后ECDLP可以解决。证据设n是ECDLP挑战者，并被赋予随机签名Oracle：当ADV2使用验证者IDv;n对Oracle ID s ;m进行此查询时，首先对H1;H2;H3Oracle进行查询，并分别从L1;L2;L3恢复元组IDi;Ri;PPub;l1i;m;IDs;IDv;Us;Rs;l2i;m ;IDs;IDv;Us;Rs;l2i;l3i，并从LCuser：n恢复元组IDi;xi;PKi，生成两个随机数ri;r2i2Zω和集ki ril2i;Vil1iPPubXil2il-1;对于一个随机选择的a2Zωq，它的目标是计算a：假设AD V2是一个与n交互的II型对手，如博弈II中所建模的。现在我们证明了n可以使用ADV2求解ECDLP：在模拟过程中n需要猜测ADV2的目标身份：在不损失一般性的情况下，n将IDω作为消息mω上ADV2的目标身份：U i<$r2 iXv和W i<$r2 iP：n返回ri 1/4Wi;Vi;ki至ADV2：注意，以这种方式生成的riWi;Vi;ki（一）.D.验证Oracle最后一个问题：W母鸡ADV2将ID_s;ID_v; m_i和r_i_v_i提交给n;该算法从L1列表中恢复ID_v; R_v; P_Pub;11_i，并如下进行。i)如果IDv- 搜索阶段：算法n设定P 简体中文sP并运行安装程序ID s;IDv;U i;R i;l2 i从L2&L3列表中删除。如果这些条目并不存在时，然后n选择生成参数的算法：n然后将参数和主密钥提供给ADV2：-查询阶段： 在此查询阶段，n以以下方式回答ADV2执行的一系列在OracleH1上运行的OracleH1中，OracleIDi;Ri;PPub：n维护一个ini-基本上为空的列表L1，并且具有形式为"IDi;Ri;PPub;l1i“的元组：当ADV2对 IDi;Ri;PPub;l1i” 进 行 H1 查 询 时 ， 将 检 查 元 组IDi;Ri;PPub;l1i“是否在列表中。如果这个元组存在于L1中，则n返回l1i：否则，n随机选择l1i并添加到L1：最后，n返回l1i：在Oracle H 2上运行H2m;ID s;IDv;U s;R s：n维护一个初始为空的列表L2，并具有形式为m;ID s;IDv;U s;R s;l2 i的元组：后接收H2查询onm;IDs;IDv;Us;Rs如果元组m;IDs;IDv;Us;Rs;l2i存在于L2;n上，则返回l2i：否则，n选取随机l2i2Zωq并返回l2 i：n将m;IDs;IDv;U s;R s;l2 ii添加到L2：在OracleH3上运行H3n n nm;I Ds;I Dv;Us;Rs;l2in n：n维护初始空列表L3;元组的形式m;IDs;IDv;Us;Rs;l2i;l3i查询如果元组存在于L3 上，则在H3n=m;IDs;IDv;Us;Rs;l2in;n上给出l3i：否则，n选取随机l3i2Zωq;并返回l3i和nl2i;l3i2Zωq 并定义H2m;IDs;IDv;Ui;Ril2i和H3m; ID s; IDv; U i;R i; l2 il3 i：n，然后验证ril3 i;V i;k i的有效性，如果ri有效，则返回1，其他-wise它返回0到ADV2：ii)如果IDv<$IDω;n适用于所有可能的对于某些Ui，条目H2m;IDs;IDv;Ui;Ri和H3m;IDs;IDv;Ui;Ri;l2i：a)对于每个可能的条目H2m;IDs;IDv;Ui;Ri1/2i 和 H3m;IDs;IDv;Ui;Ri;1/2i 和 1/3i ， 对 于 某 些Ui;n，计算等式（一）.如果验证结果为1（有效），则n向ADV2返回1（有效）：b)如果上述操作没有导致n返回ADV2的答案;n则向ADV2返回0（无效）：P. 验证Oracle验证：AD V2将验证IDs;I Dv;m和ri¼ IDW i;V i;k i提交给n：然后执行与D中相同的过程。验证Oracle。唯一的区别是：当n个判断ri1 =W i;V i;k i1是有效签名时（即，在D中返回1。Verify Oracle）;它返回Aid <$U i<$r2 iXv<$xvW i<$Yisay到ADV：当n个判断r1/r2/W;V;k=无效时（即，添加了字符串m;ID;ID;U;R;l ;l 我是L：2ii我我svsS2我3 i3在D中返回0。验证Oracle）;它返回？ADV2：CreateUserOracleCuserrCuserIDi创建：n维护一个最初为空的列表LCuser;它包含形式为CuserIDi;xi;PKi的元组：当ADV2对CuserIDi进行查询时，算法n检查列表LCuser，如果请求具有被制成之前否则，n是否-伪造：最后ADV2输出IDωs;IDωv;mω;rωi 作为它的伪造，其中rω1=W ω;V ω;kω2：如果I Di- I D ω s ; n停止模拟。否则，n分别向上查找LCuser。 令r1W1;Vi;k1表示rW i;Vi;ki：以下.i)如果IDi发电公司 两 随机数字ri;xi2Zω和计算R i i P; H1βIDi;Ri;P出版物分叉引理（Pointcheval和Stern，2000），如果我们有一个用相同的随机磁带重放n，但选择不同的H2;H3;ADV2将再推出三个RjWj;V i;kjQh1 i和X i¼x i P：n集PK i¼X i;R i并添加我我我2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 19。H1i=H1i并且，将RQIDi;xi;PKi映射到LCuser：n将PKi作为响应返回给ADV2.kjP-RljPX对于j1; 2; 3：ii)如 果IDi1/IDω;n 生 成 随机数r