The security of cryptographic algorithms based on integer factorization and discrete logarithm will be threatened by quantum computers in future.Since December 2016,the National Institute of Standards and Technology(N...The security of cryptographic algorithms based on integer factorization and discrete logarithm will be threatened by quantum computers in future.Since December 2016,the National Institute of Standards and Technology(NIST)has begun to solicit post-quantum cryptographic(PQC)algorithms worldwide.CRYSTALS-Kyber was selected as the standard of PQC algorithm after 3 rounds of evaluation.Meanwhile considering the large resource consumption of current implementation,this paper presents a lightweight architecture for ASICs and its implementation on FPGAs for prototyping.In this implementation,a novel compact modular multiplication unit(MMU)and compression/decompression module is proposed to save hardware resources.We put forward a specially optimized schoolbook polynomial multiplication(SPM)instead of number theoretic transform(NTT)core for polynomial multiplication,which can reduce about 74%SLICE cost.We also use signed number representation to save memory resources.In addition,we optimize the hardware implementation of the Hash module,which cuts off about 48%of FF consumption by register reuse technology.Our design can be implemented on Kintex-7(XC7K325T-2FFG900I)FPGA for prototyping,which occupations of 4777/4993 LUTs,2661/2765 FFs,1395/1452 SLICEs,2.5/2.5 BRAMs,and 0/0 DSP respective of client/server side.The maximum clock frequency can reach at 244 MHz.As far as we know,our design consumes the least resources compared with other existing designs,which is very friendly to resource-constrained devices.展开更多
With the rapid development of quantum computers capable of realizing Shor’s algorithm,existing public key-based algorithms face a significant security risk.Crystals-Kyber has been selected as the only key encapsulati...With the rapid development of quantum computers capable of realizing Shor’s algorithm,existing public key-based algorithms face a significant security risk.Crystals-Kyber has been selected as the only key encapsulation mechanism(KEM)algorithm in the National Institute of Standards and Technology(NIST)Post-Quantum Cryptography(PQC)competition.In this study,we present a portable and efficient implementation of a Crystals-Kyber post-quantum KEM based on WebAssembly(Wasm),a recently released portable execution framework for high-performance web applications.Until now,most Kyber implementations have been developed with native programming languages such as C and Assembly.Although there are a few previous Kyber implementations based on JavaScript for portability,their performance is significantly lower than that of implementations based on native programming languages.Therefore,it is necessary to develop a portable and efficient Kyber implementation to secure web applications in the quantum computing era.Our Kyber software is based on JavaScript and Wasm to provide portability and efficiency while ensuring quantum security.Namely,the overall software is written in JavaScript,and the performance core parts(secure hash algorithm-3-based operations and polynomial multiplication)are written in Wasm.Furthermore,we parallelize the number theoretic transform(NTT)-based polynomial multiplication using single instruction multiple data(SIMD)functionality,which is available in Wasm.The three steps in the NTT-based polynomial multiplication have been parallelized with Wasm SIMD intrinsic functions.Our software outperforms the latest reference implementation of Kyber developed in JavaScript by×4.02(resp.×4.32 and×4.1),×3.42(resp.×3.52 and×3.44),and×3.41(resp.×3.44 and×3.38)in terms of key generation,encapsulation,and decapsulation on Google Chrome(resp.Firefox,and Microsoft Edge).As far as we know,this is the first software implementation of Kyber with Wasm technology in the web environment.展开更多
公钥密码学对全球数字信息系统的安全起着至关重要的作用。然而,随着量子计算机研究的发展和Shor算法等的出现,公钥密码学的安全性受到了潜在的极大的威胁。因此,能够抵抗量子计算机攻击的密码算法开始受到密码学界的关注,美国国家标准...公钥密码学对全球数字信息系统的安全起着至关重要的作用。然而,随着量子计算机研究的发展和Shor算法等的出现,公钥密码学的安全性受到了潜在的极大的威胁。因此,能够抵抗量子计算机攻击的密码算法开始受到密码学界的关注,美国国家标准与技术研究院(National Institute of Standards and Technology,NIST)发起了后量子密码(Post-quantum cryptography,PQC)算法标准全球征集竞赛。在参选的算法中,基于格的算法在安全性、公钥私钥尺寸和运算速度中达到了较好的权衡,因此是最有潜力的后量子加密算法体制。而CRYSTALS-KYBER作为基于格的密钥封装算法(Key encapsulation mechanism,KEM),通过了该全球征集竞赛的三轮遴选。对于后量子密码算法,算法的硬件实现效率是一个重要评价指标。因此,本文使用高层次综合工具(High-level synthesis,HLS),针对CRYSTALS-KYBER的三个主模块(密钥生成,密钥封装和密钥解封装),在不同参数集下探索了硬件设计的实现和优化空间。作为一种快速便捷的电路设计方法,HLS可以用来对不同算法的硬件实现进行高效和便捷的探索。本文利用该工具,对CRYSTALS-KYBER的软件代码进行了分析,并尝试不同的组合策略来优化HLS硬件实现结果,并最终获得了最优化的电路结构。同时,本文编写了tcl-perl协同脚本,以自动化地搜索最优优化策略,获得最优电路结构。实验结果表明,适度优化循环和时序约束可以大大提高HLS综合得到的KYBER电路性能。与已有的软件实现相比,本文具有明显的性能优势。与HLS实现工作相比,本文对Kyber-512的优化使得封装算法的性能提高了75%,解封装算法的性能提高了55.1%。与基准数据相比,密钥生成算法的性能提高了44.2%。对于CRYSTALS-KYBER的另外两个参数集(Kyber-768和Kyber-1024),本文也获得了类似的优化效果。展开更多
基金supported in part by the Shaanxi Province Key R&D Program(2019ZDLGY12-09)in part by the Higher Education Discipline Innovation 111 project(B16037)+1 种基金in part by the Shaanxi innovation team project(2018TD-007)in part by the China National Natural Science Foundation(62102298).
文摘The security of cryptographic algorithms based on integer factorization and discrete logarithm will be threatened by quantum computers in future.Since December 2016,the National Institute of Standards and Technology(NIST)has begun to solicit post-quantum cryptographic(PQC)algorithms worldwide.CRYSTALS-Kyber was selected as the standard of PQC algorithm after 3 rounds of evaluation.Meanwhile considering the large resource consumption of current implementation,this paper presents a lightweight architecture for ASICs and its implementation on FPGAs for prototyping.In this implementation,a novel compact modular multiplication unit(MMU)and compression/decompression module is proposed to save hardware resources.We put forward a specially optimized schoolbook polynomial multiplication(SPM)instead of number theoretic transform(NTT)core for polynomial multiplication,which can reduce about 74%SLICE cost.We also use signed number representation to save memory resources.In addition,we optimize the hardware implementation of the Hash module,which cuts off about 48%of FF consumption by register reuse technology.Our design can be implemented on Kintex-7(XC7K325T-2FFG900I)FPGA for prototyping,which occupations of 4777/4993 LUTs,2661/2765 FFs,1395/1452 SLICEs,2.5/2.5 BRAMs,and 0/0 DSP respective of client/server side.The maximum clock frequency can reach at 244 MHz.As far as we know,our design consumes the least resources compared with other existing designs,which is very friendly to resource-constrained devices.
基金This work was supported by Institute of Information&communications Technology Planning&Evaluation(IITP)grant funded by the Korea government(MSIT)(No.2022-0-01019,Development of eSIM security platform technology for edge devices to expand the eSIM ecosystem)This was partly supported by the MSIT(Ministry of Science and ICT)Korea,under the ITRC(Information Technology Research Center)support program(IITP-2022-RS-2022-00164800)supervised by the IITP(Institute for Information&Communications Technology Planning&Evaluation).
文摘With the rapid development of quantum computers capable of realizing Shor’s algorithm,existing public key-based algorithms face a significant security risk.Crystals-Kyber has been selected as the only key encapsulation mechanism(KEM)algorithm in the National Institute of Standards and Technology(NIST)Post-Quantum Cryptography(PQC)competition.In this study,we present a portable and efficient implementation of a Crystals-Kyber post-quantum KEM based on WebAssembly(Wasm),a recently released portable execution framework for high-performance web applications.Until now,most Kyber implementations have been developed with native programming languages such as C and Assembly.Although there are a few previous Kyber implementations based on JavaScript for portability,their performance is significantly lower than that of implementations based on native programming languages.Therefore,it is necessary to develop a portable and efficient Kyber implementation to secure web applications in the quantum computing era.Our Kyber software is based on JavaScript and Wasm to provide portability and efficiency while ensuring quantum security.Namely,the overall software is written in JavaScript,and the performance core parts(secure hash algorithm-3-based operations and polynomial multiplication)are written in Wasm.Furthermore,we parallelize the number theoretic transform(NTT)-based polynomial multiplication using single instruction multiple data(SIMD)functionality,which is available in Wasm.The three steps in the NTT-based polynomial multiplication have been parallelized with Wasm SIMD intrinsic functions.Our software outperforms the latest reference implementation of Kyber developed in JavaScript by×4.02(resp.×4.32 and×4.1),×3.42(resp.×3.52 and×3.44),and×3.41(resp.×3.44 and×3.38)in terms of key generation,encapsulation,and decapsulation on Google Chrome(resp.Firefox,and Microsoft Edge).As far as we know,this is the first software implementation of Kyber with Wasm technology in the web environment.
文摘公钥密码学对全球数字信息系统的安全起着至关重要的作用。然而,随着量子计算机研究的发展和Shor算法等的出现,公钥密码学的安全性受到了潜在的极大的威胁。因此,能够抵抗量子计算机攻击的密码算法开始受到密码学界的关注,美国国家标准与技术研究院(National Institute of Standards and Technology,NIST)发起了后量子密码(Post-quantum cryptography,PQC)算法标准全球征集竞赛。在参选的算法中,基于格的算法在安全性、公钥私钥尺寸和运算速度中达到了较好的权衡,因此是最有潜力的后量子加密算法体制。而CRYSTALS-KYBER作为基于格的密钥封装算法(Key encapsulation mechanism,KEM),通过了该全球征集竞赛的三轮遴选。对于后量子密码算法,算法的硬件实现效率是一个重要评价指标。因此,本文使用高层次综合工具(High-level synthesis,HLS),针对CRYSTALS-KYBER的三个主模块(密钥生成,密钥封装和密钥解封装),在不同参数集下探索了硬件设计的实现和优化空间。作为一种快速便捷的电路设计方法,HLS可以用来对不同算法的硬件实现进行高效和便捷的探索。本文利用该工具,对CRYSTALS-KYBER的软件代码进行了分析,并尝试不同的组合策略来优化HLS硬件实现结果,并最终获得了最优化的电路结构。同时,本文编写了tcl-perl协同脚本,以自动化地搜索最优优化策略,获得最优电路结构。实验结果表明,适度优化循环和时序约束可以大大提高HLS综合得到的KYBER电路性能。与已有的软件实现相比,本文具有明显的性能优势。与HLS实现工作相比,本文对Kyber-512的优化使得封装算法的性能提高了75%,解封装算法的性能提高了55.1%。与基准数据相比,密钥生成算法的性能提高了44.2%。对于CRYSTALS-KYBER的另外两个参数集(Kyber-768和Kyber-1024),本文也获得了类似的优化效果。
