NTRU格上基于身份的环签名方案

doi:10.11772/j.issn.1001-9081.2022081268

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (9): 2798-2805.DOI: 10.11772/j.issn.1001-9081.2022081268

NTRU格上基于身份的环签名方案

李金波, 张平(), 张冀, 刘牧华

河南科技大学数学与统计学院，河南洛阳 471023

收稿日期:2022-08-26 修回日期:2022-11-21 接受日期:2022-12-01 发布日期:2023-01-11 出版日期:2023-09-10
通讯作者: 张平
作者简介:李金波（1997—），男，河南郑州人，硕士研究生，主要研究方向：信息安全、密码学
张冀（1983—），男，河南洛阳人，高级实验师，博士，主要研究方向：信息安全、编码理论
刘牧华（1987—），男，河南洛阳人，讲师，博士，主要研究方向：密码学、信息安全、区块链应用。
基金资助:
国家自然科学基金资助项目(62102134);河南省科技攻关项目(222102210053);河南省教育厅高等学校重点科研项目(21A510003)

Identity-based ring signature scheme on number theory research unit lattice

Jinbo LI, Ping ZHANG(), Ji ZHANG, Muhua LIU

School of Mathematics and Statistics，Henan University of Science and Technology，Luoyang Henan 471023，China

Received:2022-08-26 Revised:2022-11-21 Accepted:2022-12-01 Online:2023-01-11 Published:2023-09-10
Contact: Ping ZHANG
About author:LI Jinbo， born in 1997， M. S. candidate. His research interests include information security， cryptography.
ZHANG Ji， born in 1983， Ph. D.， senior experimentalist. His research interests include information security， coding theory.
LIU Muhua， born in 1987， Ph. D.， lecturer. His research interests include cryptography， information security， blockchain application.
Supported by:
National Natural Science Foundation of China(62102134);Key Science and Technology Research Project of Henan Province(222102210053);Key Scientific Research Project of Colleges and Universities of Department of Education of Henan Province(21A510003)

摘要/Abstract

摘要：

针对格基环签名方案的陷门基尺寸过大以及环成员的公钥需要数字证书认证的问题，提出一种NTRU（Number Theory Research Unit）格上的身份基环签名方案（NTRU-IBRS）。首先，使用NTRU格上的陷门生成算法生成系统的主公私钥对；然后，将主私钥作为陷门信息并对单向函数进行求逆运算以得到环成员的私钥；最后，基于小整数解（SIS）问题使用拒绝抽样技术生成环签名。安全性分析表明，NTRU-IBRS在随机预言机模型下具有匿名性以及适应性选择消息和身份攻击下的存在不可伪造性。性能分析与实验仿真表明，与理想格上的环签名方案和NTRU格上的身份基可链接环签名方案相比，在存储开销方面，NTRU-IBRS的系统私钥长度下降了0~99.6%，签名私钥长度的下降了50.0%~98.4%；在时间开销方面，NTRU-IBRS的总时间开销减少了15.3%~21.8%。将NTRU-IBRS应用于动态车联网（IoV）场景中，模拟结果表明NTRU-IBRS在车辆交互期间能够同时保证隐私安全和提高通信效率。

关键词: NTRU格, 身份基环签名, 小整数解问题, 拒绝抽样技术, 车联网

Abstract:

Concerning the problems that the size of the trapdoor base is too large and the public key of ring members needs digital certificate authentication in the lattice-based ring signature schemes， an NTRU （Number Theory Research Unit） lattice-based Identity-Based Ring Signature scheme （NTRU-IBRS） was proposed. Firstly， the trapdoor generation algorithm on NTRU lattice was used to generate the system master public-private key pairs. Secondly， the master private key was taken as the trapdoor information and the one-way function was reversely operated to obtain the private key of every ring member. Finally， based on the Small Integer Solution （SIS） problem， the ring signature was generated by using the rejection sampling technology. Security analysis shows that NTRU-IBRS is anonymous and existentially unforgeable under adaptive chosen message and chosen identity attacks. Performance analysis and experimental simulation show that compared with the ring signature scheme on ideal lattice and the identity-based linkable ring signature scheme on NTRU lattice： in storage overhead， NTRU-IBRS has the system private key length decreased by 0 to 99.6% and the signature private key length decreased by 50.0% to 98.4%； and in time overhead， NTRU-IBRS has the total time overhead reduced by 15.3% to 21.8%. Simulation results of applying NTRU-IBRS to the dynamic Internet of Vehicles （IoV） scenario show that NTRU-IBRS can ensure privacy security and improve communication efficiency during vehicle interaction at the same time.

Key words: NTRU (Number Theory Research Unit) lattice, identity-based ring signature, Small Integer Solution (SIS) problem, rejection sampling technology, Internet of Vehicles (IoV)

