紧安全的环签名构造

2022-06-07唐国锋林东岱

信息安全学报 2022年3期

邱添,唐国锋, 林东岱

紧安全的环签名构造

邱添1,2,唐国锋3, 林东岱1,2

1中国科学院信息工程研究所信息安全国家重点实验室北京中国 1000932中国科学院大学网络空间安全学院北京中国 1000493中国科学院软件研究所可信计算与信息保障实验室北京中国 100190

对于一个密码方案而言, 如何在安全证明中降低归约损失、实现紧归约是一个重要的问题。因为一般来说归约损失越大, 就需要更大的参数来保证方案的理论安全强度, 而在部署一个紧安全的密码方案的时候, 则不需要牺牲效率来弥补归约损失。在这篇文章中, 我们关注紧安全的环签名构造。环签名在2001年由Rivest等人首次提出, 它允许用户在隐藏自己身份的同时进行签名, 任何人都不能破坏环签名的匿名性, 同时敌手不能冒充任意一个环成员生成相应的有效签名。虽然目前已有多种环签名的构造方案, 但证明过程中的归约损失是高效实现的一大阻碍。

在本文中, 我们基于DDH假设在随机预言机模型下提出了一种环签名方案, 其中安全证明的归约损失仅为常数, 因此称为紧安全的环签名构造。在构造中, 我们令每个用户的公钥由两个子公钥构成, 用户私钥为其中一个子公钥对应的子私钥, 再基于Goh与Jarecki提出的紧安全的EDL签名方案, 我们利用标准的CDS变换构造了一个1/N-DDH非交互零知识证明系统, 从而证明用户拥有有效的私钥, 得到相应的环签名方案。得益于这种特殊的构造, 在安全证明中我们不必使用分叉引理, 也不必猜测敌手的目标公钥, 从而实现了紧安全归约。此外, 我们的方案可以用来构造附加其他性质的环签名方案, 如可链接环签名, 同时对于其他匿名签名方案的紧安全设计也具有启发意义。

环签名; 可证明安全; 紧安全归约; DDH假设

1 引言

1976年, Diffie与Hellman发表了文章《密码学的新方向》[1], 标志着公钥密码学的建立。此后众多公钥密码算法相继被提出, 并应用到人们的日常生活当中, 如密钥交换算法、公钥加密算法、数字签名算法等等。

然而紧归约的实现一般比较困难, 主要体现在两个方面, 一是证明方法, 比如基于离散对数假设的Schnorr签名[2], 它本质上是由一个Σ-协议通过Fiat-Shamir变换[3]得到的, 在该方案的安全证明中, 挑战者通过重绕敌手得到针对于同一个承诺值的两次伪造, 从中提取出离散对数的解。由分叉引理[4]可知这个归约并不紧, 且损失因子与敌手询问随机预言机的次数有关。尽管有很多紧安全的基于离散对数的签名构造, 但它们或者损失了效率[5], 或者需要更强的假设[6-8]。另一方面是应用场景, 比如在多用户的场景中[9], 挑战者需要猜测敌手的目标用户公钥, 猜对了才能解决底层困难问题, 成功概率一般与用户的个数有关, 因此多用户场景也会引起归约损失。为了使密码方案在理论上达到特定的安全级别, 部署方案时就需要过大的安全参数, 因此降低效率。作为一类典型的多用户签名方案, 环签名就是这样一个例子。

1.1 相关工作

环签名(Ring Signature, RS)这一概念[10]由 Rivest、Shamir和Tauman于2001 年提出。一个环签名方案中可以有多个用户, 每个用户可以任意选取多个其他用户的公钥构成一个环, 在签名算法中签名者只需证明自己是环中的一个成员, 从而隐藏自己的身份, 匿名性保证验证者可以检查签名的有效性, 但不知道签名是由环中的哪一个成员所签。不可伪造性保证敌手不能冒充任意一个环成员伪造出一个有效的签名。目前已有众多环签名方案, 它们或者以提高效率为目的[11-16], 或者增加了新的功能[17-20]。除了Rivest等人的工作, Bender等人[11]对环签名提出了严格的安全定义, 并在标准模型下给出了理论上的构造。

就功能性而言, 具有额外属性的环签名方案也相继被提出, 如可链接环签名[17], 基于身份的环签名[18-19], 唯一环签名[20]等等。

1.2 主要难点

1.3 主要贡献与技术

