基于椭圆曲线的高效无证书环签名方案

doi:10.11772/j.issn.1001-9081.2022111801

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (11): 3368-3374.DOI: 10.11772/j.issn.1001-9081.2022111801

• 2022年全国开放式分布与并行计算学术年会(DPCS 2022) • 上一篇下一篇

基于椭圆曲线的高效无证书环签名方案

朱秀萍¹^,²^,³, 刘亚丽¹^,²^,³(), 林昌露², 李涛¹^,²^,³, 董永权¹

^1.江苏师范大学计算机科学与技术学院，江苏徐州 221116
^2.福建省网络安全与密码技术重点实验室（福建师范大学），福州 350117
^3.广西密码学与信息安全重点实验室（桂林电子科技大学），广西桂林 541004

收稿日期:2022-11-04 修回日期:2023-01-04 接受日期:2023-01-10 发布日期:2023-03-15 出版日期:2023-11-10
通讯作者: 刘亚丽
作者简介:朱秀萍（1997—），女，四川内江人，硕士研究生，CCF会员，主要研究方向：公钥密码学、数字签名、物联网隐私保护
刘亚丽（1981—），女，江苏徐州人，教授，博士，CCF高级会员，主要研究方向：信息安全、认证和隐私保护、区块链、车载自组织网络、密码算法和协议 liuyali@jsnu.edu.cn
林昌露（1978—），男，福建大田人，教授，博士生导师，博士，CCF会员，主要研究方向：密码学、网络安全、秘密共享、安全多方计算、公钥密码学
李涛（1998—），男，湖北黄冈人，硕士研究生，主要研究方向：无线射频识别认证、隐私保护、物联网安全、区块链
董永权（1979—），男，江苏宿迁人，教授，博士，CCF会员，主要研究方向：Web信息管理、Web信息安全。
基金资助:
国家自然科学基金资助项目(61702237);徐州市科技计划项目(KC22052);福建省网络安全与密码技术重点实验室（福建师范大学）开放课题(NSCL?KF2021?04);广西密码学与信息安全重点实验室（桂林电子科技大学）研究课题(GCIS202114);江苏师范大学研究生科研与实践创新计划项目(2021XKT1396);教育部产学合作协同育人项目(202101374001)

Efficient certificateless ring signature scheme based on elliptic curve

Xiuping ZHU¹^,²^,³, Yali LIU¹^,²^,³(), Changlu LIN², Tao LI¹^,²^,³, Yongquan DONG¹

^1.College of Computer Science and Technology，Jiangsu Normal University，Xuzhou Jiangsu 221116，China
^2.Fujian Provincial Key Laboratory of Network Security and Cryptology （Fujian Normal University），Fuzhou Fujian 350117，China
^3.Guangxi Key Laboratory of Cryptography and Information Security （Guilin University of Electronic Technology），Guilin Guangxi 541004，China

Received:2022-11-04 Revised:2023-01-04 Accepted:2023-01-10 Online:2023-03-15 Published:2023-11-10
Contact: Yali LIU
About author:ZHU Xiuping， born in 1997， M. S. candidate. Her research interests include public-key cryptography， digital signature， Internet of Things privacy-preserving.
LIU Yali， born in 1981， Ph. D.， professor. Her research interests include information security， authentication and privacy-preserving， blockchain， vehicular ad-hoc network， cryptographic algorithms and protocols.
LIN Changlu， born in 1978， Ph. D.， professor. His research interests include cryptography， network security， secret sharing， secure multi-party computation， public-key cryptography.
LI Tao， born in 1998， M. S. candidate. His research interests include Radio Frequency Identification （RFID） authentication， privacy protection， Internet of Things security， blockchain.
DONG Yongquan， born in 1979， Ph. D.， professor. His research interests include Web information management， Web information security.
Supported by:
National Natural Science Foundation of China(61702237);Science and Technology Planning Foundation of Xuzhou City(KC22052);Opening Foundation of Fujian Provincial Key Laboratory of Network Security and Cryptology Research Fund, Fujian Normal University(NSCL-KF2021-04);Opening Foundation of Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology(GCIS202114);Postgraduate Research and Practice Innovation Program of Jiangsu Normal University(2021XKT1396);Ministry of Education University-Industry Collaborative Education Program of China(202101374001)

摘要/Abstract

