(西华大学数学与计算机学院，四川 成都 610039)

·计算机软件理论、技术与应用·

基于多接收者加密算法的可否认环认证协议

曾晟珂，何明星，唐明伟

(西华大学数学与计算机学院，四川 成都 610039)

可否认的环认证协议允许消息的发送者匿名地认证某消息，而在认证的同时，消息接收方却不能够向第三方揭示此次认证的发生，即消息发送方可以否认该认证。针对这一问题，提出一种新的基于多接收者加密算法的可否认环认证协议。消息接收者运行基于多接收者的加密算法对认证码进行加密，并将结果发送给消息发送方。发送方解密后得到认证码，并利用该认证码对消息进行认证。该协议构造简单，仅需要2轮通信。多接收者加密算法保护了发送者的隐私，且其可否认性在并发环境中成立。

并发可否认性；可否认的环认证；多接收者加密

认证协议是网络通信中的重要协议。通过认证协议，消息接收方能够确信消息得到了指定发送方的认证。数字签名算法是实现消息认证的最直接的方法。给定签名，消息接收者可以通过签名者的公钥验证该消息是否为发送方发出；然而，数字签名算法具有公开可验证性。任何验证者都能够通过数字签名算法中输入的公钥得到消息发送方的身份且发送方无法否认。在一些场景中，发送方希望在认证某消息的同时保护自己的隐私，或者不希望自己因为对某消息的认证而陷入某种困境中；因此，数字签名算法的公开可验证性不适合提供可否认的认证。在可否认的认证协议里，消息接收方在接受发送方对某消息认证的同时，却不能够向第三方展示该消息被发送方认证过的证据；因此，认证协议的可否认性保护了消息发送方的隐私，即发送方在第三方面前可以否认对某消息的认证。然而，发送方在做认证时，其身份对于接收方来说是公开的。可否认的环认证协议实现了对接收方的匿名认证，即将发送方的身份隐藏于一组成员当中，使得接收方无法判断这组成员中谁是真正的认证者。此外，发送方可以在第三方面前否认此次认证。

可否认的认证协议最早是由Dolev等[1]提出的，此后Dwork等[2]对可否认的认证进行形式化的研究，模型化认证协议的“可否认性”，即存在对诚实双方真实认证副本的仿真副本，且2种副本不可区分。对于可否认的认证协议，学者陆续提出了相关方案[3-6]。Jiang[7]利用时限加密提出一种可否认认证的密钥交换协议。Li等[8]提出一种非交互式的基于身份的可否认的认证协议。该协议虽然实现了非交互式，但仅达到了半可否认性，即发送方可以否认参与了认证，这是因为接收方能够仿真发送方的认证副本。也就是说，该认证过程留下了证据使得至少有参与者不能够否认参与了认证。Naor[9]将可否认的认证与环签名进行结合，提出了可否认的环认证协议，即消息发送方隐藏在一组成员中，接收方无法判断发送方的真实身份；然而，该协议需要在“时间假设”下满足并发环境中的可否认性，且通信轮数为6轮。Dowsley等[10]根据文献[9]的模型提出一种可否认的环认证协议，将通信轮数降低到了4轮；然而，文献[10]的可否认性仍然需要“时间假设”来满足并发环境。文献[11]使用时限承诺构造了通信轮数为2轮的全可否认性环认证方案，该方案的并发可否认性不需要使用“时间假设”；然而由于采用基于效率较低的非交互式零知识证明系统，其效率不高。综上，本文提出一种新的可否认的环认证协议，该认证过程不会留下任何证据，因此所有参与者可以否认参与了此次认证，达到了全可否认性。该协议的可否认性在并发环境中成立，且不需要“时间假设”。也就是说，尽管若干次认证通信被攻击者随意交错执行，认证的副本仍然可以被仿真。本文提出的可否认的环认证协议仅需要2轮，其构造是基于多接收者加密算法的，该加密算法需要满足明文可意识性(plaintext awareness)。

1 预备知识

1.1多接收者加密算法

假定接收者集合R={pk1,pk2,…,pkn}。使用接收者集合中的所有公钥R={pk1,pk2,…,pkn}对消息m加密，生成的加密结果Ci被发送给集合R中对应的成员。收到Ci后，用户i使用自己的私钥ski对密文Ci进行解密，得到明文m。这种加密算法被称为多接收者加密算法[12]。一个对于消息m的多接收者加密算法Σ=(KGen,Enc,Dec)由以下算法组成。

