标准模型下基于格的变色龙签名方案

张彦华; 陈岩; 刘西蒙; 尹毅峰; 胡予濮

doi:10.11999/JEIT231093

标准模型下基于格的变色龙签名方案

doi: 10.11999/JEIT231093

1.
郑州轻工业大学计算机科学与技术学院郑州 450001
2.
福州大学数学与计算机科学学院福州 350108
3.
西安电子科技大学通信工程学院西安 710071

基金项目: 河南省自然科学基金(222300420371)，河南省网络密码技术重点实验室开放课题(LNCT2022-A09)，河南省高层次人才国际化培养项目(2023026)，河南省高等学校重点科研项目(24A520054)

详细信息

作者简介:
张彦华：男，讲师，研究方向为格公钥密码学、隐私保护、后量子密码学等

陈岩：男，硕士生，研究方向为格公钥密码、基于身份的密码等

刘西蒙：男，研究员，研究方向为私计算、密文数据挖掘等

尹毅峰：男，教授，研究方向为群组密钥协商等

胡予濮：男，教授，研究方向为多线性映射、后量子密码学等

通讯作者:
张彦华　yhzhang@email.zzuli.edu.cn

中图分类号: TN918;TP309
计量
- 文章访问数: 379
- HTML全文浏览量: 207
- PDF下载量: 62
- 被引次数: 0
出版历程
- 收稿日期: 2023-10-09
- 修回日期: 2024-02-02
- 网络出版日期: 2024-02-26
- 刊出日期: 2024-07-29

Chameleon Signature Schemes over Lattices in the Standard Model

1.
School of Computer Science and Technology, Zhengzhou University of Light Industry, Zhengzhou 450001, China
2.
College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China
3.
School of Telecommunications Engineering, Xidian University, Xi’an 710071, China

Funds: The Natural Science Foundation of Henan Province (222300420371), The Open Subject of Henan Key Laboratory of Network Cryptography Technology (LNCT2022-A09), The International Cultivation of Henan Advanced Talents (2023026), The Key Scientific Research Project of Higher Education of Henan Province (24A520054)

摘要

摘要: 作为一种比较理想的指定验证者签名，变色龙签名(CS)通过在签名算法中嵌入变色龙哈希函数(CHF)对消息进行散列，更简便地解决了签名的2次传递问题。在获得不可传递性的同时，变色龙签名还要求满足不可伪造性、签名者可拒绝性以及不可抵赖性等特性。针对基于大整数分解或离散对数等传统数论难题的CS无法抵御量子计算机攻击，以及随机预言机模型下可证明安全的数字签名方案在实际具体实现中未必安全的问题，该文给出了标准模型下基于格的变色龙签名；进一步地，针对签名者可拒绝性的获得需要耗费其较大的本地存储的问题，给出了标准模型下基于格的无需本地存储的变色龙签名，新方案彻底消除了签名者对本地签名库的依赖，使得签名者能够在不存储原始消息与签名的条件下辅助仲裁者拒绝任意敌手伪造的变色龙签名。特别地，基于格上经典的小整数解问题和差错学习问题，两个方案在标准模型下是可证明安全的。
- 变色龙签名 /
- 格 /
- 不可传递性 /
- 标准模型 /
- 无需本地存储
Abstract: As an ideal designated verifier signature, Chameleon Signature (CS) can solve the problem of signature secondary transmission more subtly by embedding an efficient Chameleon Hash Function (CHF) into the signing algorithm. In addition to non-transferability, CS also should satisfy unforgeability, deniability, non-repudiation for the signer, and so on. To solve the problems that cryptosystems based on the traditional number theory problems, such as the large integer factorization or discrete logarithm cannot resist quantum computing attacks, and the schemes that provably secure in the random oracle model may not be secure in a practical implementation, a lattice-based CS scheme in the standard model is proposed; Furthermore, to solve the problem of requiring a significant local storage to obtain deniability for the signer, a lattice-based CS scheme without local storage in the standard model is proposed, the new scheme completely eliminates the signer’s dependence on the local signature library, and enables the signer to assist an arbitrator to reject a forged signature of any adversary without storing the original message and signature. Particularly, based on the hardness of the small integer solution problem and learning with errors problem, both schemes are proved secure in the standard model.
- Chameleon Signature (CS) /
- Lattice /
- Non-transferability /
- Standard model /
- Without local storage