摘要：

环签名具有自发性和匿名性，被广泛用于解决用户身份和数据隐私泄露问题；而无证书公钥密码体制不仅可以解决密钥托管问题，还不需要公钥证书的管理；无证书环签名则结合了上述两者的优点，具有广泛的研究意义，但现有大多数无证书环签名方案基于双线性配对运算和模指数运算，计算成本高、效率低。为了提高签名阶段和验证阶段的效率，提出一种新的基于椭圆曲线的高效无证书环签名（ECL-RS）方案，使用了计算代价低、安全性高、灵活性好的椭圆曲线。该方案的安全性规约为离散对数困难问题和Diffie-Hellman问题，且在随机预言机模型（ROM）下证明了它能够抵抗公钥替换攻击和恶意密钥生成中心攻击，具有不可伪造性和匿名性。性能分析表明，ECL-RS方案只需（n+2）（n表示为环成员个数）次椭圆曲线标量乘法和标量加法运算，以及（n+3）次单向哈希运算，在保证安全的情况下具有较低的计算代价和更高的效率。

关键词: 环签名, 椭圆曲线, 无证书环签名, 高效性, 随机预言机模型

Abstract:

Ring signature is widely used to solve the problems of user identity and data privacy disclosure because of its spontaneity and anonymity； and certificateless public key cryptosystem can not only solve the problem of key escrow， but also do not need the management of public key certificates； certificateless ring signature combines the advantages of both of the above mentioned， and has extensive research significance， but most of the existing certificateless ring signature schemes are based on the calculation of bilinear pairings and modular exponentiation， which are computationally expensive and inefficient. In order to improve the efficiency of signature and verification stages， a new Efficient CertificateLess Ring Signature （ECL-RS） scheme was proposed， which used elliptic curve with low computational cost， high security and good flexibility. The security statute of ECL-RS scheme stems from a discrete logarithm problem and a Diffie-Hellman problem， and the scheme is proved to be resistant to public key substitution attacks and malicious key generation center attacks under Random Oracle Model （ROM） with unforgeability and anonymity. Performance analysis shows that ECL-RS scheme only needs （n+2）（n is the number of ring members） elliptic curve scalar multiplication and scalar addition operations as well as （n+3） one-way hash operations， which has lower computational cost and higher efficiency while ensuring security.

Key words: ring signature, elliptic curve, certificateless ring signature, efficiency, Random Oracle Model (ROM)

中图分类号:

TP309

朱秀萍, 刘亚丽, 林昌露, 李涛, 董永权. 基于椭圆曲线的高效无证书环签名方案[J]. 计算机应用, 2023, 43(11): 3368-3374.

Xiuping ZHU, Yali LIU, Changlu LIN, Tao LI, Yongquan DONG. Efficient certificateless ring signature scheme based on elliptic curve[J]. Journal of Computer Applications, 2023, 43(11): 3368-3374.

图/表 4

表1 符号说明

Tab. 1 Description of symbols

参数	含义
$E$	有限域 $F P$ 上的椭圆曲线
$q$	大素数
$G$	$q$ 阶的循环加法群
$P$	群 $G$ 的一个生成元
$Z q *$	小于 $q$ 的正整数组成的集合
$I D i$	第i个用户的身份
$H 1 ~ H 3$	3个安全的哈希函数
$M$	消息
$s$	系统主密钥
$P p u b$	系统主公钥， $P p u b = s P$
$p k i$	第 $i$ 个用户的公钥， $p k i = (X i, Y i)$
$s k i$	第 $i$ 个用户的私钥， $s k i = (x i, y i)$
$L$	n个用户的公钥集合 $L = {p k 1, p k 2, …, p k n}$
$u t$	实际签名者
$U$	n个用户组成的集合 $U = {u 1, u 2, …, u n}$
$σ L (M)$	对消息M的签名
$V$	验证者

表1 符号说明

Tab. 1 Description of symbols