1)密钥生成算法KGen(1γ)：给定安全参数γ，返回每个成员i的公私钥对(pki,ski)←KGen(1γ)。

2)加密算法Enc(R,m)：给定成员集合R={pk1,pk2,…,pkn}以及消息m，返回密文C=(c1,c2,…,cn)←Enc(R,m)。

3)解密算法Dec(R,ci;ski)：给定密文ci，接收者公钥集合R={pk1,pk2,…,pkn}以及某个接收者私钥ski，返回m←Dec(R,ci;ski)。

如果一个多接收者加密算法Σ是CCA2安全的，那么攻击者F不会有超过1/2的概率获得下面游戏的胜利。

1)F发布公钥询问。挑战者运行密钥生成算法(pki,ski)←KGen(1γ)，并设置公钥集合R={pk1,pk2,…,pkn}。集合R作为此次询问的返回结果。

3)F任意选取2个长度一样的明文(m0,m1)以及一个接收者集合R*∈R，F发布对于(m0,m1)和R*的挑战询问。挑战者随机选取b←{0,1}，返回此次询问的结果C*←Enc(R*,mb)。

5)F输出它的猜测b′。如果b′=b，那就说攻击者F在此次的游戏中获得了胜利。

1.2明文可意识性(plaintext awareness)

明文可意识性要求密文拥有者必须知道该密文对应的明文，该概念是由Bellare等[13]提出的。这里分别介绍PA1和PA2这2种层次的明文可意识性。说一个加密算法是PA1安全的，也就是说攻击者F利用公钥pk生成了一个有效的密文c，那么存在F′可以在不用访问解密预言机的情况下得到c对应的明文。很明显，要使这种情况成立，F′其实可以被当作是攻击者F本身。由于攻击者知道他所要询问的密文所对应的明文，那么这就意味着解密预言机对它来说是无用的。Bellare等[14]指出PA1+CPA≠CCA2而PA2+CPA=CCA2。PA2加强了PA1的安全性，因为PA2允许攻击者F监听密文。也就是说，PA2性质允许F获得加密预言机，尽管如此，它也不能得到一个不知道其明文的密文。在PA2中，同样存在一个F′可以在不用访问解密预言机的情况下输出由F生成的密文c对应的明文；但是对于F从加密预言机中得到的密文c，F′无法得到c对应的明文。

2 安全模型

为实现消息发送者的身份对接收者匿名，可否认的环认证采用环签名算法的思想，将发送者的身份隐藏在一组成员中；因此，可否认的环认证协议由发送者、接收者和一组其他成员组成，所有成员组成了可否认的环认证协议的参与者。假定所有参与者的公钥可以被任何人访问，发送者随意选择一些成员组成群体R，然后按照可否认的环认证协议，对m进行认证。协议结束后，接收方要么接受此次认证并确信群体R中的某成员对m进行了认证(但不知道具体是哪位成员)，要么拒绝该认证。尽管接收方接受了此次认证，但是它不能够使第三方相信m被R中成员认证了的事实，即R中成员可以否认此次认证。一个在并发环境下安全的可否认的环认证协议需要满足完整性、健壮性、消息源匿名性以及并发可否认性。

1)完整性。对于要认证的消息m和群体R，如果发送者A(A的公钥pkA∈R)与接收者B诚实执行协议，那么接收者B将以压倒性优势接受此次认证。

2)健壮性(不可伪造性)。敌手F可以得到对于任何消息m1,m2,…关于R的认证副本。如果F使得B接受消息m*∉{mi}i=1,2…被环R*(R*中的所有成员的私钥都未被F获得)中的某个成员认证的事实，那么，攻击者F破坏了可否认的环认证协议的健壮性。如果F成功的概率可忽略，那么协议满足健壮性。

3)消息源匿名性。尽管F可以获得R中所有成员的私钥，F也无法从认证副本中得知该认证是由群体R中的哪位成员执行的。

4)并发可否认性。如果接收方B不能使第三方相信A对m进行了认证，那么该认证协议满足可否认性。即存在一个仿真副本(该仿真副本没有使用认证者的私钥)，该仿真副本与真实副本是不可区分的。在并发环境里，F与A运行并发的多次认证通信且这些通信可以被任意的交错执行。如果在这种环境下，F与A的认证副本同样存在不可区分的仿真副本，该协议满足并发可否认性。把F与A之间被模拟的认证记为Γsim，而F与A之间进行的真实的认证记为Γreal。如果存在区分者D，使得|Pr[D(view(F,Γsim))=1]-Pr[D(view(F,Γreal))]=1|可以忽略，那么并发可否认性成立。

