具有否认认证的SM9标识加密算法.pdf

计算机科学与探索Journal of Frontiers of Computer Science and Technology1673-9418/2023/17(10)-2519-10doi:10.3778/j.issn.1673-9418.2207013具有否认认证的SM9标识加密算法赵晨阳1，柯品惠2+，林昌露21.福建师范大学 计算机与网络空间安全学院，福州 3501172.福建师范大学 数学与统计学院，福州 350117+通信作者 E-mail:摘要：SM9标识加密算法是我国自主设计的商用标识加密算法，它已成为国内标识加密算法行业的标准，并被广泛应用于诸如电子邮件、电子投票和网上谈判等。然而SM9标识加密算法不能有效保护发送者的身份隐私。为此，基于SM9标识加密算法，并结合否认认证协议，提出具有否认认证的SM9标识加密算法。该算法允许发送者在协议运行后否认其参与，只有预期的接收者可以识别给定消息的真实来源；与此同时，接收者不能使任何其他第三方相信消息是由特定发送者发送的。在DBDH困难问题假设下，给出具有否认认证的SM9标识加密算法的形式化定义和安全模型，并在随机预言模型下给出算法的安全性分析，证明该算法可同时满足否认性、保密性和否认认证性。理论分析和仿真实验表明，该算法不仅保持了SM9标识加密算法的效率优势，而且计算开销低于其他具有否认认证的标识加密算法。关键词：SM9；标识加密；否认认证；双线性对文献标志码：A中图分类号：TP309SM9 Identity-Based Encryption Algorithm with Deniable AuthenticationZHAO Chenyang1,KE Pinhui2+,LIN Changlu21.College of Computer and Cyber Security,Fujian Normal University,Fuzhou 350117,China2.College of Mathematics and Statistics,Fujian Normal University,Fuzhou 350117,ChinaAbstract:SM9 identity-based encryption algorithm is a commercial identity-based encryption algorithm independentlydesigned by our country,which has become the standard of the domestic identity-based encryption algorithm industry,and is widely used in e-mail,electronic voting and online negotiation,etc.However,SM9 identity-based encryptionalgorithm can t effectively protect the identity privacy of the sender.Based on SM9 identity-based encryptionalgorithm,combined with the deniable authentication protocol,this paper proposes SM9 identity-based encryptionalgorithm with deniable authentication.This algorithm allows the sender to deny its participation after the protocolruns,and only the intended receiver can identify the true source of the given message.At the same time,the receivercant convince any other third party that the message is sent by a specific sender.Under the assumption of DBDHsdifficult problem,the formal definition and security model of SM9 identity-based encryption algorithm withdeniable authentication are given,and the security analysis of the algorithm is given under the random oracle model,which proves that the algorithm can satisfy denial,confidentiality and deniable authentication at the same time.Theoretical analysis and simulation experiments show that the proposed algorithm not only maintains the efficiency基金项目：国家自然科学基金（61772292，61772476）；福建省自然科学基金（2019J01273）。This work was supported by the National Natural Science Foundation of China(61772292,61772476),and the Natural Science Founda-tion of Fujian Province(2019J01273).收稿日期：2022-07-05修回日期：2022-10-14Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(10)标识加密算法（identity-based encryption，IBE）是一种特殊类型的公钥加密算法，它允许用户使用任意标识作为公钥，例如电子邮件地址、电话号码和身份证号码等。在IBE算法中，数据发送者不必获得接收者的公钥证书，即不需要公钥基础设施（public keyinfrastructure，PKI）。2001年，Boneh和Franklin1提出第一个实用且可证明安全的基于双线性对的标识加密方案。随后，研究者对标识加密算法进行了深入研究，基于双线性对提出了更多实用的 IBE算法2-4。虽然标识加密算法研究取得了积极进展，但标识加密算法大多以国外算法为主。为实现信息自主可控，我国自主设计了一系列中国国家标识密码标准。SM95就是其中一个有代表性的密码标准，它包括 3个组成部分：数字签名算法、密钥协商算法和标识加密算法。SM9标识加密算法于2016年成为我国商用密码标准，2020年成为国家标准。随着 SM9算法在密码技术领域占据愈来愈重要的国际地位，我国学者对SM9算法进行了深入研究，如文献6-10。虽然 SM9-IBE 是一个标准算法，但在一些特殊场景中，比如电子邮件系统、电子投标、电子投票和网上选举等，它不能很好地保护发送者的身份隐私。基于此，本文结合SM9算法添加否认认证协议，提出具有否认认证的 SM9标识加密算法，保护发送者的身份隐私，满足上述应用场景的现实需要。与传统的认证协议相比，否认认证协议具有以下两个特点：（1）协议主体可以在协议运行后否认自己的参与，只有目标接收者可以验证给定消息的来源；（2）即使接收者与第三方充分合作，也不能使任何第三方相信消息是由特定的发送者发出的。1998年，Dwork等人11首先提出了一个基于零知识的否认认证协议。之后，Aumann和Rabin12提出了另一个基于因子分解的方案，它需要一个通信双方都信任的公共目录。2001年，Deng等人13在Aumann和Rabin定义的模型下，分别提出了两个基于因式分解和离散对数问题的否认认证协议。2005年，Cao等人14利用双线性对提出了一个高效的非交互式、基于身份的否认认证协议。此外，该方案通过使用对称加密算法实现了保密性。然而，在 2006 年，Chou 等人15指出 Cao等人的方案易遭受密钥泄露伪装（keycompromise impersonation，KCI）攻击。随后 Chou 等人提出了一种新的基于身份的否认认证协议，并声称该协议是安全的。然而，2007年，Lim 等人16证明Chou等人的方案仍易受KCI攻击，其也是不安全的；此外，他们提出了一个增强的方案。然而在2009年，Tian等人17指出，Lim等人修复的协议在特殊的攻击下仍然不安全。2014年，Li等人18提出了一种高效的基于身份的否认认证协议。更重要的是，他们给出了其协议的安全模型和形式化证明，并声称他们的协议满足批量验证的要求，而且比所有已知的基于身份的否认认证协议更快。2015年，Wu等人19提出了一种高效的基于身份的否认认证加密方案，该方案在不可否认性、保密性和否认认证性均得以保证。2019年，Huang等人20提出了一种有效的保护隐私的否认认证加密方案，该方案在不可否认性、机密性和否认认证性的基础上对数据的完整性也提供了保证。2020年，Kar21提出了一个无证书环境下的否认认证加密方案，该方案既没有密钥托管问题，也不需要公钥证书。为了达到一定的安全性，上述方案大多基于安全参数较大的对称双线性对，并且在方案中多次使用双线性对，导致方案的计算效率下降。而 SM9-IBE算法采用安全参数小的非对称双线性对，用户的公钥和私钥分别由两个不同的循环群生成，因此安全强度更高。本文工作：首先定义 SM9-DAIBE（SM9 identity-based encryption of deniable authentication）算法的安全模型，然后利用双线性对提出具体的 SM9-DAIBE算法。接下来，在 DBDH（decisional bilinear Diffie-Hellman）困难问题假设下，在随机预言模型中给出了算法的安全性证明。相对 SM9-IBE 算法，本文提出的SM9-DAIBE算法可同时具有以下特性：（1）保密性：该属性确保只有目标接收者可以与发送者共享所传输的消息，任何第三方都不能获得所传输的密文。（2）否认性：消息的发送者可以在之后否认其曾传输过该消息，甚至否认参与了通信。同时，目标接收者可以识别给定消息的真实来源，但是接收者不能向任何其他第三方证明这一事实。advantage of SM9 identity-based encryption algorithm,but also has a lower computational overhead than otheridentity-based encryption algorithms with deniable authentication.Key words:SM9;identity-based encryption;deniable authentication;bilinear pairing2520赵晨阳 等：具有否认认证的SM9标识加密算法（3）否认认证性：该属性确保发送消息主体实际上是真正的发送者，而不是另一个第三方或对手。1基础知识1.1符号说明设A和B为比特串，A B表示A和B的按位异或运算，A|B表示A和B的级联。zP表示加法群中元素P的z倍，gr表示乘法群中元素g的r次幂。如果A是一个概率算法，那么y A(x)表示输入x，将算法A的输出赋值给y。表 1给出了 SM9算法中用到的密码函数的符号表示。1.2双线性群设N为素数，令G1和G2为两个N阶加法循环群，GT为N阶乘法循环群，P1和P2分别是群G1和G2的生成元。定义e:G1G2 GT为双线性对映射，则e:G1G2 GT应满足以下三条性质：（1）双 线 性 性。对 于a,b1,N-1，都 有e(aP1,bP2)=e(P1,P2)ab。（2）非 退 化 性。若P1和P2不 是 单 位 元，则e(P1,P2)也不是单位元。（3）可计算性。对于P1,P2，存在一个高效的多项式时间算法计算e(P1,P2)。特别地，若G1=G2，称为对称双线性群；否则称为非对称双线性群。SM9标识密码算法以非对称双线性群为构造基础。令G(1)表示一个双线性配对群生 成 算 法。该 算 法 以 安 全 参 数1作 为 输 入，以(e,G1,G2,GT,N,P1,P2)元组作为输出。1.3基于双线性对的困难问题及假设DBDH 问题：在双线性对映射e:G1G2 GT中，令P1 G1，P2 G2，P3 GT，对于一个给定元组Y=(P1,aP1,bP1,P2,bP2,cP2,P3)以及0,1，若可以计算P3=e(P1,P2)abc，则令=0，否则令=1，判定的值。这里a、b、c均为未知整数。DBDH假设：对于任意一个概率多项式时间攻击者A，计算DBDH问题的概率都是可以忽略不计的，即Pr0 A(Y)|=0-Pr0 A(Y)|=1是可以忽略不计的。1.4SM9-IBE算法本节回顾 SM9-IBE 算法，该算法由以下几个步骤构成：（1）系统参数。密钥生成中心生成一个双线性配对群G=(e,G1,G2,GT,N,P1,P2)，选择一个随机元素ke ZN作为系统主私钥，并计算Ppub-e=keP1和u=e(P1,P2)ke。令H(ID)=H2RF1(Hv,ID,N)及hid=3。最后生成系统参数param=(G,Ppub-e,u,H,hid)并公开，系统主私钥ke秘密保存。（2）密钥提取。给定用户的身份标识ID，密钥中心计算用户密钥deID=keke+H(ID)P2。（3）消息加密。对于消息M和身份标识ID，选择 一 个 随 机 元 素r ZN，首 先 计 算QB=Ppub-e+H(ID)P1，再计算密文C1=rQB，C2=K1 M，C3=Hv(C2|K2)，其中K1|K2=KDF(Hv,C1|t|ID,|M|+v)，t=ur。（4）密文解密。对于密文(C1,C2,C3)，首先根据私钥deID计算t=e(C1,deID)，再根据 KDF 计算K1|K2=KDF(Hv,C1|t|ID,|M|+v)。若Hv(C2|K2)=C3，则返回消息M=K1C2；否则，返回错误符号。2具有否认认证的SM9标识加密算法2.1SM9-DAIBE算法的系统模型SM9-DAIBE算法的系统模型包含以下三个实体（见图1）：（1）密钥生成中心（key generation center，KGC）：负责生成系统参数和主私钥，同时为用户（包括数据发送者和数据接收者）提供私钥。（2）数据发送者（data sender，DS）：对消息进行否认认证加密，形成认证器密文发送给数据接收者。（3）数据接收者（data receiver，DR）：从收到的认证器密文中计算出原始消息，并能确认消息的来源。2.2SM9-DAIBE算法的形式化定义本节给出新的SM9-DAIBE算法，该算法由以下四个算法组成：（1）系统参数生成算法 Setup（1）。该算法由密表1SM9算法的函数使用说明Table 1Description of use of functionsfor SM9 algorithm函数表示符号HvH2RF1(Hv,Z,p)KDF函数类型密码杂凑函数密码函数密码函数函数输入任意比特串杂凑函数Hv，比特串Z和整数p杂凑函数Hv，比特串Z和整数l函数输出v比特整数h 1,p-1比特串K(0,1)l2521Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(10)钥生成中心负责执行。输入一个安全参数，通过运行算法返回系统参数param和系统主私钥ke。密钥生成中心秘密保存系统主私钥ke，公开系统参数param。（2）用户密钥提取算法 Extract（ID）。该算法由用户和密钥生成中心交互执行。用户将自己的身份标识ID发送给密钥生成中心，密钥生成中心对收到的身份标识ID进行合法性验证，验证通过后用系统主私钥计算身份标识ID对应的私钥deID并通过安全信道发送给用户。同时，用户根据系统公开参数计算自己的公钥并公开。（3）否认认证加密算法 DAEnc(M,deS,IDS,IDR)。该算法由数据发送者负责执行。根据消息M、发送者私钥deS、发送者和接收者的身份标识IDS和IDR，数据发送者计算消息M的认证器密文后将其发送给数据接收者。（4）否认认证解密算法 DADec(,deR,IDR)。该算法由数据接收者负责执行。收到数据发送者发送的认证器密文后，数据接收者根据自己的私钥deR和身份IDR，恢复出消息M，同时确认消息是否为数据发送者发送。若是，接收消息M；否则，输出错误符号。2.3SM9-DAIBE算法的安全模型（1）SM9-DAIBE算法的保密性SM9-DAIBE算法的保密性的安全性概念称为抗适应性选择密文攻击的密文不可区分性（ciphertextindistinguishability against adaptive chosen ciphertextattacks，IND-DAIBE-CCA）。下面给出 IND-DAIBE-CCA的游戏定义。初始化阶段 算法B输入一个安全参数，运行系统参数生成算法 Setup（1），返回系统参数param和系统主私钥ke，其中系统参数param发送给攻击者A，系统主私钥ke秘密保存。询问阶段1A以如下自适应方式执行多项式有界数量的用户密钥提取查询、否认认证加密查询和否认认证解密查询。用户密钥提取查询。当攻击者A要查询标识ID的私钥时，挑战者B运行用户密钥提取算法Extract（ID）获取对应用户的私钥deID，并将其发送给攻击者A。否认认证加密查询。攻击者A选择一个发送者的身份标识IDi、一个接收者的身份标识IDj、一个明文M，并将它们发送给挑战者B。挑战者B首先运行用户密钥提取算法 Extract（ID）获得发送者IDi的私钥deIDi，然后运行否认认证加密算法DAEnc(M,deS,IDS,IDR)，将计算结果发送给攻击者A。否认认证解密查询。攻击者A提交一个DAEnc 认证器密文和一个接收者的身份标识IDj给挑战者B。挑战者B首先运行用户密钥提取算法Extract（ID）获得接收者IDj的私钥deIDj，然后运行否认认证解密算法 DADec(,deR,IDR)，将计算结果发送给攻击者A。挑战 在攻击者A决定询问阶段 1结束时，攻击者A输出两个等长的明文M0、M1，以及之前没有做过用户密钥提取查询的两个标识IDS、IDR一并发送给挑战者B。挑战者B从 0和 1中随机选择一位记为，将=DAEnc(M,deS,IDS,IDR)的计算结果发送给攻击者A作为挑战。询问阶段2 攻击者A可以像询问阶段1一样发出更多的多项式有界查询，但是在这个阶段，攻击者A不能对身份标识IDS和IDR进行用户密钥提取查询。同时，攻击者A也不能对挑战进行否认认证解密查询。猜测 最终，攻击者A输出一比特作为对的猜测。如果=，表明游戏获胜。定义攻击者A在该游戏中的优势为：AdvCA()=|Pr=-12。如果对于任意多项式时间攻击者A，其游戏获胜的优势是可忽略的，即AdvCA()negl()，其中negl()为可忽略函数，则SM9-DAIBE算法满足保密性。（2）SM9-DAIBE算法的否认认证性此处借用数字签名中抵抗适应性选择消息攻击的不可伪造性的概念来定义 SM9-DAIBE 算法的否图1SM9-DAIBE系统模型Fig.1System model for SM9-DAIBE2522赵晨阳 等：具有否认认证的SM9标识加密算法认认证性的安全概念。然而，SM9-DAIBE算法中的安全概念与数字签名算法的安全概念有本质的不同。这是因为在数字签名中，只有具有正确私钥的发送方才有能力生成有效的签名，而在 SM9-DAIBE算法中，发送方和接收方都有能力生成有效的 SM9-DAIBE 认证器密文。SM9-DAIBE 算法的不可伪造性的安全性概念称为抗适应性选择消息攻击的否认认证性（deniable authentication against adaptive chosenmessages attacks，DA-DAIBE-CMA）。下面给出 DA-DAIBE-CMA的游戏定义。初始化阶段 算法B输入一个安全参数，运行系统参数生成算法 Setup(1)，返回系统参数param和系统主私钥ke，其中系统参数param发送给攻击者X，系统主私钥ke秘密保存。攻击阶段 和前面的IND-DAIBE-CCA的游戏定义一致，攻击者X以自适应方式执行多项式有界数量的用户密钥提取查询、否认认证加密查询和否认认证解密查询。伪造阶段 攻击者X输出一个 DAEnc认证器和两个身份标识IDS和IDR。如果同时满足以下三个条件，视为攻击者X游戏获胜。是一个对于发送方IDS和接收方IDR有效的认证器，也就是说，DADec(,deR,IDR)的结果不是一个错误符号。攻击者X没有对IDS和IDR做过用户密钥提取查询。攻击者X没有对消息M和身份标识IDS和IDR做过否认认证加密查询。这里把攻击者X的优势定义为它在游戏中获胜的概率。为了实现SM9-DAIBE算法的否认性，在以上条件的第二步需要攻击者X对IDS和IDR均没有做过用户密钥提取查询，原因是接收者也可以生成一个有效的DAEnc认证器密文。2.4SM9-DAIBE算法的构造SM9-DAIBE算法的具体构造如下：（1）系统参数生成算法 Setup（1）。在输入安全参数后，该算法执行以下操作：密钥生成中心选择一个双线性配对群G=(e,G1,G2,GT,N,P1,P2)。密钥生成中心选择一个随机元素ke ZN作为 系 统 主 私 钥，并 计 算Ppub-e=keP1。令H(ID)=H2RF1(Hv,ID,N)及hid=3。密钥生成中心生成系统参数param=(G,Ppub-e,H,hid)并公开，同时秘密保存系统主私钥ke。（2）用户密钥提取算法 Extract(ID)。在输入用户标识ID后，该算法执行以下操作：给定用户标识ID，密钥生成中心计算用户的私钥deID=ke+H(ID)P2。密钥生成中心通过安全信道将用户私钥deID发送给用户。用户ID根据系统公开参数计算自己公钥QID=Ppub-e+H(ID)P1。注：本文假定发送者和接收者的公私钥对分别是(QS,deS)和(QR,deR)。（3）否认认证加密算法 DAEnc(M,deS,IDS,IDR)。在输入消息M、发送者私钥deS、发送者和接收者的身份标识IDS和IDR后，该算法执行以下操作：数据发送者首先选择一个随机数r N，计算C1=rQs，u=e(QR,deS)，t=ur。利用密钥派生函数KDF，计算K1|K2=KDF(Hv,C1|t|IDR,|M|IDS|+v)，其 中K1和K2的 长 度 分 别 为|M|IDS|比特和v比特。数据发送者计算C2=K1(M|IDS)，C3=Hv(C2|K2)。数据发送者将DAEnc认证器密文=(C1,C2,C3)发送给数据接收者。（4）否认认证解密算法 DADec(,deR,IDR)：在输入认证器密文、接收者私钥deR、接收者的身份IDR后，该算法执行以下操作：数据接收者根据自己的私钥deR计算t=e(C1,deR)。数据接收者利用 KDF计算出K1|K2=KDF(Hv,C1|t|IDR,|M|IDS|+v)。若Hv(C2|K2)=C3，返回M|IDS=K1C2，从而恢复出消息M；否则，返回错误符号。正确性分析：由于C1=rQS，QID=Ppub-e+H(ID)P1，deID=ke+H(ID)P2，有t=e(C1,deR)=e(rQS,deR)=e(Ppub-e+H(IDS)P1,ke+H(IDR)P2)r=e(ke+H(IDS)P1,ke+H(IDR)P2)r=e(ke+H(IDR)P1,ke+H(IDS)P2)r=e(Ppub-e+H(IDR)P1,ke+H(IDS)P2)r=e(QR,deS)r=ur=t因此，数据接收者可以计算出正确的中间密钥K1和K2，进而恢复出原始消息M。2523Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(10)3SM9-DAIBE算法的安全性分析3.1否认性本算法实现了否认性，由于接收者也可以生成有效的 DAEnc认证器密文，而该认证器密文无法与发送者的认证器密文进行区分，原因如下：（1）在收到发送者发来的 DAEnc 认证器密文=(C1,C2,C3)后，接收者通过运行否认认证解密算法，获得恢复后的消息M。之后接收者可以执行以下操作：t1=e(C1,deR)K1|K2=KDF(Hv,C1|t1|IDR,|M|IDS|+v)C2=K1(M|IDS)C3=Hv(C2|K2)该情形下的输出为=(C1,C2,C3)。显然，对于同 一 消 息M，第 三 方 很 难 区 分=(C1,C2,C3)与=(C1,C2,C3)。（2）发送者也可以选择一个随机数r ZN，计算C1=rQS，执行上面（1）所示的过程。该情形下输出为=(C1,C2,C3)，其与=(C1,C2,C3)对第三方来说也难以区分。3.2保密性本文所提 SM9-DAIBE 算法在随机预言模型下满足抗适应性选择密文攻击的密文不可区分性。定理 1 在随机预言模型下，若攻击者A能以优势AdvCA()赢得密文不可区分性游戏（至多进行qH次哈 希 询 问），则 存 在 一 个 算 法B能 利 用A以1qHAdvCA()的优势解决DBDH问题。证明 可以通过 2.3节中定义的密文不可区分性IND-DAIBE-CCA 游戏来证明本文算法的保密性。若存在一个攻击者A可以破解这个算法，则可构造一个算法B来解决DBDH问题。不妨设算法B要解决 的 一 个 DBDH 实 例 元 组 为：Y=(P1,xP1,yP1,P2,yP2,zP2,Z)。在下面的游戏中，B扮演攻击者A的挑战者。初始化阶段 算法B输入一个安全参数，运行系 统 参 数 生 成 算 法 Setup（1），生 成 系 统 参 数param=(G,Ppub-e,H,hid)，其中G=(e,G1,G2,GT,N,P1,P2)为双线性配对群，Ppub-e=keP1且ke未知。挑战者将系统参数param发送给A。询问阶段 1A执行多项式有界次数的以下查询，B对A的查询做如下回答：（1）哈希查询OH(IDi)。首先，B维持一个形如(IDi,ni)、初始为空集的二元列表LH。其次，B选择两个不同的数N1,N21,2,qH。如果IDi是A的第N1(i=N1)次询问，则B回答QN1=Ppub-e+xP1。如果IDi是A的第N2(i=N2)次询问，则B回答QN2=Ppub-e+yP1。对于一个由A给定的标识IDi(i1,2,qH且iN1,N2)，B首先检查列表LH是否存在元素(IDi,ni)。若存在，返回QIDi=Ppub-e+niP1的结果给A。若不存在，则B选择一个随机数ni ZN，将(IDi,ni)添加至列表LH中，并计算QIDi=Ppub-e+niP1作为查询结果返回给A。（2）KDF 查询OK(IDi,ti,li)。首先B建立一个形如(IDi,ti,Ki)、初始为空集的列表LK。当A询问(IDi,ti,li)的输出结果时，B首先检查LK中是否存在形如(IDi,ti,Ki)的三元组。若存在，当|Ki|li时，返回Ki的前li比特。否则，随机选取li-|Ki|长度的比特串K，返回Ki|K给A，同时替换(IDi,ti,Ki)为(IDi,ti,Ki|K)。若不存在，则B询问列表L1（见用户密钥提取查询）中的每个元素对应的哈希列表元素(IDi,dei)。根据dei的取值，B随机选取长度为li的比特串Ki，返回给A，并将(IDi,ti,Ki)添加至列表LK中。（3）用户密钥提取查询。首先，B建立一个形如(IDi,dei)、初始为空集的二元哈希列表L1。其次，B选择一个随机元素r N。当A询问身份标识IDi的私钥时，B首先查询列表L1中是否存在元素(IDi,dei)，并以如下形式返回对应的dei给A。若存在，则B将dei返回给A。若不存在：如果IDi是第N1或N2(iN1,N2)次询问，则游戏失败终止。否则，B首先询问OH(IDi)对应的哈希列表是否包含元素(IDi,ni)。若包含，则B计算dei=r+niP2，将结果返回给A，并将(IDi,dei)更新至列表L1中。若不包含，则B执行哈希查询OH(IDi)，选择一个随机数ni N，将dei=r+niP2的计算结果返回给A，同时更新LH、L1两个列表。（4）否认认证加密查询。A向B提交发送者的身份标识IDj、接收者的身份标识IDk和明文M。如果jN1,N2，B通过查询列表L1获得身份标识IDj2524赵晨阳 等：具有否认认证的SM9标识加密算法对应的私钥，若不存在，则通过用户密钥提取查询和哈希查询OH(IDi)生成用户IDj的公私钥对，接着运行否认认证加密算法，计算=DAEnc(M,dej,IDj,IDk)的结果发送给A。如果jN1,N2，游戏失败终止。（5）否 认 认 证 解 密 查 询。A向B提 交 一 个DAEnc 认证器=(C1,C2,C3)和接收者的身份标识IDk。如果kN1,N2，B查询列表L1是否存在标识IDk的私钥dek。若不存在，则通过用户密钥提取查询和哈希查询OH(IDi)生成用户IDk的私钥，运行否认认证解密算法，将恢复出的消息M发送给A。如果kN1,N2，游戏失败终止。挑战 在A决定询问阶段1结束时，A输出两个等长的明文M0、M1以及之前没有做过密钥提取查询的两个身份标识IDS、IDR一并发送给B。如果A在游戏中向B询问过IDS和IDR的私钥，则B失败，游戏终止。同时，若IDS和IDR均不是IDN1和IDN2(S,R N1,N2)，则B仍失败，游戏终止。为了计算DAEnc认证器密文，B执行以下操作：（1）B通 过 用 户 密 钥 提 取 查 询 和 哈 希 查 询OH(IDi)生成身份标识IDS的私钥。（2）B随机选择一位 0,1，运行否认认证加密算法，将=DAEnc(M,deS,IDS,IDR)的计算结果发送给A作为挑战。询问阶段2 类似于询问阶段1，A允许继续询问私钥和密文解密等，但A不能对身份标识IDS和IDR做用户密钥提取查询。与此同时，A也不能对挑战做否认认证解密查询。猜测 最终A输出一位 0,1。如果 =，B输出0，否则输出1。用F表示A对挑战身份的猜测不正确，此时模拟会终止。若B终止，则B随机输出=的概率是12。由于A是随机猜测的，F不发生的概率是2qH，即Pr(F)=2qH。假设B不终止，若Z=e(P1,P2)xyz，因为B的模拟与A的真实攻击视图相同，此时A游戏获胜的概率为AdvCA()+12。若Z是GT中的随机元素，由于B模拟是完备的，A最多以12的概率游戏获胜。综上，B解决DBDH困难问题的优势可表示如下：AdvDBDHB()=|Pr=|FPrF+Pr=|FPrF-12=|12(1-PrF)+(Pr=0|F=0Pr=0+|Pr=1|F=1Pr=1)PrF-12|12(1-PrF)+PrFAdvCA()+1212+14-12=12PrFAdvCA()=1qHAdvCA()由计算可知，如果AdvCA()不可忽略，则AdvDBDHB()也不可忽略，即B可以以不可忽略的优势解决DBDH问题，这与DBDH假设矛盾。因此，攻击者A无法以不可忽略的优势赢得密文不可区分性游戏。证毕。3.3否认认证性本文所提 SM9-DAIBE 算法在随机预言模型下满足抗适应性选择消息攻击的否认认证性。定理 2 在随机预言模型下，若攻击者X在一定时间内赢得DA-DAIBE-CMA游戏，则存在一个高效的多项式时间算法解决DBDH问题。证明 此处通过2.3节定义的挑战者B和攻击者X之间的 DA-DAIBE-CMA 游戏证明本文算法的否认认证性。如果存在一个攻击者X可以打破这个算法，那么可以使用攻击者X来构造一个算法B，进而解决DBDH问题。类似定理1中保密性的证明，游戏的过程描述如下：初始化阶段 算法B输入一个安全参数，运行系统参数生成算法Setup（1），返回系统参数param=(G,Ppub-e,H,hid)，其中G=(e,G1,G2,GT,N,P1,P2)为双线性配对群，Ppub-e=keP1且ke未知。X将系统参数param发送给攻击者X。攻击阶段 与定理1证明中询问阶段1的查询一致，X执行多项式有界数量的哈希查询、KDF查询、用户密钥提取查询、否认认证加密查询和否认认证解密查询等。伪造阶段X输出一个 DAEnc认证器密文=(C1,C2,C3)和两个身份标识IDS、IDR。其中X未对IDS和IDR进行私钥询问。由分叉引理22可知，如果X是该游戏中的一个成功的伪造者，那么可以构造X。X可 以 生 成(IDS,IDR,t,C2,C3)和(IDS,IDR,t,C2,C3)，其中C2 C2。目前没有公认的解决DBDH困难问题的有效算法，因此实际上不存在这样的攻击者X，证明该算法具有否认认证性。证毕。2525Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(10)4性能分析本章从理论分析和实验分析两方面出发，将本文所设计的 SM9-DAIBE 算法与文献5，19，21中算法进行比较。4.1理论分析表 2 比较了 4 个算法的参数大小和主要运算时间。符号说明：N表示用户的密文数量，“Exp”表示指数运算，“Pairing”表示双线性对运算。在比较各算法所需的运算操作次数时，忽略了除指数运算和配对运算之外的操作。SM9-DAIBE 与文献5，19，21中的算法运算均需基于双线性对运算。不妨假定|G1|=|G2|=|GT|=1 024bit，|ID|=160bit，|M|=160bit以及哈希值|H|=160bit，因此可计算出文献19的通信规模为|ID|+|G1|+|M|+|G2|=2 368bit，文献21的通信规模为|ID|+|G1|+|M|+|G2|+|H|=2 528bit，文献5和本文算法的通信规模为|ID|+|G1|+|M|+|G2|+|GT|=3 392bit。图2给出了这4个算法通信规模的具体条形图。通过表 2 和图 2 的比较可以看到，本文 SM9-DAIBE算法保持了原始 SM9-IBE算法5的系统公钥和私钥的选取方式。与文献19,21相比，对于用户加密和解密算法，文献19共需要4次双线性配对运算，文献21共需要 3次双线性配对运算，而本文仅需要2次双线性配对运算。一般来讲，双线性配对运算较其他运算耗时较多。因此，本文算法相比文献19,21的算法在用户加密和解密等方面具有一定的优势。并且本文算法采用安全参数小的非对称双线性对，用户的公私钥分别由两个不同的循环群生成，安全强度更高。正因此，本文算法中增加了乘法循环群GT，这使得该算法在通信开销上相较于文献19,21中的算法会有所增加。4.2实验分析本节通过仿真实验将本文算法与文献5,19,21在发送方计算成本（CS）和接收方计算成本（CR）两方面进行对比。实验环境为荣耀笔记本（3.20 GHz的 64 位 AMD Ryzen 7 5800H with Radeon Graphics处理器、16 GB内存（RAM）、Windows 10操作系统），使用PBC库23中的A型配对实现了4个算法，并获得图3所示的实验结果。A型配对构造在嵌入度为2的曲线y2 x3+x(modp)上（其中p 3mod4且为素数）。从图3可以看到：对于文献5，CS是45.809