CRYSTALS-Dilithium算法实现的空间优化

敖思凡; 王后珍; 白鹭; 文嘉明; 张焕国

doi:10.14188/j.1671-8836.2022.0199

您当前的位置：

首页 >

文章列表页 >

CRYSTALS-Dilithium算法实现的空间优化

信息安全 | 更新时间：2024-01-03

- CRYSTALS-Dilithium算法实现的空间优化
- Spatial Optimization for CRYSTALS-Dilithium Digital Signature Scheme
- 武汉大学学报（理学版） 2023年69卷第6期页码：709-718
- 作者机构：
  
  1.空天信息安全与可信计算教育部重点实验室，武汉大学国家网络安全学院，湖北武汉 430072
  2.先进密码技术与系统安全四川省重点实验室，四川成都 610054
- 作者简介：
  
  敖思凡，男，硕士生，现从事密码学方面的研究。E-mail：aosifan@whu.edu.cn
  E-mail：whz@whu.edu.cn
- 基金信息：
  
  国家重点研发计划(2022YFB4500800);中央高校基本科研业务费专项资金(2042022kf0021);先进密码技术与系统安全四川省重点实验室开放课题(SKLACSS-202203)
- DOI：10.14188/j.1671-8836.2022.0199
  中图分类号：
扫描看全文
敖思凡，王后珍，白鹭，等.CRYSTALS-Dilithium算法实现的空间优化［J］.武汉大学学报（理学版），2023，69（6）：709-718. DOI：10.14188/j.1671-8836.2022.0199.

AO Sifan，WANG Houzhen，BAI Lu，et al.Spatial Optimization for CRYSTALS-Dilithium Digital Signature Scheme ［J］.J Wuhan Univ （Nat Sci Ed），2023，69（6）：709-718. DOI：10.14188/j.1671-8836.2022.0199（Ch）.
敖思凡，王后珍，白鹭，等.CRYSTALS-Dilithium算法实现的空间优化［J］.武汉大学学报（理学版），2023，69（6）：709-718. DOI：10.14188/j.1671-8836.2022.0199. DOI：

AO Sifan，WANG Houzhen，BAI Lu，et al.Spatial Optimization for CRYSTALS-Dilithium Digital Signature Scheme ［J］.J Wuhan Univ （Nat Sci Ed），2023，69（6）：709-718. DOI：10.14188/j.1671-8836.2022.0199（Ch）. DOI：

摘要

量子计算机的高速发展给传统公钥密码带来了潜在的威胁，基于格的数字签名算法CRYSTALS-Dilithium，虽然实现效率较传统公钥密码要高效得多，但是需要较大的存储资源空间保存公钥、私钥以及中间变量。针对上述问题，提出了节省矩阵所需要的空间和减少临时变量的数量两种优化方法，减少签名过程中的中间变量所需空间大小。通过本文的方法，可以减少大量程序运行所需要的存储资源，以便能更好地应用于存储资源受限的物联网设备中。对于三种不同安全级别的Dilithium算法，节省空间分别为23.53%，32.00%和38.89%。

Abstract

The rapid development of quantum computers has brought potential threats to traditional encryption and signature schemes. Although the lattice⁃based digital signature algorithm Crystals Dilithium has a breakneck speed, it needs ample space to store public keys, private keys, and intermediate variables. To address this issue, the paper introduces two methods aimed at reducing the space required by the matrix and the number of temporary variables. This, in turn,minimizes the space needed for the intermediate variables in the signature process. Through the method in this paper, we can reduce the space programs required to run on space-limited IOT devices. For the three different security levels of the Dilithium algorithm, the space savings are 23.53%, 32.00%, and 38.89%, respectively.

关键词

抗量子密码格密码数字签名物联网快速数论变换

Keywords

post-quantum cryptographylattice-based cryptographydigital signatureInternet of things(IoT)NTT(number theoretic transforms)

references

SHOR P W. Algorithms for quantum computation： Discrete logarithms and factoring［C］//Proceedings 35th Annual Symposium on Foundations of Computer Science. New York： IEEE Press， 2002： 124-134. DOI： 10.1109/SFCS.1994.365700http://dx.doi.org/10.1109/SFCS.1994.365700.

AJTAI M. Generating hard instances of lattice problems （extended abstract）［C］//Proceedings of the 28th Annual ACM Symposium on Theory of Computing. New York： ACM， 1996： 99-108. DOI： 10.1145/237814.237838http://dx.doi.org/10.1145/237814.237838.