3 可否认的环认证协议Auth

新的可否认的环认证协议Auth是基于多接收者加密算法Σ的。如果Σ是一个可验证的对单一消息的加密算法，那么认证协议Auth的消息源匿名性是可以实现的。如果Σ满足PA2安全，那么认证协议的并发可否认性是成立的。本文提出的协议Auth仅需要2轮，而在相同模型下，Naor协议[9]需要6轮，Dowsley协议[10]需要4轮。

协议Auth的执行思路是接收方B希望群体R中的成员对消息m进行认证。B首先利用多接收者加密算法Σ对随机数k进行加密，并将加密结果flow1发送给群体R。当收到flow1后，R中的某个成员A首先检查flow1是否是对单一消息的加密。如果不是，那么A将放弃此次认证；如果是，A对flow1解密并获得随机数k。A利用k对消息m进行认证。协议Auth的具体执行如下。

1)初始化阶段。群体R={pk1,pk2,…,pkn}中的公钥事先注册并已公开，Σ是一个具有PA2安全的多接收者加密算法，m是需要被认证的消息，H:{0,1}*→{0,1}λ是一个抗碰撞的哈希函数，MAC是一个安全的消息认证码算法。

2)协议执行阶段。

第1阶段，B→A。接收方B选择一个随机数k0并生成k=H(m,R)‖k0。B运行多接收者加密算法Σ=(KGen,Enc,Dec)，对k进行加密，并将flow1=Enc(k)发送给群体R。

第2阶段，A→B。假设群体R中的成员A将要对m进行认证。A首先检查是否是对单一消息的加密。如果不是，A将放弃此次认证；否则，A再检查flow1的前λ位是否与H(m,R)相等。如果不等，A将拒绝继续认证；如果相等，A对flow1解密得到值k′，并从k′中获得值k0′。A计算flow2=MACk0′(m,R)，并将认证结果flow2发送给B。如果flow2=MACk0(m,R)，B将接受此次认证。

如果加密算法Σ是CCA2安全的，那么协议的可否认性仅在验证者是诚实的前提下实现；因为，此时的认证副本是通过加密算法Σ生成的密文。该密文也可以由接收者来生成，因此发送者A可以否认。如果存在一个恶意接收者B*及仿真者M，M收到flow1=Enc(k)；但是它不能仿真MACk0(m,R)，因为M不能解密flow1而得到k0。由于无法仿真这样的认证副本，发送者无法否认此次认证；因此，如果Σ仅是CCA2安全的则无法实现协议Auth的可否认性。

4 安全性分析与性能比较

4.1安全性分析

按照安全模型，对所构造的可否认的环认证协议Auth进行消息源匿名性、健壮性以及并发可否认性等方面的安全性分析。

4.1.1 消息源匿名性

如果Σ是一个可验证的对单一消息的多接收者加密算法，那么发送者A的身份就不会在认证中被暴露。因为R中的任何成员收到的密文都是对相同认证密钥k0的加密，即使R中的所有成员都被俘获(即Big Brother[9-10])，消息接收者也无法判断flow2是由R中哪位成员生成的。也就是说，消息认证源满足了匿名性。

4.1.2 健壮性(不可伪造性)

假设存在破坏协议Auth健壮性的攻击者F，F可以得到对于任何消息m1,m2,…关于R的认证副本。如果F可以使B接受消息m*∉{mi}i=1,2,…被R*中某个成员认证的事实，那么协议Auth的健壮性就被破坏。协议Auth的健壮性由多接收者加密算法Σ的安全性保证。由于Σ是PA2安全的，因此，Bellare在文献[14]中指出PA2+CPA=CCA2。如果多接收者加密算法Σ满足PA2和CPA是安全的(即Σ满足CCA2安全)，那么F成功破坏协议Auth的健壮性的概率是可忽略的。

定理1：如果MAC是一个安全的消息认证码算法且多接收者加密算法Σ满足CCA2安全，那么协议Auth满足健壮性。

4.1.3 并发可否认性

并发环境中的仿真器M可以为攻击者F模拟一个与真实认证副本不可区分的仿真认证副本，因此，发送方能够成功否认对该消息进行过认证。定理2将证明协议Auth满足并发可否认性。

