Efficient certificateless ring signature scheme based on elliptic curve

doi:10.11772/j.issn.1001-9081.2022111801

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (11): 3368-3374.DOI: 10.11772/j.issn.1001-9081.2022111801

• National Open Distributed and Parallel Computing Conference 2022 (DPCS 2022） • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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)

摘要：

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

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

CLC Number:

TP309

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.

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

Figures/Tables 4

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$	验证者

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$	验证者

Fig. 1 Flow of ECL-RS scheme

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

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

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$

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$

References 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]	Yue LI, Dan TANG, Minjun SUN, Xie WANG, Hongliang CAI, Qiong ZENG. Efficient reversible data hiding scheme based on two-dimensional modulo operations [J]. Journal of Computer Applications, 2024, 44(6): 1880-1888.
[2]	Zhipeng MAO, Runhe QIU. Energy-spectrum efficiency trade-off for multi-cognitive relay network with decode-and-forward full-duplex maximum energy harvesting [J]. Journal of Computer Applications, 2024, 44(4): 1202-1208.
[3]	Lipeng ZHAO, Bing GUO. Blockchain consensus improvement algorithm based on BDLS [J]. Journal of Computer Applications, 2024, 44(4): 1139-1147.
[4]	Rui TANG, Shibo YUE, Ruizhi ZHANG, Chuan LIU, Chuanlin PANG. Energy efficiency optimization mechanism for UAV-assisted and non-orthogonal multiple access-enabled data collection system [J]. Journal of Computer Applications, 2024, 44(4): 1209-1218.
[5]	Yiting WANG, Wunan WAN, Shibin ZHANG, Jinquan ZHANG, Zhi QIN. Linkable ring signature scheme based on SM9 algorithm [J]. Journal of Computer Applications, 2024, 44(12): 3709-3716.
[6]	Jinbo LI, Ping ZHANG, Ji ZHANG, Muhua LIU. Identity-based ring signature scheme on number theory research unit lattice [J]. Journal of Computer Applications, 2023, 43(9): 2798-2805.
[7]	Yanan SUN, Jiehong WU, Junling SHI, Lijun GAO. Multi-UAV collaborative task assignment method based on improved self-organizing map [J]. Journal of Computer Applications, 2023, 43(5): 1551-1556.
[8]	Xia HUA, Zhenghao ZHU, Cong XU, Xihuang ZHANG, Zhilei CHAI, Wenjie CHEN. Workload automatic mapper for spiking neural network based on precise communication modeling [J]. Journal of Computer Applications, 2023, 43(3): 827-834.
[9]	Qian ZHANG, Runhe QIU. Trade-off between energy efficiency and spectrum efficiency for decode-and-forward full-duplex relay network [J]. Journal of Computer Applications, 2023, 43(10): 3188-3194.
[10]	Liang ZHU, Hua XU, Jinhai CHENG, Shen ZHU. Analysis and improvement of AdaBoost’s sample weight and combination coefficient [J]. Journal of Computer Applications, 2022, 42(7): 2022-2029.
[11]	Jingyu SUN, Jiayu ZHU, Ziqiang TIAN, Guozhen SHI, Chuanjiang GUAN. Attribute based encryption scheme based on elliptic curve cryptography and supporting revocation [J]. Journal of Computer Applications, 2022, 42(7): 2094-2103.
[12]	Hongwei GUO, Xiangsuo FAN, Shuai LIU, Xiang WEI, Lingli ZHAO. Video coding optimization algorithm based on rate-distortion characteristic [J]. Journal of Computer Applications, 2022, 42(3): 946-952.
[13]	Xin LING, Minzheng LI. Hybrid beamforming method with high spectral efficiency for unmanned aerial vehicle patrol system [J]. Journal of Computer Applications, 2022, 42(3): 980-984.
[14]	Jun FENG, Bingfa WANG, Jiamin LU. Query performance evaluation of distributed resource description framework data management systems [J]. Journal of Computer Applications, 2022, 42(2): 440-448.
[15]	Lingzhao WANG, Runhe QIU. Joint optimization method of full-duplex cognitive relay network based on nonlinear energy harvesting [J]. Journal of Computer Applications, 2022, 42(10): 3130-3139.

Efficient certificateless ring signature scheme based on elliptic curve

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 21

Related Articles 15

Recommended Articles

Metrics