中图分类号:

TP309.7

李金波, 张平, 张冀, 刘牧华. NTRU格上基于身份的环签名方案[J]. 计算机应用, 2023, 43(9): 2798-2805.

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.

图/表 5

表1 存储开销对比

Tab. 1 Comparison of storage overhead

方案	系统私钥	签名私钥	签名长度
文献［16］方案	$n 2 l b q$	$2 n l l b q$	$2 (n + l) l b q + n / 2$
文献［17］方案	$n l b q$	$4 n l b q$	$(2 l + 1) n l b q$
NTRU-IBRS	$n l b q$	$2 n l b q$	$(2 n l + 1) (n + 1) l b q$

表1 存储开销对比

Tab. 1 Comparison of storage overhead

方案	系统私钥	签名私钥	签名长度
文献［16］方案	$n 2 l b q$	$2 n l l b q$	$2 (n + l) l b q + n / 2$
文献［17］方案	$n l b q$	$4 n l b q$	$(2 l + 1) n l b q$
NTRU-IBRS	$n l b q$	$2 n l b q$	$(2 n l + 1) (n + 1) l b q$

表2 时间开销对比

Tab. 2 Comparison of time overhead

方案	系统私钥	签名私钥	签名生成	签名验证
文献［16］方案	$T T G$	$T E B + T m u l$	$2 n (l + 2) T m u l + T S P$	$(2 n + 4) T m u l$
文献［17］方案	$T T G$	$T C G$	$2 n l T S D + n (l + 1) T m u l + 2 n T R S$	$n l T m u l$
NTRU-IBRS	$T T G$	$T S P$	$[2 n (l + 2) + 2] T m u l$	$(2 n + 1) T m u l$

表2 时间开销对比

Tab. 2 Comparison of time overhead

方案	系统私钥	签名私钥	签名生成	签名验证
文献［16］方案	$T T G$	$T E B + T m u l$	$2 n (l + 2) T m u l + T S P$	$(2 n + 4) T m u l$
文献［17］方案	$T T G$	$T C G$	$2 n l T S D + n (l + 1) T m u l + 2 n T R S$	$n l T m u l$
NTRU-IBRS	$T T G$	$T S P$	$[2 n (l + 2) + 2] T m u l$	$(2 n + 1) T m u l$

表3 存储开销实验数据对比 (KB)

Tab. 3 Experimental data comparison of storage overhead

方案	系统私钥长度	签名私钥长度	签名长度
文献［16］方案	220.16	109.93	67.53
文献［17］方案	0.86	3.42	339.27
NTRU-IBRS	0.86	1.71	691.82

表4 时间开销实验数据对比 (ms)

Tab. 4 Experimental data comparison of time overhead

方案

系统

私钥

签名

私钥

签名

生成

签名

验证

图1 动态车联网模型

Fig. 1 Dynamic IoV model

参考文献 31

1	ZHANG X W， YE C J. A novel privacy protection of permissioned blockchains with conditionally anonymous ring signature［J］. Cluster Computing， 2022， 25（2）：1221-1235. 10.1007/s10586-021-03529-4
2	佘维，霍丽娟，刘炜，等. 一种可隐藏敏感文档和发送者身份的区块链隐蔽通信模型［J］. 电子学报， 2022， 50（4）：1002-1013. 10.12263/DZXB.20211021
	SHE W， HUO L J， LIU W， et al. A blockchain-based covert communication model for hiding sensitive documents and sender identity［J］. Acta Electronica Sinica， 2022， 50（4）： 1002-1013. 10.12263/DZXB.20211021
3	HERRANZ J， SÁEZ G. New identity-based ring signature scheme［C］// Proceedings of the 2004 International Conference on Information and Communications Security， LNCS 3269. Berlin： Springer， 2004： 27-39.
4	CHOW S S M， YIU S M， HUI L C K. Efficient identity based ring signature［C］// Proceedings of the 2005 International Conference on Applied Cryptography and Network Security， LNCS 3531. Berlin： Springer， 2005： 499-512.
5	SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer［J］. SIAM Journal on Computing， 1997， 26（5）：1484-1509. 10.1137/s0097539795293172
6	WANG L P， CHEN J， ZHANG K， et al. A post-quantum hybrid encryption based on QC-LDPC codes in the multi-user setting［J］. Theoretical Computer Science， 2020， 835： 52-96. 10.1016/j.tcs.2020.06.013
7	卫宏儒，黄靖怡. SOTS：一个基于哈希函数更短的后量子数字签名方案［J］. 计算机研究与发展， 2021， 58（10）：2300-2309. 10.7544/issn1000-1239.2021.20210619
	WEI H R， HUANG J Y. SOTS： a Hash function-based shorter post-quantum digital signature scheme［J］. Journal of Computer Research and Development， 2021， 58（10）： 2300-2309. 10.7544/issn1000-1239.2021.20210619