参数	含义
$E$	有限域 $F P$ 上的椭圆曲线
$q$	大素数
$G$	$q$ 阶的循环加法群
$P$	群 $G$ 的一个生成元
$Z q *$	小于 $q$ 的正整数组成的集合
$I D i$	第i个用户的身份
$H 1 ~ H 3$	3个安全的哈希函数
$M$	消息
$s$	系统主密钥
$P p u b$	系统主公钥， $P p u b = s P$
$p k i$	第 $i$ 个用户的公钥， $p k i = (X i, Y i)$
$s k i$	第 $i$ 个用户的私钥， $s k i = (x i, y i)$
$L$	n个用户的公钥集合 $L = {p k 1, p k 2, …, p k n}$
$u t$	实际签名者
$U$	n个用户组成的集合 $U = {u 1, u 2, …, u n}$
$σ L (M)$	对消息M的签名
$V$	验证者

图1 ECL-RS方案流程

Fig. 1 Flow of ECL-RS scheme

表2 密码符号表示及运算时间

Tab. 2 Cipher symbol representation and operation time

符号	密码运算名称	时间/ms
$T P$	双线性配对运算	7.396 8
$T M$	标量乘法运算	1.315 1
$T A$	标量加法运算	0.023 6
$T W$	幂指数运算	0.259 0
$T H$	哈希函数运算	0.000 1

表2 密码符号表示及运算时间

Tab. 2 Cipher symbol representation and operation time

符号	密码运算名称	时间/ms
$T P$	双线性配对运算	7.396 8
$T M$	标量乘法运算	1.315 1
$T A$	标量加法运算	0.023 6
$T W$	幂指数运算	0.259 0
$T H$	哈希函数运算	0.000 1

表3 六种方案的计算代价对比（n=10） ( ms)

Tab. 3 Computational cost comparison of six schemes

方案来源	签名阶段	签名验证阶段	总时间
文献［7］	$(n + 1) T M + 2 (n - 1) T A + n T H ≈ 14.891 9$	$2 T P + n T M + 2 n T A + n T H ≈ 28.417 6$	$2 T P + (2 n + 1) T M + (4 n - 2) T A + 2 n T H ≈ 43.309 5$
文献［18］	$4 T M + 3 T H ≈ 5.260 7$	$2 T P + T M + T A + T H ≈ 16.132 4$	$2 T P + 5 T M + T A + 4 T H ≈ 21.393 1$
文献［19］	$(n + 1) T W + (n + 2) T M + T H ≈ 18.630 3$	$(n + 1) T P + T M + T W + T H ≈ 82.939 0$	$(n + 1) T P + (n + 3) T M + (n + 2) T W + 2 T H ≈ 101.569 3$
文献［20］	$(2 n + 4) T M + (4 n + 1) T A + 2 n T H ≈ 32.532 0$	$3 T P + 2 n T M + 2 T A ≈ 48.539 6$	$3 T P + (4 n + 4) T M + (4 n + 3) T A + 2 n T H ≈ 81.071 6$
文献［21］	$(n + 11) T W + (3 n - 2) T M ≈ 42.261 8$	$3 T P + (n + 1) T W + (n - 1) T M ≈ 36.8753$	$3 T P + (2 n + 12) T W + (3 n - 3) T M ≈ 79.137 1$
ECL-RS	$n T M + n T A + 3 T H ≈ 13.387 3$	$2 T M + 2 T A + n T H ≈ 2.678 4$	$(n + 2) T M + (n + 2) T A + (n + 3) T H ≈ 16.065 7$

表3 六种方案的计算代价对比（n=10） ( ms)

Tab. 3 Computational cost comparison of six schemes

方案来源	签名阶段	签名验证阶段	总时间
文献［7］	$(n + 1) T M + 2 (n - 1) T A + n T H ≈ 14.891 9$	$2 T P + n T M + 2 n T A + n T H ≈ 28.417 6$	$2 T P + (2 n + 1) T M + (4 n - 2) T A + 2 n T H ≈ 43.309 5$
文献［18］	$4 T M + 3 T H ≈ 5.260 7$	$2 T P + T M + T A + T H ≈ 16.132 4$	$2 T P + 5 T M + T A + 4 T H ≈ 21.393 1$
文献［19］	$(n + 1) T W + (n + 2) T M + T H ≈ 18.630 3$	$(n + 1) T P + T M + T W + T H ≈ 82.939 0$	$(n + 1) T P + (n + 3) T M + (n + 2) T W + 2 T H ≈ 101.569 3$
文献［20］	$(2 n + 4) T M + (4 n + 1) T A + 2 n T H ≈ 32.532 0$	$3 T P + 2 n T M + 2 T A ≈ 48.539 6$	$3 T P + (4 n + 4) T M + (4 n + 3) T A + 2 n T H ≈ 81.071 6$
文献［21］	$(n + 11) T W + (3 n - 2) T M ≈ 42.261 8$	$3 T P + (n + 1) T W + (n - 1) T M ≈ 36.8753$	$3 T P + (2 n + 12) T W + (3 n - 3) T M ≈ 79.137 1$
ECL-RS	$n T M + n T A + 3 T H ≈ 13.387 3$	$2 T M + 2 T A + n T H ≈ 2.678 4$	$(n + 2) T M + (n + 2) T A + (n + 3) T H ≈ 16.065 7$