定理2：如果多接收者加密算法Σ满足PA2和CPA，那么协议Auth的并发可否认性成立。

证明：采取仿真技术，通过讨论仿真器与攻击者之间的通信副本并说明该副本与真实通信副本存在不可区分性来证明协议Auth满足可否认性。假定敌手F的目的是攻击协议Auth的可否认性，构造一个仿真器M以及2个游戏Γreal和Γsim。游戏Γreal运行的是F与真实发送者A的通信副本，游戏Γsim运行的是F与仿真器M的通信副本。对于可否认性，需要证明这2个通信副本是不可区分的，即view(F,Γreal)与view(F,Γsim)是不可区分的。

讨论F与仿真器M的通信副本。首先F向M发送flow1=c。由于F是恶意的攻击者，这里有3种情况需要考虑。第1种情况，c是由F生成的有效密文；第2种情况，c是由F生成的无效密文；第3种情况，c是F截获的诚实接收方与真实发送方之间交互的副本。在第3种情况中，F并不知道密文c对应的明文。需要讨论的是在这3种情况下仿真器M所做的回应并指出view(F,Γreal)≈view(F,Γsim)。

对于第1种情况，c是由F生成的有效密文。由于协议Auth使用的多接收者加密算法Σ是PA2安全的，那么存在F′可以在不需要访问解密预言机的情况下为M输出F生成的密文c所对应的明文，也就是说在这种情况下，M可以得到认证码k0；因此， M对flow1的回应flow2完全等同于F与真实发送者之间进行的认证副本。

对于第2种情况，F向M发送的是无效密文。在这种情况下，M选择一个随机数rk作为认证码并向F回应flow2=MACrk(m,R)。由于c是无效的密文，这种情况下，无论是仿真的通信还是真实的通信，向MAC码输入的认证密钥都是随机选取的；因此， F与M的仿真的通信副本分布等同于F与真实发送者之间进行的认证副本分布。

对于第3种情况，c是F转发的由诚实接收者向真实发送者发送的有效密文，在这种情况下F′无法为M提取c对应的明文。为此，M选择一个随机数rk并向F回应flow2=MACrk(m,R)。在真实的认证中，flow2=MACk0(m,R)，其中k0是密文c中加密的数据。在仿真的认证中，flow2是由随机数rk生成。由于多接收者加密算法Σ满足CCA2安全(PA2+CPA=CCA2)，因此区分者无法分辨c中加密的是rk还是k0，即flow2=MACrk(m,R)与flow2=MACk0(m,R)的分布同样是不可区分的。

因此，对于这3种情况，F在与真实发送者之间的通信副本和在与仿真器交互的副本都是不可区分的，即view(F,Γreal)≈view(F,Γsim)。故协议Auth满足可否认性。由于在证明中，并没有使用“rewinding”技术[2]，也就是说，即使在多次认证通信可以被攻击者任意交错执行的并发环境中，本文的证明过程仍然是有效的，协议Auth的并发可否认性成立。

4.2性能比较

Naor按照“可否认的认证”模型[2]，结合环签名思想，提出第一个可否认的环认证协议[9]。该协议在big brother(即所有成员都暴露了私钥)的情况下，通信轮数为6。Dowsley等[10]构造了一种基于可验证的广播加密算法的可否认的环认证协议，该协议的通信轮数为4。文献[9-10]的并发可否认性都需要“时间假设”。Li等[8]构造了一个基于身份的可否认的认证协议，该协议满足非交互式，即通信轮数为1，效率很高；然而文献[8]仅实现了半可否认性，从安全性的角度来说，其方案不及文献[9-10]。文献[11]提出一种通信轮数为2的可否认的环认证协议，该协议满足big brother情况，且不需要“时间假设”就能实现并发可否认性；然而，文献[11]是基于效率较低的非交互式零知识证明系统的。本文构造了一种通信轮数为2的可否认的环认证协议，该协议满足big brother情况，实现了全可否认性，且该可否认性在并发环境中成立并不需要“时间假设”。表1是从通信轮数、可否认性的强度等方面对几个相关的可否认的认证协议进行比较的结果。

表1 几个相关协议的性能比较

5 结论

本文提出了一种新的可否认的环认证协议，该协议构造简单，通信轮数仅为2。该认证协议基于满足PA2安全的多接收者加密算法。由于利用了可验证的对单一消息加密的多接收者加密算法，该环认证协议满足消息源匿名性。多接收者加密算法的PA2安全性保证了该环认证协议在并发环境中仍然可以满足可否认性。