8	RIVEST R L， SHAMIR A R L， 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.
9	王凤和，胡予濮，王春晓. 格上基于盆景树模型的环签名［J］. 电子与信息学报， 2010， 32（10）： 2400-2403. 10.3724/sp.j.1146.2009.01491
	WANG F H， HU Y P， WANG C X. A lattice-based ring signature scheme from bonsai trees［J］. Journal of Electronics and Information Technology， 2010， 32（10）： 2400-2403. 10.3724/sp.j.1146.2009.01491
10	WANG J， SUN B. Ring signature schemes from lattice basis delegation［C］// Proceedings of the 2011 International Conference on Information and Communications Security， LNCS 7043. Berlin： Springer， 2011： 15-28.
11	田苗苗，黄刘生，杨威. 高效的基于格的环签名方案［J］. 计算机学报， 2012， 35（4）：712-718. 10.3724/sp.j.1016.2012.00712
	TIAN M M， HUANG L S， YANG W. Efficient lattice-based ring signature scheme［J］. Chinese Journal of Computers， 2012， 35（4）：712-718. 10.3724/sp.j.1016.2012.00712
12	李玉海，田苗苗，黄刘生. 一种格上基于身份的环签名方案［J］. 小型微型计算机系统， 2013， 34（8）：1768-1771. 10.3969/j.issn.1000-1220.2013.08.012
	LI Y H， TIAN M M， HUANG L S. An identity-based ring signature scheme from lattices［J］. Journal of Chinese Computer Systems， 2013， 34（8）： 1768-1771. 10.3969/j.issn.1000-1220.2013.08.012
13	张利利，卜春霞. 格上基于身份的高效环签名方案及安全性分析［J］. 数学的实践与认识， 2015， 45（1）：177-181.
	ZHANG L L， BU C X. Efficient lattice-based identity-based ring signature and analysis of security［J］. Mathematics in Practice and Theory， 2015， 45（1）： 177-181.
14	孙意如，梁向前，商玉芳. 理想格上基于身份的环签名方案［J］. 计算机应用， 2016， 36（7）：1861-1865，1880. 10.11772/j.issn.1001-9081.2016.07.1861
	SUN Y R， LIANG X Q， SHANG Y F. Identity based ring signature scheme in ideal lattice［J］. Journal of Computer Applications， 2016， 36（7）： 1861-1865， 1880. 10.11772/j.issn.1001-9081.2016.07.1861
15	贾小英，何德彪，许芷岩，等. 格上高效的基于身份的环签名体制［J］. 密码学报， 2017， 4（4）：392-404.
	JIA X Y， HE D B， XU Z Y， et al. An efficient identity-based ring signature scheme over a lattice［J］. Journal of Cryptologic Research， 2017， 4（4）：392-404.
16	赵宗渠，葛炳辉，赵楠楠，等. 格上高效的环签名方案［J］. 计算机应用研究， 2021， 38（6）：1855-1858.
	ZHAO Z Q， GE B H， ZHAO N N， et al. Efficient ring signature scheme on lattice［J］. Application Research of Computers， 2021， 38（6）：1855-1858.