HTML全文

图 1 各方案耗时比较

下载: 全尺寸图片幻灯片

表 1 效率分析

方案	公共参数长度	签名长度	不可伪造性	不可传递性	可拒绝性	不可抵赖性	无需本地存储	安全模型
文献[12]	$\tilde {\mathcal{O}}\left( {{n^2}} \right)$	$\tilde {\mathcal{O}}\left( {{n^2}} \right)$	$\times$	$\surd$	$\times$	$\surd$	$\times$	随机预言机
文献[13]	$\tilde {\mathcal{O}}\left( {{n^3}} \right)$	$\tilde {\mathcal{O}}\left( {{n^2}} \right)$	$\surd$	$\surd$	$\times$	$\surd$	$\times$	标准
文献[14]	$\tilde {\mathcal{O}}\left( {{k_0} \cdot {n^2}} \right)$	$\tilde {\mathcal{O}}\left( {{n^2}} \right)$	$\surd$	$\times$	$-$	$-$	$-$	标准
文献[15]	$\tilde {\mathcal{O}}\left( {{n^2}} \right)$	$\tilde {\mathcal{O}}\left( {{k_1} \cdot n} \right)$	$\surd$	$\surd$	$\surd$	$\surd$	$\times$	随机预言机
文献[16]	$\tilde {\mathcal{O}}\left( {{n^2}} \right)$	$\tilde {\mathcal{O}}\left( n \right)$	$\surd$	$\surd$	$\surd$	$\surd$	$\times$	随机预言机
本文方案1	$\tilde {\mathcal{O}}\left( {{n^2}} \right)$	$\tilde {\mathcal{O}}\left( n \right)$	$\surd$	$\surd$	$\surd$	$\surd$	$\times$	标准
本文方案2	$\tilde {\mathcal{O}}\left( {{n^2}} \right)$	$\tilde {\mathcal{O}}\left( n \right)$	$\surd$	$\surd$	$\surd$	$\surd$	$\surd$	标准
注： ${k_0}$ 表示同态计算的数据集尺寸， ${k_1}$ 表示有向无环图的内部顶点数； $\times$ 表示不满足， $\surd$ 表示满足， $-$ 表示不考虑。

下载: 导出CSV

表 2 参数设置

参数	设置号
参数	1	2	3	4	5	6
n	128	136	192	214	256	320
q	14680063	17608247	56623093	78402743	134217803	294912113
m	6144	6528	9984	11556	13824	17920

下载: 导出CSV

表 3 不同方案的运行时间

方案	Sign	Forge	Verify
文献[16]方案1	${{\mathrm{ST}}} + \left( {2m + 2} \right){\mathrm{MT}}$	${{\mathrm{ST}}} + \left( {m + 3} \right){\mathrm{MT}}$	$\left( {2m + 3} \right){\mathrm{MT}}$
文献[16]方案2	${{\mathrm{ST}}} + \left( {2m + 4} \right){\mathrm{MT}}$	${{\mathrm{ST}}} + \left( {m + 3} \right){\mathrm{MT}}$	$\left( {2m + 5} \right){\mathrm{MT}}$
本文方案1	${{\mathrm{ST}}} + {\mathrm{2MT}}$	${{\mathrm{ST}}} + {\mathrm{3MT}}$	${\mathrm{3MT}}$
本文方案2	${{\mathrm{ST}}} + 5{\mathrm{MT}}$	${{\mathrm{ST}}} + 3{\mathrm{MT}}$	$3{\mathrm{MT}}$

下载: 导出CSV

参考文献(20)