REGEV O. On lattices， learning with errors， random linear codes， and cryptography［C］//Proceedings of the 37th Annual ACM Symposium on Theory of Computing. New York： ACM， 2005： 84-93. DOI： 10.1145/1060590.1060603http://dx.doi.org/10.1145/1060590.1060603.

GENTRY C. Fully homomorphic encryption using ideal lattices［C］//Proceedings of the 41st Annual ACM Symposium on Theory of Computing. New York： ACM， 2009： 169-178. DOI： 10.1145/1536414.1536440http://dx.doi.org/10.1145/1536414.1536440.

BRAKERSKI Z， VAIKUNTANATHAN V. Efficient fully homomorphic encryption from （standard） LWE［J］. SIAM Journal on Computing， 2014， 43（2）： 831-871. DOI: 10.1137/120868669http://dx.doi.org/10.1137/120868669.

GENTRY C， SAHAI A， WATERS B. Homomorphic encryption from learning with errors： Conceptually-simpler， asymptotically-faster， attribute-based［C］//Annual Cryptology Conference. Berlin： Springer， 2013： 75-92.DOI： 10.1007/978-3-642-40041-4_5http://dx.doi.org/10.1007/978-3-642-40041-4_5.

GENTRY C， PEIKERT C， VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions［C］//Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. New York： ACM， 2008： 197-206. DOI： 10.1145/1374376.1374407http://dx.doi.org/10.1145/1374376.1374407.

ALKIM E， DUCAS L， PÖPPELMANN T， et al. Post-quantum key exchange—A New Hope［DB/OL］.［2022-09-12］. https：//cryptojedi.org/papers/newhope-20151105.pdfhttps://cryptojedi.org/papers/newhope-20151105.pdf.

LYUBASHEVSKY V， PEIKERT C， REGEV O. On ideal lattices and learning with errors over rings［C］//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg： Springer， 2010： 1-23. DOI： 10.1007/978-3-642-13190-5_1http://dx.doi.org/10.1007/978-3-642-13190-5_1.

RENTERÍA-MEJÍA C P， VELASCO-MEDINA J. High-throughput ring-LWE cryptoprocessors［J］. IEEE Transactions on Very Large Scale Integration （VLSI） Systems， 2017， 25（8）： 2332-2345. DOI： 10.1109/TVLSI.2017.2697841http://dx.doi.org/10.1109/TVLSI.2017.2697841.

LYUBASHEVSKY V. Fiat-shamir with aborts： Applications to lattice and factoring-based signatures［C］//International Conference on the Theory and Application of Cryptology and Information Security. Berlin： Springer， 2009： 598-616. DOI： 10.1007/978-3-642-10366-7_35http://dx.doi.org/10.1007/978-3-642-10366-7_35.

LYUBASHEVSKY V. Lattice signatures without trapdoors［C］//Advances in Cryptology ― EUROCRYPT 2012. Berlin： Springer， 2012： 738-755. DOI： 10.1007/978-3-642-29011-4_43http://dx.doi.org/10.1007/978-3-642-29011-4_43.

DUCAS L， DURMUS A， LEPOINT T， et al. Lattice signatures and bimodal Gaussians［C］//Annual Cryptology Conference. Berlin： Springer， 2013： 40-56. DOI： 10.1007/978-3-642-40041-4_3http://dx.doi.org/10.1007/978-3-642-40041-4_3.

GÜNEYSU T， LYUBASHEVSKY V， PÖPPELMANN T. Practical lattice-based cryptography： A signature scheme for embedded systems［C］//International Workshop on Cryptographic Hardware and Embedded Systems. Berlin： Springer， 2012： 530-547. DOI： 10.1007/978-3-642-33027-8_31http://dx.doi.org/10.1007/978-3-642-33027-8_31.

BAI S， GALBRAITH S D. An improved compression technique for signatures based on learning with errors［C］//Cryptographers’ Track at the RSA Conference. Cham： Springer， 2014： 28-47. DOI： 10.1007/978-3-319-04852-9_2http://dx.doi.org/10.1007/978-3-319-04852-9_2.

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-4http://dx.doi.org/10.1007/s10623-014-9938-4.

BOS J， DUCAS L， KILTZ E， et al. CRYSTALS - Kyber： A CCA-secure module-lattice-based KEM［C］//2018 IEEE European Symposium on Security and Privacy （EuroS&P）. New York： IEEE Press， 2018： 353-367. DOI： 10.1109/EuroSP.2018.00032http://dx.doi.org/10.1109/EuroSP.2018.00032.