[1]Dolev D, Dwork C, Naor M. Non-malleable Cryptography[J]. SIAM Journal on Computing,2000, 30(2): 391-437.

[2]Dwork C, Naor M, Sahai A. Concurrent Zero-knowledge[C]//Proceedings of The 30thAnnual ACM Symposium on the Theory of Computing (STOC 1998). Dallas, USA：[s.n.], 1998: 409-418.

[3]Pass R. On Deniability in the Common Reference String and Random Oracle Model[C]//Proceedings of 23rdAnnual International Cryptology Conference (Crypto 2003). Santa Barbara, USA：[s.n.], 2003: 316-337.

[4]Di Raimondo M, Gennaro R, Krawczyk H. Deniable Authentication and Key Exchange[C]//Proceedings of 13thACM Conference on Computer and Communications Security (CCS 2006). Alexandria, USA：[s.n.], 2006: 400-409.

[5]Di Raimondo M, Gennaro R, Naor M. New Approaches for Deniable Authentication[J]. Journal of Cryptology: 2009, 22(4) : 572-615.

[6]Dodis Y, Katz J, Smith A. Composability and on-line Deniability of Authentication[C]//Proceedings of 6thTheory of Cryptography Conference (TCC 2009). SanFrancisco：[s.n.], 2009: 146-162.

[7]Jiang S. Timed Encryption with Application to Deniable Key Exchange[J]. Theoretical Computer Science,2014, 560: 172-189.

[8]Li F, Xiong P, Jin C. Identity-based Deniable Authentication for Ad Hoc Networks[J]. Computing,2014, 96(9): 843-853.

[9]Naor M. Deniable Ring Authentication[C]//Proceedings of 22ndAnnual International Cryptology Conference (Crypto 2002).Santa Barbara, USA：[s.n.], 2002:481-498.

[10]Dowsley R, Hanaoka G., Imai H, et al. Round-optimal Deniable Ring Authentication in the Presence of Big Brother[C]//Proceedings of 11thInternational Workshop on Information Security Applications (WISA 2010).Jeju Island, Korea：[s.n.], 2011: 307-321.

[11]曾晟珂，秦志光. 并发环境下可否认的环认证协议[J]. 计算机应用研究,2013,30(12): 3745-3748.

[12]Bellare M, Boldyreva A, Micali S. Public-key Encryption in a Multi-user Setting: Security Proofs and Improvements[C]//Proceedings of International Conference on the Theory and Application of Cryptographic Techniques (Eurocrypt 2000). Bruges, Belgium：[s.n.], 2000:259-274.

[13]Bellare M, Rogaway P. Optimal Asymmetric Encryption[C]//Proceedings of Workshop on the Theory and Application of Cryptographic Techniques (Eurocrypt 1994). Perugia, Italy：[s.n.], 1995:92-111.

[14]Bellare M, Palacio A. Towards Plaintext-aware Public-key Encryption without Random Oracles[C]//Proceedings of 10thInternational Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt 2004).Jeju Island, Korea：[s.n.], 2004:48-62.

(编校：饶莉)

DeniableRingAuthenticationBasedonMulti-receiverEncryption

ZENG Sheng-ke, HE Ming-xing, TANG Ming-wei

(SchoolofMathematicsandComputerEngineering,XihuaUniversity,Chengdu610039China)

Deniable ring authentication protocol allows a sender to deny an authentication and his identity is anonymous to the receiver. In this work, we propose a new deniable ring authentication protocol based on the multi-receiver encryption scheme. The receiver encrypts an authentication key with multi-receiver encryption scheme and sends it to the sender. The sender decrypts it using his private key to obtain the authentication key and uses this key to authenticate messages. This protocol only requires two communication rounds and its deniability holds in the concurrent setting without requiring timing assumption due to the multi-receiver encryption.

concurrent deniability； deniable ring authentication；multi-receiver encryption

2014-10-15

国家自然科学基金 (61402376，U1433130)；数字空间安全保障四川省高校重点实验室开放课题 (szjj2014-078)；教育部春晖计划(Z2014051)；四川省科技厅项目(2013JY0089)；四川省教育厅重点项目(13ZA0019)；西华大学重点项目(Z1222623, Z1322622)。

曾晟珂(1982—)，女，讲师，博士，主要研究方向为信息安全与密码学。

TP309

：A

：1673-159X(2015)02-0001-5

10.3969/j.issn.1673-159X.2015.02.001