Aitps: A Two-Party Signature Scheme from Asymmetry Module Lattice Problems

Wen Jiaming; Wang Houzhen; Liu Jinhui; Zhang Huanguo

doi:10.7544/issn1000-1239.202220533

Journal of Computer Research and Development > 2023 > 60(9): 2137-2151. > DOI: 10.7544/issn1000-1239.202220533

Wen Jiaming, Wang Houzhen, Liu Jinhui, Zhang Huanguo. Aitps: A Two-Party Signature Scheme from Asymmetry Module Lattice Problems[J]. Journal of Computer Research and Development, 2023, 60(9): 2137-2151. DOI: 10.7544/issn1000-1239.202220533

Citation:

PDF (1721 KB)

Aitps: A Two-Party Signature Scheme from Asymmetry Module Lattice Problems

Wen Jiaming^{1, 2,},
Wang Houzhen^{1, 2, 3, ,},
Liu Jinhui^{1, 2, 4,},
Zhang Huanguo^{1, 2,}

1.
School of Cyber Science and Engineering, Wuhan University, Wuhan 430072
2.
Key Laboratory of Aerospace Information Security and Trusted Computing (Wuhan University), Ministry of Education, Wuhan 430072
3.
State Key Laboratory of Cryptology, Beijing 100878
4.
School of Cyber Security, Northwestern Polytechnical University, Xi’an 710072

Funds: This work was supported by the National Key Research and Development Program of China(2022YFB4500800), the National Natural Science Foundation of China (62272385, 62272389, U19B2021), and the Fundamental Research Funds for the Central Universities(2042022kf0021).

More Information

Author Bio:
Wen Jiaming: born in 1997. PhD candidate. His main research interests include lattice-based cryptography and cryptography protocols

Wang Houzhen: born in 1981. PhD, associate professor. Member of CCF. His main research interests include public key cryptography and post-quantum cryptography

Liu Jinhui: born in 1989. PhD, associate professor. Her main research interests include cryptography and blockchain security

Zhang Huanguo: born in 1945. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include information security, cryptography, and trusted computing
Received Date: June 10, 2022
Revised Date: October 09, 2022
Available Online: May 03, 2023

Graphical Abstract

Abstract

Abstract

Recent years, with the advancement of the IoT and blockchain, multi-party signature protocols have received renewed attention. Multi-party signature is a special digital signature that requires users to interact with each other to jointly generate a signature for a message and achieve the authentication. Compared with each user signing respectively, the advantage is that the key size can be greatly decreased, and every party cannot get a legal signature only by itself, which can be used to prevent the danger of being impersonated when user’s key is lost or hijacked. On the other hand, the progress of quantum computers poses a potential threat to the traditional public key cryptography scheme, the PQC(post-quantum cryptography) project was organized by the NIST(National Institute of Standards and Technology) in the US since 2016, and it determined the algorithm that was standardized in July 2022. At the same time, the multi-party signature based on its candidate digital signature schemes (such as CRYSTALS-Dilithium) also appeared. Chinese Association for Cryptologic Research(CACR) also held a national cryptographic algorithm design competition in 2019, Aigis-sig, which is the first prize signature algorithm, adopts the similar structure with Dilithium. In this paper, Aitps is proposed, which is a two-party signature based on Aigis-sig. Compared with the existing Dilithium-based two-party signatures, Aitps has better key sizes and signature sizes. For example, the signature sizes can be reduced by more than 20% at the same security level. Lastly, Aitps can also be extended to multi-party signature.
- digital signature,
- two-party signature,
- lattice-based cryptography,
- post-quantum cryptography,
- key protection

FullText(HTML)

References (44)

References