DUCAS L， KILTZ E， LEPOINT T， et al. CRYSTALS-Dilithium： A lattice-based digital signature scheme［J］. IACR Transactions on Cryptographic Hardware and Embedded Systems， 2018： 238-268. DOI： 10.46586/tches.v2018.i1.238-268http://dx.doi.org/10.46586/tches.v2018.i1.238-268.

FOUQUE P A， HOFFSTEIN J， KIRCHNER P， et al. Fast-fourier lattice-based compact signatures over NTRU［EB/OL］.［2022-09-30］. https：//falcon-sign.info/https://falcon-sign.info/.

ZHANG J， YU Y， FAN S Q， et al. Tweaking the asymmetry of asymmetric-key cryptography on lattices： KEMs and signatures of smaller sizes［C］//IACR International Conference on Public-Key Cryptography. Cham： Springer， 2020： 37-65.10.1007/978-3-030-45388-6_2. DOI: 10.1007/978-3-030-45388-6_2http://dx.doi.org/10.1007/978-3-030-45388-6_2.

陈朝晖，马原，荆继武. 格密码关键运算模块的硬件实现优化与评估［J］. 北京大学学报（自然科学版）， 2021， 57（4）： 595-604. DOI： 10.13209/j.0479-8023.2021.054http://dx.doi.org/10.13209/j.0479-8023.2021.054.

CHEN Z H， MA Y， JING J W. Hardware optimization and evaluation for crucial modules of lattice-based cryptography［J］. Acta Scientiarum Naturalium Universitatis Pekinensis， 2021， 57（4）： 595-604. DOI： 10.13209/j.0479-8023.2021.054（Chhttp://dx.doi.org/10.13209/j.0479-8023.2021.054（Ch）.

李斌，陈晓杰，冯峰，等. 后量子密码CRYSTALS-Kyber的FPGA多路并行优化实现［J］. 通信学报， 2022， 43（2）： 196-207. DOI： 10.11959/j.issn.1000-436x.2022026http://dx.doi.org/10.11959/j.issn.1000-436x.2022026.

LI B， CHEN X J， FENG F， et al. FPGA multi-unit parallel optimization and implementation of post-quantum cryptography CRYSTALS-Kyber［J］. Journal on Communications， 2022， 43（2）： 196-207. DOI： 10.11959/j.issn.1000-436x.2022026（Chhttp://dx.doi.org/10.11959/j.issn.1000-436x.2022026（Ch）.

吴志红，赵建宁，朱元，等. 国密算法和国际密码算法在车载单片机上应用的对比研究［J］. 信息网络安全， 2019（8）： 68-75. DOI： 10.3969/j.issn.1671-1122.2019.08.010http://dx.doi.org/10.3969/j.issn.1671-1122.2019.08.010.

WU Z H， ZHAO J N， ZHU Y， et al. Comparative study on application of Chinese cryptographic algorithms and international cryptographic algorithms in vehicle microcotrollers［J］. Netinfo Security， 2019（8）： 68-75. DOI： 10.3969/j.issn.1671-1122.2019.08.010（Chhttp://dx.doi.org/10.3969/j.issn.1671-1122.2019.08.010（Ch）.

DU C H， BAI G Q. Towards efficient polynomial multiplication for lattice-based cryptography［C］//2016 IEEE International Symposium on Circuits and Systems （ISCAS）. New York： IEEE Press， 2016： 1178-1181. DOI： 10.1109/ISCAS.2016.7527456http://dx.doi.org/10.1109/ISCAS.2016.7527456.

FENG X， LI S G， XU S F. RLWE-oriented high-speed polynomial multiplier utilizing multi-lane stockham NTT algorithm［J］. IEEE Transactions on Circuits and Systems Ⅱ： Express Briefs， 2020， 67（3）： 556-559. DOI： 10.1109/TCSII.2019.2917621http://dx.doi.org/10.1109/TCSII.2019.2917621.

ZHOU Z， HE D B， LIU Z， et al. A software/hardware co-design of crystals-dilithium signature scheme［J］. ACM Transactions on Reconfigurable Technology and Systems， 2021，14（2）：Article No. 11. DOI： 10.1145/3447812http://dx.doi.org/10.1145/3447812.

周朕，何德彪，罗敏，等. 紧凑的Aigis-sig数字签名方案软硬件协同实现方法［J］. 网络与信息安全学报， 2021， 7（2）： 64-76. DOI： 10.11959/j.issn.2096-109x.2021026http://dx.doi.org/10.11959/j.issn.2096-109x.2021026.