其次, 基于Goh与Jarecki提出的EDL签名方案[6], 我们利用标准的CDS变换[22]构造了一个1/N-DDH非交互零知识证明系统。我们把CDH问题的输入嵌入到公钥和哈希值中, 利用敌手的一次伪造, 挑战者便能得到CDH问题的解, 从而归约成功。利用CDS变换, 我们将这个Σ-协议扩展成一个1/N版本。

基于我们的环签名构造, 还可以得出具有其他附加性质的环签名方案, 譬如可链接环签名[17]。此外, 我们的工作对于在匿名情境下设计紧安全的签名方案还具有启发意义, 如群签名[23]、可追踪签名[24]等。

在本文第二章节中我们介绍了与本方案有关的预备知识和相关概念; 在第三章中介绍了1/N-DDH零知识证明系统, 以此为底层协议, 我们在第四部分给出了环签名的具体方案并在随机预言机模型下证明其安全性, 证明过程中的归约损失仅为常数; 第五章总结本文并提出未来的研究方向。

2 预备知识

2.1 Diffie-Hellman困难问题假设

定义2.(判定Diffie-Hellman问题, DDH.)对于概率多项式时间(Probabilistic Polynomial Time, PPT)的敌手, 给定两个数组(g, g, g)和(g, g, g), 令其判断其中哪一个是DDH数组。

定义3.(计算Diffie-Hellman问题, CDH.)对于概率多项式时间(Probabilistic Polynomial Time, PPT)的敌手, 给定数组(g, g, g), 令其计算g。

定理 1的证明可参见文献[9]。

2.2 Σ-协议

图1 DDH问题的Σ-协议

Figure 1 Σ-protocol of DDH problem

2.3 环签名

一个环签名方案由以下4个算法构成(初始化, 密钥生成, 签名, 验证):

我们用以下三个预言机来刻画敌手能力:

3 1/N -DDH零知识证明

利用以上模拟算法, 我们可得到如下定理:

4 紧安全的环签名方案

4.1 方案描述

4.2 安全性分析

我们称一个环签名方案是安全的, 如果它满足匿名性和不可伪造性。这两个性质我们在第2.3节中已经给出了定义, 在本节中将通过以下两个定理分别证明4.1节中给出的环签名方案满足这两个性质, 从而说明此方案是安全的。

4.3 性能分析

表1 现有工作对比

5 结论

本文中我们基于DDH假设提出了一个紧安全的环签名方案, 安全证明过程中的归约损失仅为常数。在设计中, 我们令用户的公钥包含两个子公钥, 从而避免了猜测敌手目标所带来的归约损失; 基于EDL签名方案, 我们构造了一个1/N-DDH非交互零知识证明系统, 从而证明用户拥有有效的私钥, 得到相应的环签名方案。得益于这种构造方式, 在证明过程中我们没有使用重绕技术, 最终的归约损失仅为常数。

下一步, 我们可以从两个方面继续我们的研究工作, 一是基于我们的设计构造具有其他性质的环签名方案, 如可链接环签名。文献[25]提出可以利用一个环签名方案和一个一次签名方案来构造可链接环签名, 基于我们的构造虽然可以降低可链接环签名方案的归约损失, 但并不能直接得到紧安全的可链接环签名方案, 仍需进一步的研究。另一方面, 可以探究如何利用我们的思想和技术来设计其他隐私保护签名方案, 如紧安全的群签名、可追踪签名等等。

[1] Diffie W, Hellman M. New Directions in Cryptography[C]., 1976: 644-654.

[2] Blazy O, Kakvi S A, Kiltz E, et al. Tightly-Secure Signatures from Chameleon Hash Functions[C]., 2015: 256-279.

[3] Fiat A, Shamir A. How to Prove Yourself: Practical Solutions to Identification and Signature Problems[C].′, 1987: 186-194.

[4] Pointcheval D, Stern J. Security Arguments for Digital Signatures and Blind Signatures[J]., 2000, 13(3): 361-396.

[5] Fischlin M. Communication-Efficient Non-Interactive Proofs of Knowledge with Online Extractors[C]., 2005: 152-168.

[6] Goh E J, Jarecki S. A Signature Scheme as Secure as the Diffie-Hellman Problem[C]., 2003: 401-415.

[7] Katz J, Wang N. Efficiency Improvements for Signature Schemes with Tight Security Reductions[C]., 2003: 155-164.

[8] Chevallier-Mames B. An Efficient CDH-Based Signature Scheme with a Tight Security Reduction[C]., 2005: 511-526.

[9] Bellare M, Boldyreva A, Micali S. Public-Key Encryption in a Multi-User Setting: Security Proofs and Improvements[C]., 2000: 259-274.