[1]	中国互联网络信息中心. 第49次《中国互联网络发展状况统计报告》[EB/OL]. （2022-02-25）[2022-07-23]. http://www.cnnic.net.cn/n4/2022/0401/c88−1131.html CNNIC. The 49th statistical report on China’s Internet development [EB/OL]. (2022-02-25)[2022-07-23]. http://www.cnnic.net.cn/n4/2022/0401/c88−1131.html
[2]	冯琦,何德彪,罗敏,等. 移动互联网环境下轻量级 SM2两方协同签名[J]. 计算机研究与发展,2020,57(10):2136−2146 doi: 10.7544/issn1000-1239.2020.20200401 Feng Qi, He Debiao, Luo Min, et al. Efficient two-party SM2 signing protocol for mobile Internet[J]. Journal of Computer Research and Development, 2020, 57(10): 2136−2146 (in Chinese) doi: 10.7544/issn1000-1239.2020.20200401
[3]	Shoup V. Practical threshold signatures[C]//Proc of the 19th Int Conf on the Theory and Application of Cryptographic Techniques (EUROCRYPT). Berlin: Springer, 2000: 207−220
[4]	Damgård I, Mikkelsen G L, Skeltved T. On the security of distributed multiprime RSA[C]//Proc of the 17th Int Conf on Information Security and Cryptology(ICISC). Berlin: Springer, 2014: 18−33
[5]	Lindell Y. Fast secure two-party ECDSA signing[C]//Proc of the 37th Annual Int Cryptology Conf(CRYPTO). Berlin: Springer, 2017: 613−644
[6]	Doerner J, Kondi Y, Lee E, et al. Secure two-party threshold ECDSA from ECDSA assumptions[C]//Proc of the 39th IEEE Symp on Security and Privacy(S&P). Piscataway, NJ: IEEE, 2018: 980−997
[7]	Xue Haiyang, Au M H, Xie Xiang, et al. Efficient online-friendly two-party ECDSA signature[C]//Proc of the 27th ACM SIGSAC Conf on Computer and Communications Security(CCS). New York: ACM, 2021: 558−573
[8]	Maxwell G, Poelstra A, Seurin Y, et al. Simple Schnorr multi-signatures with applications to bitcoin[J]. Designs, Codes and Cryptography, 2019, 87(9): 2139−2164 doi: 10.1007/s10623-019-00608-x
[9]	Komlo C, Goldberg I. FROST: Flexible round-optimized Schnorr threshold signatures[C]//Proc of the 27th Selected Areas in Cryptography (SAC). Berlin: Springer, 2014: 34−65
[10]	Garillot F, Kondi Y, Mohassel P. Threshold schnorr with stateless deterministic signing from standard assumptions[C]//Proc of the 41st Annual Int Cryptology Conf (CRYPTO). Berlin: Springer, 2021: 127−156
[11]	Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Review, 1999, 41(2): 303−332 doi: 10.1137/S0036144598347011
[12]	Ajtai M. Generating hard instances of lattice problems (extended abstract)[C]//Proc of the 28th Annual ACM Symp on the Theory of Computing (STOC). New York: ACM, 1996: 99–108
[13]	Ducas L, Durmus A, Lepoint T, et al. CRYSTALS-Dilithium: A lattice-based digital signature scheme[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018, 2018(1): 238−268
[14]	Bos J, Ducas L, Kiltz E, et al. CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM[C]//Proc of IEEE European Symp on Security and Privacy(EuroS&P). Piscataway, NJ: IEEE, 2018: 353–367
[15]	Fouque P A, Hoffstein J, Kirchner P, et al. Falcon: Fast-Fourier lattice-based compact signatures over NTRU [EB/OL]. (2020-01-10)[2022-07-23].https://falcon-sign.info/
[16]	Zhang Jiang, Yu Yu, Fan Shuqin, et al. Tweaking the asymmetry of asymmetric-key cryptography on lattices: KEMs and signatures of smaller sizes[C]//Proc of the 23rd IACR Int Conf on Practice and Theory of Public-Key Cryptography (PKC). Berlin: Springer, 2020: 37–65
[17]	Lu Xianhui, Liu Yamin, Zhang Zhenfei, et al. LAC: Practical ring-LWE based public-key encryption with byte-level modulus [J/OL]. IACR Cryptology ePrint Archive, 2018 [2022-09-25].https://eprint.iacr.org/2018/1009
[18]	沈诗羽,何峰,赵运磊. Aigis密钥封装算法多平台高效实现与优化[J]. 计算机研究与发展,2021,58(10):2238−2252 Shen Shiyu, He Feng, Zhao Yunlei. Multi-platform efficient implementation and optimization of Aigis-enc algorithm[J]. Journal of Computer Research and Development, 2021, 58(10): 2238−2252 (in Chinese)
[19]	周朕,何德彪,罗敏,等. 紧凑的Aigis-sig 数字签名方案软硬件协同实现方法[J]. 网络与信息安全学报,2021,7(2):64−76 doi: 10.11959/j.issn.2096-109x.2021026 Zhou Zhen, He Debiao, Luo Min, et al. Compact software/hardware co-design and implementation method of Aigis-sig digital signature scheme[J]. Chinese Journal of Network and Information Security, 2021, 7(2): 64−76 (in Chinese) doi: 10.11959/j.issn.2096-109x.2021026
[20]	Cozzo D, Smart N P. Sharing the LUOV: Threshold post-quantum signatures[C]//Proc of the 17th IMA Int Conf on Cryptography and Coding (IMACC). Berlin: Springer, 2019: 128–153
[21]	Damgard I, Orlandi C, Takahashi A, et al. Two-round n-out-of-n and multi-signatures and trapdoor commitment from lattices[J]. Journal of Cryptology, 2022, 35(2): 1−56
[22]	Lyubashevsky V. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures[C]//Proc of the 15th Int Conf on the Theory and Application of Cryptology and Information Security (ASIACRYPT). Berlin: Springer, 2009: 598–616
[23]	Baum C, Damgård I, Lyubashevsky V et al. More efficient commitments from structured lattice assumptions[C]//Proc of the 11th Int Conf on Security and Cryptography for Networks (SCN). Berlin: Springer, 2018: 368–385
[24]	Vakarjuk J, Snetkov N, Willemson J. Dilizium: A two-party lattice-based signature scheme[J]. Entropy, 2021, 23(8): 989−1018 doi: 10.3390/e23080989
[25]	Lyubashevsky V, Micciancio D, Peikert C, et al. SWIFFT: A modest proposal for FFT hashing[C]//Proc of the 15th Int Conf on Fast Software Encryption (FSE). Berlin: Springer, 2008: 54–72
[26]	Fukumitsu M, Hasegawa S. A lattice-based provably secure multisignature scheme in quantum random oracle model[C]//Proc of the 14th Int Conf on Provable and Security (ProvSec). Berlin: Springer, 2020: 45–64
[27]	Garcia-Escartin J C, Gimeno V, Moyano-Fernández J J. Quantum collision finding for homomorphic Hash functions [J/OL]. IACR Cryptology ePrint Archive, 2021 [2022-09-25].https://eprint.iacr.org/2021/1016
[28]	Bai Shi, Galbraith S D. An improved compression technique for signatures based on learning with errors[C]//Proc of Cryptographers’ Track at the RSA Conf (CT-RSA). Berlin: Springer, 2014: 28–47
[29]	Laud P, Snetkov N, Vakarjuk J. DiLizium 2.0: Revisiting two-party crystals-Dilithium [J/OL]. IACR Cryptology ePrint Archive, 2022 [2022-09-25].https://eprint.iacr.org/2022/644
[30]	Langlois A, Stehlé D. Worst-case to average-case reductions for module lattices[J]. Designs, Codes and Cryptography, 2015, 75(3): 565−599 doi: 10.1007/s10623-014-9938-4
[31]	Chor B, Goldwasser S, Micali S. Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract)[C] //Proc of the 26th Annual Symp on Foundations of Computer Science(FOCS). Los Alamitos, CA: IEEE Computer Society, 1985: 383–395
[32]	Lyubashevsky V, Nguyen N K, Seiler G. SMILE: Set membership from ideal lattices with applications to ring signatures and confidential transactions[C]//Proc of the 41st Annual Int Cryptology Conf (CRYPTO). Berlin: Springer, 2021: 611–640
[33]	田杨童, 张煌, 谢少浩, 等. 后量子的智能电表隐私保护方案[J]. 计算机研究与发展, 2019, 56（10）: 2229−2242 Tian Yangtong, Zhang Huang, Xie Shaohao, et al [J]. Journal of Computer Research and Development, 2019, 56(10): 2229−2242 (in Chinese)
[34]	Lyubashevsky V, Nguyen N K, Plancon M, et al. Shorter lattice-based group signatures via “almost free” encryption and other optimizations[C]//Proc of the 27th Int Conf on Theory and Application of Cryptology and Information Security (ASIACRYPT). Berlin: Springer, 2021: 218–248
[35]	Esgin M F, Steinfeld R, Sakzad A, et al. Short lattice-based one-out-of-many proofs and applications to ring signatures[C]//Proc of the 17th Int Conf on Applied Cryptography and Network Security (ACNS). Berlin: Springer, 2019: 67–88
[36]	NIST. PQC standardization process: Announcing four candidates to be standardized, plus fourth round candidates [EB/OL]. (2022-07-05)[2022-07-25].https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4
[37]	Bernstein D J, Hülsing A, Kölbl S, et al. The SPHINCS+ signature framework[C]//Proc of the 26th ACM SIGSAC Conf on Computer and Communications Security (CCS). New York: ACM, 2019: 2129−2146
[38]	Güneysu T, Lyubashevsky V, Pöppelmann T. Practical lattice-based cryptography: A signature scheme for embedded systems[C]//Proc of the 14th Int Conf on Cryptographic Hardware and Embedded Systems (CHES). Berlin: Springer, 2012: 530–547
[39]	Lyubashevsky V. Lattice signatures without trapdoors[C]//Proc of the 31st Int Conf on the Theory and Application of Cryptographic Techniques (EUROCRYPT). Berlin: Springer, 2012: 738−755
[40]	Ducas L, Durmus A, Lepoint T, et al. Lattice signatures and bimodal Gaussians[C]// Proc of the 33rd Annual Int Cryptology Conf (CRYPTO). Berlin: Springer, 2013: 40–56
[41]	Bruinderink L G, Hülsing A, Lange T, et al. Flush, gauss, and reload —A cache attack on the BLISS lattice-based signature scheme[C]// Proc of the 18th Int Conf on Cryptographic Hardware and Embedded Systems (CHES). Berlin: Springer, 2016: 323–345
[42]	Pessl P, Bruinderink L G, Yarom Y. To BLISS-B or not to be: Attacking strongswan’s implementation of post-quantum signatures[C]//Proc of the 24th ACM SIGSAC Conf on Computer and Communications Security (CCS). New York: ACM, 2017: 1843–1855
[43]	Zhang Jiang, Yu Yu, Fan Shuqin, et al. Aigis: A family of signatures and key encapsulatIon mechanisms from asymmetric (M)LWE and (M)SIS (the part of digital signature) [EB/OL]. (2019-02-28)[2022-07-25].https://sfjs.cacrnet.org.cn/site/term/list_72_1.html
[44]	Bellare M, Neven G. Multi-signatures in the plain public-key model and a general forking lemma [C]//Proc of the 13th ACM SIGSAC Conf on Computer and Communications Security (CCS). New York: ACM, 2006: 390–399