ZHOU Z， HE D B， LUO M， et al. Compact Aigis-sig digital signature scheme software and hardware co-implementation method［J］. Chinese Journal of Network and Information Security， 2021， 7（2）： 64-76. DOI： 10.11959/j.issn.2096-109x.2021026（Chhttp://dx.doi.org/10.11959/j.issn.2096-109x.2021026（Ch）.

RIVEST R L， SHAMIR A， ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems［J］. Communications of the ACM， 1978， 21（2）： 120-126. DOI： 10.1145/359340.359342http://dx.doi.org/10.1145/359340.359342.

陶云亭，孔凡玉，于佳，等. 抗量子格密码体制的快速数论变换算法研究综述［J］. 信息网络安全， 2021， 21（9）： 46-51. DOI： 10.3969/j.issn.1671-1122.2021.09.007http://dx.doi.org/10.3969/j.issn.1671-1122.2021.09.007.

TAO Y T， KONG F Y， YU J， et al. Survey of number theoretic transform algorithms for quantum-resistant lattice-based cryptography［J］. Netinfo Security， 2021， 21（9）： 46-51. DOI： 10.3969/j.issn.1671-1122.2021.09.007（Chhttp://dx.doi.org/10.3969/j.issn.1671-1122.2021.09.007（Ch）.

GÜNEYSU T， KRAUSZ M， ODER T， et al. Evaluation of lattice-based signature schemes in embedded systems［C］//2018 25th IEEE International Conference on Electronics， Circuits and Systems （ICECS）. New York： IEEE Press， 2019： 385-388. DOI： 10.1109/ICECS.2018.8617969http://dx.doi.org/10.1109/ICECS.2018.8617969.

KANNWISCHER M J， RIJNEVELD J， SCHWABE P， et al. pqm4： Testing and Benchmarking NIST PQC on ARM Cortex-M4［J］. IACR Cryptol EPrint Arch， 2019， 2019： 844. DOI: 10.1007/978-3-030-21568-2_14http://dx.doi.org/10.1007/978-3-030-21568-2_14.

KANNAN R. Improved algorithms for integer programming and related lattice problems［C］//Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. New York： ACM， 1983： 193-206. DOI： 10.1145/800061.808749http://dx.doi.org/10.1145/800061.808749.

DON C. Small solutions to polynomial equations， and low exponent RSA vulnerabilities［J］. Journal of Cryptology， 1997， 10（4）： 233-260. DOI： 10.1007/s001459900030http://dx.doi.org/10.1007/s001459900030.

van EMDE BOAS P. Another NP-complete problem and the complexity of computing short vectors in a lattice［R］. Amsterdam： University of Amsterdam， 1981.

AJTAI M. The shortest vector problem in L2 is NP-hard for randomized reductions （extended abstract）［C］//Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. New York： ACM， 1998： 10-19. DOI： 10.1145/276698.276705http://dx.doi.org/10.1145/276698.276705.

HENK M. Note on shortest and nearest lattice vectors［J］. Information Processing Letters， 1997， 61（4）： 183-188. DOI： 10.1016/S0020-0190（97）00019-7http://dx.doi.org/10.1016/S0020-0190（97）00019-7.

MICCIANCIO D. Improving lattice based cryptosystems using the Hermite normal form［C］//Cryptography and Lattices（LNCS 2146）. Berlin： Springer， 2001： 126-145. DOI： 10.1007/3-540-44670-2_11http://dx.doi.org/10.1007/3-540-44670-2_11.

GROOT BRUINDERINK L， HÜLSING A， LANGE T， et al. Flush， Gauss， and reload―A cache attack on the BLISS lattice-based signature scheme［C］//International Conference on Cryptographic Hardware and Embedded Systems. Berlin： Springer， 2016： 323-345. DOI： 10.1007/978-3-662-53140-2_16http://dx.doi.org/10.1007/978-3-662-53140-2_16.

PESSL P， BRUINDERINK L G， YAROM Y. To BLISS-B or not to be： Attacking strongSwan’s implementation of post-quantum signatures［C］//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2017： 1843-1855. DOI： 10.1145/3133956.3134023http://dx.doi.org/10.1145/3133956.3134023.

LIANG Z C， ZHAO Y L. Number theoretic transform and its applications in lattice-based cryptosystems： A survey［EB/OL］. 2022： arXiv： 2211.13546. https：//arxiv.org/abs/2211.13546https://arxiv.org/abs/2211.13546.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

一种杀毒软件升级流程的安全性分析方法

基于轻量级数字签名的药品防伪追溯系统的设计

一个前向和后向安全的数字签名方案

基于保形迭代深度问题的公钥密码体制