NTT 기반의 효율적인 다항식 곱셈기 설계
Design of Efficient NTT-based Polynomial Multiplier
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
현재 사용되고 있는 RSA, ECC와 같은 공개키 암호화 기법은 소인수분해와 같은 현재의 컴퓨터로 계산이 오래 걸리는 수학적 문제를 암호화에 사용했다. 그러나 양자컴퓨터가 상용화된다면 Shor Algorithm에 의해 기존의 암호화 시스템은 쉽게 깨질수 있다. 그로 인해 Quantum-resistant 한 암호화 알고리즘의 도입이 필요해졌고, 그중 하나로 Lattice-based Cryptography가제안되고 있다. 이 암호화 알고리즘은 Polynomial Ring에서 연산이 행해지고, 그중 Polynomial Multiplication이 가장 큰 연산 시간을 차지한다. 그러므로 다항식 곱셈 계산을 빠르게 하는 하드웨어 모듈이 필요하고, 그중 Finite Field에서 연산 되는FFT인 Number Theoretic Transform을 이용해서 다항식 곱셈을 계산하는 8-point NTT-based Polynomial Multiplier 모듈을 설계하고 시뮬레이션했다. HDL을 사용하여 로직검증을 수행하였고, Hspice를 사용하여 트랜지스터 수준에서 제안된 설계가 지연시간과 전력소모에서 얼마나 개선되는지를 비교 분석하였다. 제안된 설계에서 평균 지연속도 30%의 개선과 8% 이상의 전력소모 감소 효과를 볼 수 있었다
Abstract
Public-key cryptographic algorithms such as RSA and ECC, which are currently in use, have used mathematicalproblems that would take a long time to calculate with current computers for encryption. But those algorithms can beeasily broken by the Shor algorithm using the quantum computer. Lattice-based cryptography is proposed as newpublic-key encryption for the post-quantum era. This cryptographic algorithm is performed in the Polynomial Ring, andpolynomial multiplication requires the most processing time. Therefore, a hardware model module is needed to calculatepolynomial multiplication faster. Number Theoretic Transform, which called NTT, is the FFT performed in the finitefield. The logic verification was performed using HDL, and the proposed design at the transistor level using Hspice wascompared and analyzed to see how much improvement in delay time and power consumption was achieved. In theproposed design, the average delay was improved by 30% and the power consumption was reduced by more than 8%.
참고문헌 (10)
- H. Nejatollahi, "Post-Quantum LatticeBased Cryptography Implementations: A Survey", ACM Computing Surveys, 51(6), pp.1~41 (2019)[DOI]
- R. C. Agarwal, "Number Theoretic Transforms to Implement Fast Digital Convolution", Proceedings of the IEEE, 63(4), pp.550~560 (1975)[DOI]
- G. X. Yao, "Recofigurable Number Theoretic Transform Architectures for Cryptographic Applications", Proc. of the International Conference on Field-Programmable Technology, pp.308~331 (2010)
- P. Longa, "Cryptology and Network Security", Springer, Cham (2016)[DOI]
- C. P. Rentería-Mejía, "Hardware Design of an NTT-based Polynomial Multiplier", Proc. of the IX Southern Conference on Programmable Logic (SPL), pp.1~5 (2014)
- A. C. Mert, "Design and Implementation of a Fast and Scalable NTT-Based Polynomial Multiplier Architecture", Proc. of the Euromicro Conference on Digital System Design (DSD), pp.253~260 (2019)
- J. G. Proakis, "Digital Signal Processing" (2007), Prentice Hall
- A. C. Mert, "FPGA implementation of a run-time configurable NTT-based polynomial multiplication hardware", Microprocessors and Microsystems, 78, pp.103219~ (2020)[DOI]
- S. Vijayakumar, "Area and power efficient hybrid PTCSL MUX design", European Journal of Scientific Research, 83(1), pp.39~52 (2012)
- M. Alioto, "Analysis and Comparison on Full Adder Block in Submicron Technology", IEEE Transactions on VLSI Systems, 10(6), pp.806~823 (2002)[DOI]