17	TANG Y L， XIA F F， YE Q， et al. Identity-based linkable ring signature on NTRU lattice［J］. Security and Communication Networks， 2021， 2021： No.9992414. 10.1155/2021/9992414
18	ZHOU Y H， DONG S S， YANG Y G. Ring signature scheme based on lattice and its application on anonymous electronic voting［J］. KSII Transactions on Internet and Information Systems， 2022， 16（1）： 287-304.
19	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
20	GENTRY C， PEIKERT C， VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions［C］// Proceedings of the 40th Annual ACM Symposium on Theory of Computing. New York： ACM， 2008： 197-206. 10.1145/1374376.1374407
21	AGRAWAL S， BONEH D， BOYEN X. Efficient lattice （H）IBE in the standard model［C］// Proceedings of the 2010 Annual International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 6110. Berlin： Springer， 2010：553-572.
22	STEHLÉ D， STEINFELD R. Making NTRU as secure as worst-case problems over ideal lattices［C］// Proceedings of the 2011 Annual International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 6632. Berlin： Springer， 2011： 27-47.
23	AJTAI M. Generating hard instances of the short basis problem［M］// WIEDERMANN J， EMDE BOAS P van， NIELSEN M. Automata， Languages and Programming： 26th International Colloquium， ICALP' 99. Berlin： Springer， 1999：1-9. 10.1007/3-540-48523-6_1
24	LYUBASHEVSKY V. Lattice signatures without trapdoors［C］// Proceedings of the 2012 Annual International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 7237. Berlin： Springer， 2012： 738-755.
25	BENDER A， KATZ J， MORSELLI R. Ring signatures： stronger definitions， and constructions without random oracles［J］. Journal of Cryptology， 2009， 22（1）： 114-138. 10.1007/s00145-007-9011-9
26	CASH D， HOFHEINZ D， KILTZ E， et al. Bonsai trees， or how to delegate a lattice basis［J］. Journal of Cryptology， 2012， 25（4）： 601-639. 10.1007/s00145-011-9105-2
27	PEIKERT C. An efficient and parallel Gaussian sampler for lattices［C］// Proceedings of the 2010 Annual Cryptology Conference， LNCS 6223. Berlin： Springer， 2010：80-97.
28	LYUBASHEVSKY V， PREST T. Quadratic time， linear space algorithms for Gram-Schmidt orthogonalization and Gaussian sampling in structured lattices［C］// Proceedings of the 2015 Annual International Conference on the Theory and Applications of Cryptographic Techniques LNCS 9056. Berlin： Springer， 2015： 789-815. 10.1007/978-3-662-46800-5_30
29	MICCIANCIO D， PEIKERT C. Trapdoors for lattices： simpler， tighter， faster， smaller［C］// Proceedings of the 2012 Annual International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 7237. Berlin： Springer， 2012： 700-718.
30	蒋玉章. 基于环签名和区块链的车联网隐私保护方案［D］. 成都：西华大学， 2021.
	JIANG Y Z. Privacy protection scheme of vehicular ad hoc networks based on ring signature and blockchain［D］. Chengdu： Xihua University， 2021.
31	韩龙博. 格基环签名的研究与应用［D］. 兰州：西北师范大学， 2021.
	HAN L B. Research and application of lattice-based ring signature［D］. Lanzhou： Northwest Normal University， 2021.

[1]	冯睿琪, 王雷蕾, 林翔, 熊金波. 基于软件防护扩展的车联网路况监测安全数据处理框架[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1870-1877.
[2]	顾源, 张震, 段通. 面向软件定义车联网的链路故障快速恢复方法[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 853-859.
[3]	王界钦, 林士飏, 彭世明, 贾硕, 杨苗会. 协同移动边缘计算分层资源配置机制[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2501-2510.
[4]	李智, 薛建彬. C‑V2X车联网中基于模拟退火算法的任务卸载与资源分配[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3140-3147.
[5]	朱栋, 殷新春, 宁建廷. 车联网中具有强隐私保护的无证书签名方案[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3091-3101.
[6]	陈成瑞, 孙宁, 何世彪, 廖勇. 面向C-V2X通信的基于深度学习的联合信道估计与均衡算法[J]. 计算机应用, 2021, 41(9): 2687-2693.
[7]	陈葳葳, 曹利, 顾翔. 基于区块链的车联网电子取证模型[J]. 计算机应用, 2021, 41(7): 1989-1995.
[8]	王家瑞, 谭国平, 周思源. 高速车联网场景下分簇式无线联邦学习算法[J]. 计算机应用, 2021, 41(6): 1546-1550.
[9]	巫光福, 王影军. 基于区块链与云-边缘计算混合架构的车联网数据安全存储与共享方案[J]. 计算机应用, 2021, 41(10): 2885-2892.
[10]	陈锦宇, 刘兆伟. 基于改进投票证明共识协议的车联网系统[J]. 计算机应用, 2021, 41(1): 170-176.
[11]	黄辰, 曹建农, 王时绘, 张龑. 基于协作反馈控制算法的车联网行车安全动态强化模型[J]. 计算机应用, 2020, 40(4): 1209-1214.
[12]	陈葳葳, 曹利, 邵长虹. 基于区块链技术的车联网高效匿名认证方案[J]. 计算机应用, 2020, 40(10): 2992-2999.
[13]	樊娜, 朱光源, 康军, 唐蕾, 朱依水, 王路阳, 段嘉欣. 车联网环境下基于节点认知交互的路由算法[J]. 计算机应用, 2019, 39(2): 518-522.
[14]	陈镜任, 吴业福, 吴冰. 基于车辆行驶数据的驾驶人行为谱分析方法[J]. 计算机应用, 2018, 38(7): 1916-1922.
[15]	袁娜, 史昕, 赵祥模. 基于改进人工鱼群算法的车辆轨迹规划方法[J]. 计算机应用, 2018, 38(10): 3030-3035.

NTRU格上基于身份的环签名方案

Identity-based ring signature scheme on number theory research unit lattice

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 31

相关文章 15

编辑推荐

Metrics