Hardware Optimization and Evaluation for Crucial Modules of Lattice-based Cryptography

CHEN Zhaohui1,2, MA Yuan2,3,†, JING Jiwu1,4

1. School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing 100049; 2. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093; 3. School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049; 4. School of Software and Microelectronics, Peking University, Beijing 102600; † Corresponding author, E-mail: mayuan@iie.ac.cn

Abstract To improve the efficiency of lattice-based cryptography in practical applications, the optimization technology of polynomial multiplication in lattice-based cryptography is proposed. The polynomial coefficients are stored in a ping-pong structure to improve the bandwidth. By eliminating pre-scale operations, 10.5% of modular multiplication operations and 16.7% of storage space are saved. The structure based on look-up table shift register and three-input adder is adopted to reduce the logical resource occupation. The pipeline structure with optional stages is designed to make the butterfly module in polynomial multiplication meet the timing requirements of different cryptographic hardware systems. The evaluation results show that the maximum frequency of low-area, balanced and high-performance implementations of the optimized butterfly unit can reach 150, 250 and 350 MHZ, respectively. Compared with the existing implementation technologies, the optimized hardware implementation can achieve higher operating frequency with a smaller circuit area, which improves the efficiency of polynomial multiplication module by 22.8%. Key words post-quantum cryptography; polynomial multiplication; number theoretic transformation; butterfly operation; FPGA

[1] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 1997, 26(5):

1484–1509 [2] Gidney C, Ekera M. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits [EB/OL]. (2019–05–23) [2020–02–21]. https://arxiv.org/ abs/1905.09749 [3] Nejatollahi H, Dutt N, Ray S, et al. Post-quantum lattice-based cryptography implementations: a survey. ACM Computing Surveys, 2019, 51(6): 1–41 [4] Bos J, Costello C, Ducas L, et al. Frodo: take off the ring! practical, quantum-secure key exchange from LWE // Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016: 1006–1018 [5] 张平原, 蒋瀚, 蔡杰, 等. 格密码技术近期研究进展. 计算机研究与发展, 2017, 54(10): 2121–2129 [6] Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over ring // Annual International Conference on the Theory and Applications of Cryptographic Techniques. French Riviera, 2010: 1–23 [7] Pöppelmann T, Güneysu T. Towards efficient arithmetic for lattice-based cryptography on reconfigurable hardware // Proceedings of LATINCRYPT’12. Berlin Heidelberg: Springer, 2012: 139–158 [8] 芮康康, 王成华, 范赛龙, 等. 一种高性能R-LWE格加密算法的电路结构及其FPGA实现. 数据采集与处理, 2019, 34(4): 689–696 [9] Alkim E, Ducas L, Pöppelmann T, et al. Post-quantum key exchange—a new hope // Proceedings of the 25th USENIX Security’16. Austin: USENIX Association, 2016: 327–343 [10] Ducas L, Durmus A, Lepoint T, et al. Lattice signatures and bimodal Gaussians // Proceedings of CRYPTO’13. Berlin: Springer, 2013: 40–56 [11] Basu K, Soni D, Nabeel M, et al. NIST post-quantum cryptography—a hardware evaluation study [EB/OL]. (2019–01–17) [2020–03–15]. https://eprint.iacr.org/20 19/047.pdf [12] Pöppelmann T, Ducas L, Güneysu T. Enhanced lattice-based signatures on reconfigurable hardware // Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin Heidelberg: Springer, 2014: 353–370 [13] Roy S S, Vercauteren F, Mentens N, et al. Compact ring-lwe cryptoprocessor // Proceedings of International Workshop on Cryptographic Hardware and

Embedded Systems. Berlin Heidelberg: Springer, 2014: 371–391 [14] Oder T, Guneysu T. Implementing the Newhope — simple key exchange on low-cost FPGAS // Lecture Notes in Computer Science. Cham: Springer, 2017: 128–142 [15] Poppelmann T. Efficient implementation of ideal lattice-based cryptography [D]. Bochum: Ruhruniversity Bochum, 2017 [16] Barrett P. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor // Proceedings of CRYPTO’86. Berlin: Springer, 1987: 311–323 [17] Liu Z, Seo H, Roy S S, et al. Efficient ring-lwe encryption on 8-bit avr processors // Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin Heidelberg: Springer, 2015: 663–682 [18] Xing Y, Li S. An efficient implementation of the Newhope key exchange on FPGAS. IEEE Transactions on Circuits and Systems I: Regular Papers, 2020, 67(3): 866–878 [19] Banerjee U, Ukyab T S, Chandrakasan A P. Sapphire: a configurable crypto-processor for post-quantum lattice-based protocols. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019, 2019(4): 17–61 [20] Montgomery P L. Modular multiplication without trial division. Mathematics of Computation, 1985, 44: 519–521 [21] Jati A, Gupta N, Chattopadhyay A, et al. SPQCOP: side-channel protected post-quantum cryptoprocessor [EB/OL]. (2019–06–30) [2020–02–21]. https://eprint.iacr. org/2019/765.pdf. [22] Longa P, Naehrig M. Speeding up the number theoretic transform for faster ideal lattice-based cryptography // Proceedings of International Conference on Cryptology and Network Security. Berlin: Springer, 2016: 124–139 [23] Kuo P C, Li W D, Chen Y W, et al. High performance post-quantum key exchange on FPGAS [EB/OL]. (2017–06–12) [2020–02–21]. https://eprint.iacr.org/ 2017/690.pdf [24] Xilinx. Ug949—ultrafast design methodology guide for the vivado design suite (v2019.1) [EB/OL]. (2019–06–26) [2020–02–21]. https://www.xilinx.com/ support/documentation/sw_manuals/xilinx2019_1/ug9 49-vivado-design-methodology.pdf [25] Neng Z, Bohan Y, Chen C, et al. Highly efficient architecture of NEWHOPE-NIST on FPGA using lowcomplexity NTT/INTT. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020 (2): 49–72 [26] Fritzmann T, Sharif U, Mullergritschneder D, et al. Towards reliable and secure post-quantum coprocessors based on RISC-V // Design, Automation, and Test in Europe. Piscataway, 2019: 1148–1153