Analog In-memory Circuit Design of Polynomial Multiplication for Lattice Cipher Acceleration Application
Authors: 
Sichun Du, Jun Li, Chen Sun, Pingdan Xiao, Qinghui Hong, Jiliang ZhangAuthors Info & Claims
Article No.: 88, Pages 1 - 24
Abstract
As the core operation of lattice cipher, large-scale polynomial multiplication is the biggest computational bottleneck in its realization process. How to quickly calculate polynomial multiplication under resource constraints has become an urgent problem to be solved in the hardware implementation of lattice ciphers. Therefore, an analog in-memory circuit for fast polynomial multiplication calculation is proposed. First, an in-memory computing circuit for Discrete Fourier Transform and Inverse Discrete Fourier Transform based on memristor array is designed. On this basis, a fully analog circuit that can realize polynomial multiplication in one step is designed. Compared with traditional hardware implementation, the in-memory calculation method used in this article decreases the calculation time of polynomial multiplication to the microsecond level, which greatly improves the speed of lattice cipher encryption and decryption. For the specific examples in this article, PSPICE simulation shows that the average accuracy of the calculation result is above 99.90%.
References
[1]
Junwei Sun, Yangyang Wang, Peng Liu, Shiping Wen, and Yanfeng Wang. 2023. Memristor-based neural network circuit with multimode generalization and differentiation on Pavlov associative memory. IEEE Transactions on Cybernetics 53, 5 (2023), 3351–3362. DOI:
[2]
Junwei Sun, Yangyang Wang, Peng Liu, and Shiping Wen. 2023. Memristor-based circuit design of PAD emotional space and its application in mood congruity. IEEE Internet of Things Journal (2023), 1–1. DOI:
[3]
Junwei Sun, Linhao Zhao, Shiping Wen, and Yanfeng Wang. 2023. Memristor-based neural network circuit of emotional habituation with contextual dependency. IEEE Internet of Things Journal (2023), 1–1. DOI:
[4]
Qinghui Hong, Haotian Fu, Yiyang Liu, and Jiliang Zhang. 2023. In-memory computing circuit implementation of complex valued hopfield neural network for efficient portrait restoration. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2023), 1–1. DOI:
[5]
W. Xie, C. Wang, and H. Lin. 2021. A fractional-order multistable locally active memristor and its chaotic system with transient transition, state jump. Nonlinear Dynamics 104, 4 (2021), 4523–4541. DOI:
[6]
Nitesh Aggarwal, C. P. Gupta, and Iti Sharma. 2014. Fully homomorphic symmetric scheme without bootstrapping. In Proceedings of the 2014 International Conference on Cloud Computing and Internet of Things. IEEE, 14–17. DOI:
[7]
Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. 2016. Post-quantum key exchange: A new hope. In Proceedings of the 25th USENIX Conference on Security Symposium. USENIX Association, 327C343. https://eprint.iacr.org/2015/1092.
[8]
S. Arish and R. K. Sharma. 2015. An efficient binary multiplier design for high speed applications using Karatsuba algorithm and Urdhva-Tiryagbhyam algorithm. In Proceedings of the 2015 Global Conference on Communication Technologies (GCCT’15). IEEE, 192–196. DOI:
[9]
Tianyu Bai, Spencer Davis, Juanjuan Li, and Hai Jiang. 2014. Analysis and acceleration of NTRU lattice-based cryptographic system. In Proceedings of the 15th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD’14). IEEE, 1–6. DOI:
[10]
Jean-Claude Bajard, Julien Eynard, Nabil Merkiche, and Thomas Plantard. 2015. RNS arithmetic approach in lattice-based cryptography: Accelerating the “Rounding-off” core procedure. In Proceedings of the 2015 IEEE 22nd Symposium on Computer Arithmetic. IEEE, 113–120. DOI:
[11]
Rouzbeh Behnia, Muslum Ozgur Ozmen, and Attila Altay Yavuz. 2020. Lattice-based public key searchable encryption from experimental perspectives. IEEE Transactions on Dependable and Secure Computing 17, 6 (2020), 1269–1282. DOI:
[12]
Joppe W. Bos, Craig Costello, Michael Naehrig, and Douglas Stebila. 2015. Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In Proceedings of the 2015 IEEE Symposium on Security and Privacy. IEEE, 553–570. DOI:
[13]
Donald Donglong Chen, Nele Mentens, Frederik Vercauteren, Sujoy Sinha Roy, Ray C. C. Cheung, Derek Pao, and Ingrid Verbauwhede. 2015. High-speed polynomial multiplication architecture for ring-LWE and SHE cryptosystems. IEEE Transactions on Circuits and Systems I: Regular Papers 62, 1 (2015), 157–166. DOI:
[14]
Yijun Cui, Kan Yao, Ziying Ni, Chenghua Wang, and Weiqiang Liu. 2021. Efficient hardware implementation of MLWE lattice based cryptography. Journal of Cyber Security 6, 6 (2021), 40–50.
[15]
Quanli Deng and Linmao Yang. 2020. Four-wing hidden attractors with one stable equilibrium point. International Journal of Bifurcation and Chaos 30 (May 2020), 2050086. DOI:
[16]
Léo Ducas, Alain Durmus, Tancrède Lepoint, and Vadim Lyubashevsky. 2013. Lattice signatures and bimodal Gaussians. In Annual Cryptology Conference. Springer, Berlin, 40–56. DOI:
[17]
Qinghui Hong, Hegan Chen, Jingru Sun, and Chunhua Wang. 2022. Memristive circuit implementation of a self-repairing network based on biological astrocytes in robot application. IEEE Transactions on Neural Networks and Learning Systems 33, 5 (2022), 2106–2120. DOI:
[18]
Murat Burhan İlter, Neşe Koçak, Erkan Uslu, Oǧuz Yayla, and Nergiz Yuca. 2021. On the number of arithmetic operations in NTT-based polynomial multiplication in kyber and dilithium cryptosystems. In Proceedings of the 2021 14th International Conference on Security of Information and Networks (SIN’21). IEEE, 1–7. DOI:
[19]
Jintai Ding. 2012. A simple provably secure key exchange scheme based on the learning with errors problem. IACR Cryptol. ePrint Arch. 2012 (2012), 688. https://eprint.iacr.org/2012/688.
[20]
Sangpyo Kim, Wonkyung Jung, Jaiyoung Park, and Jung Ho Ahn. 2020. Accelerating number theoretic transformations for bootstrappable homomorphic encryption on GPUs. In Proceedings of the 2020 IEEE International Symposium on Workload Characterization (IISWC’20). IEEE, 264–275. DOI:
[21]
Wai-Kong Lee, Hwajeong Seo, Zhenfei Zhang, and Seong Oun Hwang. 2022. TensorCrypto: High throughput acceleration of lattice-based cryptography using tensor core on GPU. IEEE Access 10 (2022), 20616–20632. DOI:
[22]
Seungho Lee and Youngmin Kim. 2020. Implementation of modular subtraction unit for NTT-based polynomial multiplier. In Proceedings of the 2020 International SoC Design Conference (ISOCC’20). IEEE, 284–285. DOI:
[23]
Vadim Lyubashevsky. 2012. Lattice signatures without trapdoors. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, 738–755. DOI:
[24]
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2013. On ideal lattices and learning with errors over rings. Journal of the ACM (JACM) 60, 6 (2013), 1–35. DOI:
[25]
Jose Maria Bermudo Mera, Furkan Turan, Angshuman Karmakar, Sujoy Sinha Roy, and Ingrid Verbauwhede. 2020. Compact domain-specific co-processor for accelerating module lattice-based KEM. In Proceedings of the 2020 57th ACM/IEEE Design Automation Conference (DAC’20). IEEE, 1–6. DOI:
[26]
Anand Mehta, C. B. Bidhul, Sajeevan Joseph, and P. Jayakrishnan. 2013. Implementation of single precision floating point multiplier using Karatsuba algorithm. In Proceedings of the 2013 International Conference on Green Computing, Communication and Conservation of Energy (ICGCE’13). IEEE, 254–256. DOI:
[27]
Ahmet Can Mert, Emre Karabulut, Erdinç Öztürk, Erkay Savaş, Michela Becchi, and Aydin Aysu. 2020. A flexible and scalable NTT hardware: Applications from homomorphically encrypted deep learning to post-quantum cryptography. In Proceedings of the 2020 Design, Automation Test in Europe Conference Exhibition (DATE’20). IEEE, 346–351. DOI:
[28]
A. C. Mert, E Öztürk, and E. Sava. 2020. FPGA implementation of a run-time configurable NTT-based polynomial multiplication hardware. Microprocessors and Microsystems 78 (2020), 103219. DOI:
[29]
Victor S. Miller. 1985. Use of elliptic curves in cryptography. In Conference on the Theory and Application of Cryptographic Techniques. Spnnger-Verlag, Berlin, 417–426. DOI:
[30]
Hamid Nejatollahi, Rosario Cammarota, and Nikil Dutt. 2019. Flexible NTT accelerators for RLWE lattice-based cryptography. In Proceedings of the 2019 IEEE 37th International Conference on Computer Design (ICCD’19). IEEE, 329–332. DOI:
[31]
Muhamad Nursalman, Arif Sasongko, Yusuf Kurniawan, and Kuspriyanto. 2014. Improved generalizations of the Karatsuba algorithm in GF(\(2^n\)). In Proceedings of the 2014 International Conference of Advanced Informatics: Concept, Theory and Application (ICAICTA’14). IEEE, 185–190. DOI:
[32]
Thomas Pöppelmann and Tim Güneysu. 2012. Towards efficient arithmetic for lattice-based cryptography on reconfigurable hardware. In International Conference on Cryptology and Information Security in Latin America. Springer-Verlag, Berlin, 139–158. DOI:
[33]
Oded Regev. 2009. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM) 56, 6 (2009), 1–40. DOI:
[34]
C. P. Rentería-Mejía, A. López-Parrado, and J. Velasco-Medina. 2014. Hardware design of FFT polynomial multipliers. In Proceedings of the 2014 IEEE 5th Latin American Symposium on Circuits and Systems. IEEE, 1–4. DOI:
[35]
P. W. Shor. 1999. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review 41, 2 (1999), 303–332. DOI:
[36]
P. W. Shor. 1994. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science. IEEE, 124–134. DOI:
[37]
Damien Stehlé and Ron Steinfeld. 2011. Making NTRU as secure as worst-case problems over ideal lattices. In Proceedings of the 30th Annual International Conference on Theory and Applications of Cryptographic Techniques: Advances in Cryptology. Springer, Berlin, 27–47. DOI:
[38]
Yang Su, Bai-Long Yang, Chen Yang, Ze-Peng Yang, and Yi-Wei Liu. 2022. A highly unified reconfigurable multicore architecture to speed up NTT/INTT for homomorphic polynomial multiplication. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 30, 8 (2022), 993–1006. DOI:
[39]
Weihang Tan, Antian Wang, Yingjie Lao, Xinmiao Zhang, and Keshab K. Parhi. 2021. Pipelined high-throughput NTT architecture for lattice-based cryptography. In Proceedings of the 2021 Asian Hardware Oriented Security and Trust Symposium (AsianHOST’21). IEEE, 1–4. DOI:
[40]
Lipeng Wan, Fangyu Zheng, and Jingqiang Lin. 2021. TESLAC: Accelerating lattice-based cryptography with AI accelerator. In International Conference on Security and Privacy in Communication Systems. Springer, Cham, 249–269. DOI:
[41]
Vijay Kumar Yadav, Shekhar Verma, and S. Venkatesan. 2021. An efficient and light weight polynomial multiplication for ideal lattice-based cryptography. Multimedia Tools and Applications 80, 2 (2021), 3089–3120. DOI:
[42]
Fei Yu, Xinxin Kong, Abdulmajeed Abdullah Mohammed Mokbel, Wei Yao, and Shuo Cai. 2023. Complex dynamics, hardware implementation and image encryption application of multiscroll memeristive hopfield neural network with a novel local active memeristor. IEEE Transactions on Circuits and Systems II: Express Briefs 70, 1 (2023), 326–330. DOI:
[43]
Fei Yu, Hui Shen, Qiulin Yu, Xinxin Kong, Pradip Kumar Sharma, and Shuo Cai. 2023. Privacy protection of medical data based on multi-scroll memristive hopfield neural network. IEEE Transactions on Network Science and Engineering 10, 2 (2023), 845–858. DOI:
[44]
Xinmiao Zhang and Keshab K. Parhi. 2021. Reduced-complexity modular polynomial multiplication for R-LWE cryptosystems. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP’21). IEEE, 7853–7857. DOI:
[45]
Xiaojun Zhang, Chunxiang Xu, Huaxiong Wang, Yuan Zhang, and Shixiong Wang. 2021. FS-PEKS: Lattice-based forward secure public-key encryption with keyword search for cloud-assisted industrial Internet of Things. IEEE Transactions on Dependable and Secure Computing 18, 3 (2021), 1019–1032. DOI:
[46]
L. Zhe, H. Seo, S. S. Roy, Johann Groschdl, and I. Verbauwhede. 2015. Efficient Ring-LWE encryption on 8-bit AVR processors. In International Workshop on Cryptographic Hardware and Embedded Systems. Springer, Berlin, 663–682. DOI:
Index Terms
- Analog In-memory Circuit Design of Polynomial Multiplication for Lattice Cipher Acceleration Application
Recommendations
A novel tree-based representation for evolving analog circuits and its application to memristor-based pulse generation circuit
AbstractWhen applying evolutionary algorithms to circuit design automation, circuit representation is the first consideration. There have been several studies applying different circuit representations. However, they still have some problems, such as lack ...
Interesting Results Arising from Karatsuba Multiplication - Montgomery family of formulae
ICCCT '15: Proceedings of the Sixth International Conference on Computer and Communication Technology 2015Multiplication is a frequently encountered operation in the implementation of cryptography. This paper shows that Montgomery's family of 3-way (degree 2 polynomial) multiplication algorithms can be obtained from the well known Karatsuba's multiplication ...
Design of Memristor-Based Combinational Logic Circuits
AbstractThis paper proposes three modified memristor ratioed logic (MRL) gates: NOT, NOR and A AND (NOR B) (i.e., ), each of which only needs 1 memristor and 1 NMOS. Based on the modified MRL gates, we design some combinational logic circuits, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2024
505 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Journal Family
Publication History
Published: 11 September 2024
Online AM: 26 June 2023
Accepted: 20 June 2023
Revised: 21 May 2023
Received: 09 December 2022
Published in TECS Volume 23, Issue 6
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Natural Science Foundation of China
- Natural Science Foundation of Hunan Province, China
- CCF-Huawei Populus Grove Fund
- Special Funds for the Construction of Innovative Provinces in Hunan Province
- Changsha Science and Technology Project
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 401Total Downloads
- Downloads (Last 12 months)248
- Downloads (Last 6 weeks)43
Reflects downloads up to 28 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in