参考文献 21

1	RIVEST R L， SHAMIR A， TAUMAN Y. How to leak a secret［C］// Proceedings of the 2001 International Conference on the Theory and Application of Cryptology and Information Security， LNCS 2248. Berlin： Springer， 2001： 552-565.
2	DIFFIE W， HELLMAN M. New directions in cryptography［J］. IEEE Transactions on Information Theory， 1976， 22（6）： 644-654. 10.1109/tit.1976.1055638
3	GUTMANN P. PKI： it’s not dead， just resting［J］. Computer， 2002， 35（8）： 41-49. 10.1109/mc.2002.1023787
4	SHIM K A. An efficient ring signature scheme from pairings［J］. Information Sciences， 2015， 300： 63-69. 10.1016/j.ins.2014.12.019
5	张文芳，熊丹，王小敏，等. 基于RSA公钥密码体制的可选择可转换关联环签名［J］. 计算机学报， 2017， 40（5）：1168-1180. 10.11897/SP.J.1016.2017.01168
	ZHANG W F， XIONG D， WANG X M， et al. Selectively linkable and convertible ring signature based on RSA public key cryptosystem［J］. Chinese Journal of Computers， 2017， 40（5）： 1168-1180. 10.11897/SP.J.1016.2017.01168
6	SHAMIR A. Identity-based cryptosystems and signature schemes［C］// Proceedings of the 1984 Workshop on the Theory and Application of Cryptographic Techniques， LNCS 196. Berlin： Springer， 1985： 47-53. 10.1007/3-540-39568-7_5
7	WANG K， MU Y， SUSILO W. Identity-based quotable ring signature［J］. Information Sciences， 2015， 321： 71-89. 10.1016/j.ins.2015.05.033
8	AU M H， LIU J K， SUSILO W， et al. Realizing fully secure unrestricted ID-based ring signature in the standard model based on HIBE［J］. IEEE Transactions on Information Forensics and Security， 2013， 8（12）： 1909-1922. 10.1109/tifs.2013.2282908
9	赵艳琦，来齐齐，禹勇，等. 标准模型下基于身份的环签名方案［J］. 电子学报， 2018， 46（4）： 1019-1024. 10.3969/j.issn.0372-2112.2018.04.033
	ZHAO Y Q， LAI Q Q， YU Y， et al. ID-based ring signature in the standard model［J］. Acta Electronica Sinica， 2018， 46（4）： 1019-1024. 10.3969/j.issn.0372-2112.2018.04.033
10	AL-RIYAMI S S， PATERSON K G. Certificateless public key cryptography［C］// Proceedings of the 2003 International Conference on the Theory and Application of Cryptology and Information Security， LNCS 2894. Berlin： Springer， 2003： 452-473.
11	YUAN H， ZHANG F， HUANG X， et al. Certificateless threshold signature scheme from bilinear maps［J］. Information Sciences， 2010， 180（23）： 4714-4728. 10.1016/j.ins.2010.07.021
12	张福泰，孙银霞，张磊，等. 无证书公钥密码体制研究［J］. 软件学报， 2011， 22（6）： 1316-1332. 10.3724/sp.j.1001.2011.04007
	ZHANG F T， SUN Y X， ZHANG L， et al. Research on certificateless public key cryptography［J］. Journal of Software， 2011， 22（6）： 1316-1332. 10.3724/sp.j.1001.2011.04007