[10] R. Rivest, A. Shamir, Y. Tauman. How to leak a secret[C]., 2001: 552-565.

[11] Bender A, Katz J, Morselli R. Ring Signatures: Stronger Definitions, and Constructions without Random Oracles[J]., 2009, 22(1): 114-138.

[12] Shacham H, Waters B. Efficient Ring Signatures without Random Oracles[J]., 2006: 289.

[13] Chandran N, Groth J, Sahai A. Ring Signatures of Sub-Linear Size without Random Oracles[C].,, 2007: 423-434.

[14] Wang F H, Hu Y P, Wang C X. A Lattice-Based Ring Signature Scheme from Bonsai Trees[J]., 2010, 32(10): 2400-2403. (王凤和, 胡予濮, 王春晓. 格上基于盆景树模型的环签名[J]., 2010, 32(10): 2400-2403.)

[15] Groth J, Kohlweiss M. One-out-of-many Proofs: Or how to Leak a Secret and Spend a Coin[C]., 2015: 253-280.

[16] Libert B, Ling S, Nguyen K, et al. Zero-Knowledge Arguments for Lattice-Based Accumulators: Logarithmic-Size Ring Signatures and Group Signatures without Trapdoors[C]., 2016: 1-31.

[17] Liu J K, Wei V K, Wong D S. Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups[C]., 2004: 325-335.

[18] Chow S S M, Lui R W C, Hui L C K, et al. Identity Based Ring Signature: Why, how and what next[C]., 2005: 144-161.

[19] Zhang Y Y, Li H, Wang Y M. Identity-Based Ring Signature Scheme under Standard Model[J]., 2008, 29(4): 40-44.

(张跃宇, 李晖, 王育民. 标准模型下基于身份的环签名方案[J]., 2008, 29(4): 40-44.)

[20] Franklin M, Zhang H B. Unique Ring Signatures: A Practical Construction[C]., 2013: 162-170.

[21] Gjøsteen K, Jager T. Practical and Tightly-Secure Digital Signatures and Authenticated Key Exchange[C]., 2018: 95-125.

[22] Cramer R, Damgård I, Schoenmakers B. Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols[C].', 1994: 174-187.

[23] D. Chaum, E. van Heyst. Group Signatures[C]., 1991: 257-265.

[24] K. Aggelos, Y. Tsiounis, M. Yung. Traceable Signatures[C]., 2004: 571-589.

[25] Wang X L, Chen Y, Ma X C. Adding Linkability to Ring Signatures with One-Time Signatures[C]., 2019: 445-464.

Tightly-secure Ring Signature Construction

QIU Tian1,2, TANG Guofeng3, LIN Dongdai1,2

1State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China2School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China3Trusted Computing and Information Assurance Laboratory, Institute of Software Chinese Academy of Sciences, Beijing 100190, China

In real-world cryptography, reducing security loss and achieving tight security are increasingly gaining importance, as larger reduction loss must be compensated by larger parameters if we want to choose these parameters in a theoretically-sound way. However, when we implement a tightly-secure cryptographic scheme, there is no need to sacrifice efficiency. In this paper, we focus on the constructions of tightly-secure ring signature. Ring signature was introduced by Rivest et. al. in 2001. It allows users to sign messages anonymously. Nobody could break this anonymity and the adversary cannot forge a valid ring signature. Although there are many ring signature constructions, their reduction loss hinders efficient implementations.

In this paper, we propose a tightly-secure ring signature scheme in the random oracle model based on the DDH assumption and the reduction loss is just a constant factor in the security proof. In our construction, user’s public key consists of two base public keys and the secret key consists of a random secret key for one of two base public keys. Then we design a 1/N-DDH non-interactive zero-knowledge proof system by applying standard CDS transformation (CRYPTO’94) on the tightly secure EDL signature scheme proposed by Goh and Jarecki (EUROCRPYPT’03). Using this proof system, users prove the ownership of one of N secret keys and we obtain a ring signature scheme. Due to this special construction, we do not use forking lemma and do not need to guess adversary’s targeted public key, thus we achieve tight security. In addition, our scheme can be used to construct other ring signature schemes with additional properties such as linkable ring signature, and it is an important inspiration to design other privacy-preserving signature schemes.

ring signature; provable secure; tight secure reduction; Decisional Diffie-Hellman(DDH) assumption

TP309.7

10.19363/J.cnki.cn10-1380/tn.2022.05.03

邱添, 硕士, Email: qiutian@iie.ac.cn。

本课题得到国家自然科学基金 (No. 61872359, No. 61936008)资助。

2019-10-16;

2020-02-24;

2022-03-15