[1]	CHAUM D and VAN ANTWERPEN H. Undeniable signatures[M]. BRASSARD G. Advances in Cryptology - CRYPTO’89. New York: Springer, 1990: 212–216. doi: 10.1007/0-387-34805-0_20.
[2]	JAKOBSSON M, SAKO K, and IMPAGLIAZZO R. Designated veriﬁer proofs and their applications[C]. The International Conference on the Theory and Applications of Cryptographic Techniques, Saragossa, Spain, 1996: 143–154. doi: 1 0.1007/3-540-68339-9_13.
[3]	KRAWCZYK H and RABIN T. Chameleon hashing and signatures[EB/OL]. http://eprint.iacr.org/1998/10, 1998.
[4]	WU Chunhui, KE Lishan, and DU Yusong. Quantum resistant key-exposure free chameleon hash and applications in redactable blockchain[J]. Information Sciences, 2021, 548: 438–449. doi: 10.1016/j.ins.2020.10.008.
[5]	JIA Meng, CHEN Jing, HE Kun, et al. Redactable blockchain from decentralized chameleon hash functions[J]. IEEE Transactions on Information Forensics and Security, 2022, 17: 2771–2783. doi: 10.1109/TIFS.2022.3192716.
[6]	TSUNODA T, NIMURA K, YAMAMOTO D, et al. A chameleon hash-based method for proving execution of business processes[J]. Journal of Information Processing, 2022, 30: 613–625. doi: 10.2197/ipsjjip.30.613.
[7]	LI Cong, SHEN Qingni, XIE Zhikang, et al. Efficient identity-based chameleon hash for mobile devices[C]. 2022 IEEE International Conference on Acoustics, Speech and Signal Processing, Singapore, 2022: 3039–3043. doi: 10.1109/ICASSP43922.2022.9746617.
[8]	NIST. PQC standardization process: Announcing four candidates to be standardized, plus fourth round candidates[EB/OL].https://csrc.nist.gov/news/2022/pqc-candidates-to-be-standardized-and-round-4, 2022.
[9]	JOSEPH D, MISOCZKI R, MANZANO M, et al. Transitioning organizations to post-quantum cryptography[J]. Nature, 2022, 605(7909): 237–243. doi: 10.1038/s41586-022-04623-2.
[10]	GENTRY C, PEIKERT C, and VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions[C]. The 40th Annual ACM Symposium on Theory of Computing, Victoria, Canada, 2008: 197–206. doi: 10.1145/1374376.1374407.
[11]	CASH D, HOFHEINZ D, KILTZ E, et al. Bonsai trees, or how to delegate a lattice basis[C]. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, France, 2010: 523–552. doi: 10.1007/978-3-642-13190-5_27.
[12]	谢璇, 喻建平, 王廷, 等. 基于格的变色龙签名方案[J]. 计算机科学, 2013, 40(2): 117–119. doi: 10.3969/j.issn.1002-137X.2013.02.026. XIE Xuan, YU Jianping, WANG Ting, et al. Chameleon signature scheme based on lattice[J]. Computer Science, 2013, 40(2): 117–119. doi: 10.3969/j.issn.1002-137X.2013.02.026.
[13]	NOH G and JEONG I R. Strong designated verifier signature scheme from lattices in the standard model[J]. Security and Communication Networks, 2016, 9(18): 6202–6214. doi: 10.1002/sec.1766.
[14]	XIE Dong, PENG Haipeng, LI Lixiang, et al. Homomorphic signatures from chameleon hash functions[J]. Information Technology and Control, 2017, 46(2): 274–286. doi: 10.5755/j01.itc.46.2.14320.
[15]	THANALAKSHMI P, ANITHA R, ANBAZHAGAN N, et al. A hash-based quantum-resistant chameleon signature scheme[J]. Sensors, 2021, 21(24): 8417. doi: 10.3390/s21248417.
[16]	张彦华, 陈岩, 刘西蒙, 等. 格上基于身份的变色龙签名方案[J]. 电子与信息学报, 2024, 46(2): 757–764. doi: 10.11999/JEIT230155. ZHANG Yanhua, CHEN Yan, LIU Ximeng, et al. Identity-based chameleon signature schemes over lattices[J]. Journal of Electronics & Information Technology, 2024, 46(2): 757–764. doi: 10.11999/JEIT230155.
[17]	AJTAI M. Generating hard instances of lattice problems (extended abstract)[C]. The 28th Annual ACM Symposium on Theory of Computing, Philadelphia, USA, 1996: 99–108. doi: 10.1145/237814.237838.
[18]	REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]. The 37th Annual ACM Symposium on Theory of Computing, Baltimore, USA, 2005: 84–93. doi: 10.1145/1060590.1060603.
[19]	ALWEN J and PEIKERT C. Generating shorter bases for hard random lattices[J]. Theory of Computing Systems, 2011, 48(3): 535–553. doi: 10.1007/s00224-010-9278-3.
[20]	MICCIANCIO D and PEIKERT C. Trapdoors for lattices: Simpler, tighter, faster, smaller[C]. The 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, 2012: 700–718. doi: 10.1007/978-3-642-29011-4_41.