13	KARATI A， ISLAM S H， KARUPPIAH M. Provably secure and lightweight certificateless signature scheme for IIoT environments［J］. IEEE Transactions on Industrial Informatics， 2018， 14（8）： 3701-3711. 10.1109/tii.2018.2794991
14	ZHANG Y， DENG R H， ZHENG D， et al. Efficient and robust certificateless signature for data crowdsensing in cloud-assisted industrial IoT［J］. IEEE Transactions on Industrial Informatics， 2019， 15（9）： 5099-5108. 10.1109/tii.2019.2894108
15	KOBLITZ N. Elliptic curve cryptosystems［J］. Mathematics of Computation， 1987， 48（177）： 203-209. 10.1090/s0025-5718-1987-0866109-5
16	BONEH D， BOYEN X. Short signatures without random oracles［C］// Proceedings of the 2004 International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 3027. Berlin： Springer， 2004： 56-73.
17	POINTCHEVAL D， STERN J. Security proofs for signature schemes［C］// Proceedings of the 1996 International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 1070. Berlin： Springer， 1996： 387-398.
18	BOUAKKAZ S， SEMCHEDINE F. A certificateless ring signature scheme with batch verification for applications in VANET［J］. Journal of Information Security and Applications， 2020， 55： No.102669. 10.1016/j.jisa.2020.102669
19	YU H， WANG W. Certificateless network coding ring signature scheme［J］. Security and Communication Networks， 2021， 2021： No.8029644. 10.1155/2021/8029644
20	ZHANG Y， ZENG J， LI W， et al. A certificateless ring signature scheme with high efficiency in the random oracle model［J］. Mathematical Problems in Engineering， 2017， 2017： No.7696858. 10.1155/2017/7696858
21	WANG Z， FAN J. Flexible threshold ring signature in chronological order for privacy protection in edge computing［J］. IEEE Transactions on Cloud Computing， 2022， 15（9）： 1253-1261.

[1]	王伊婷, 万武南, 张仕斌, 张金全, 秦智. 基于SM9算法的可链接环签名方案[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3709-3716.
[2]	李金波, 张平, 张冀, 刘牧华. NTRU格上基于身份的环签名方案[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2798-2805.
[3]	赵洪, 喻书涵, 韩妍妍, 李兆斌. 无证书签名方案的分析与改进[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 147-153.
[4]	林素青, 张书华. 支持非单调访问结构的可验证搜索属性加密方案[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2772-2779.
[5]	孙京宇, 朱家玉, 田自强, 史国振, 关川江. 基于椭圆曲线加密且支持撤销的属性基加密方案[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2094-2103.
[6]	林定康, 颜嘉麒, 巴楠登, 符朕皓, 姜皓晨. 门罗币匿名及追踪技术综述[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 148-156.
[7]	陈虹, 刘雨朦, 肖成龙, 郭鹏飞, 肖振久. 基于椭圆曲线的改进RC4算法[J]. 计算机应用, 2019, 39(8): 2339-2345.
[8]	刘欣东, 徐水帅, 陈建华. 基于椭圆曲线密码的智能电网通信认证协议[J]. 计算机应用, 2019, 39(3): 779-783.
[9]	左黎明, 胡凯雨, 张梦丽, 陈兰兰. 铁路桥梁监测中基于短签名方案的数据传输协议[J]. 计算机应用, 2018, 38(8): 2261-2266.
[10]	徐海琳, 陆阳. 高效无双线性对的带关键词搜索的基于证书加密方案[J]. 计算机应用, 2018, 38(2): 379-385.
[11]	左黎明, 陈祚松, 夏萍萍, 易传佳. 高效的可证安全短代理签名方案[J]. 计算机应用, 2018, 38(12): 3455-3461.
[12]	杨兴春, 许春香, 李朝荣. 基于ECC的支持标签所有权转移的RFID认证协议[J]. 计算机应用, 2017, 37(8): 2275-2280.
[13]	荣星, 赵勇. 基于无证书环签名的虚拟机可信证明方案[J]. 计算机应用, 2017, 37(2): 378-382.
[14]	孙意如, 梁向前, 商玉芳. 理想格上基于身份的环签名方案[J]. 计算机应用, 2016, 36(7): 1861-1865.
[15]	李云, 陈庞森, 孙山林. 基于近场通信认证的无线局域网无线接入协议的安全性设计[J]. 计算机应用, 2016, 36(5): 1236-1245.

基于椭圆曲线的高效无证书环签名方案

Efficient certificateless ring signature scheme based on elliptic curve

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 21

相关文章 15

编辑推荐

Metrics