An efficient and light weight polynomial multiplication for ideal lattice-based cryptography
- PDF / 1,118,480 Bytes
- 32 Pages / 439.642 x 666.49 pts Page_size
- 109 Downloads / 179 Views
An efficient and light weight polynomial multiplication for ideal lattice-based cryptography Vijay Kumar Yadav1
· Shekhar Verma1 · S. Venkatesan1
Received: 27 February 2020 / Revised: 13 August 2020 / Accepted: 25 August 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Ring-Learning With Errors (Ring-LWE) based cryptographic schemes such as signature, key exchange, and encryption require polynomial multiplication. This multiplication operation is the most time consuming and computationally rigorous process in Ring-LWE. In order to improve the efficiency of the Ring-LWE based schemes, most of the existing schemes use Fast Fourier Transform (FFT) based polynomial multiplication algorithm. It is known that Discrete Sine Transformation (DST) and Discrete Cosine Transformation (DCT) are faster than the FFT. The combination of DCT and DST is Discrete Trigonometric Transform (DTT). When we generalize DTT in terms of FFT form, it becomes Generalized Discrete Fourier Transform (GDFT). In this paper, we propose two new polynomial multiplication techniques using DTT and GDFT. When we apply circular convolution and skew-circular convolution on DTT or GDFT for the polynomial multiplication, it gives us wrong results. To overcome this issue, we use symmetric convolution operation on DTT and GDFT. We implemented and compared the proposed polynomial multiplication schemes with the current state-of-the-art schemes in terms of computation and communication costs. The implementation results show that the proposed schemes DTT and GDFT perform more efficiently as compared to current state-of-the-art schemes in terms of computation and communication costs. Keywords Fast fourier transform · Discrete cosine transformation · Number theoretic transform · Lattice-based cryptography · Ring-learning with errors
Vijay Kumar Yadav
[email protected] Shekhar Verma [email protected] S. Venkatesan [email protected] 1
Indian Institute of Information Technology Allahabad Devghat, Jhalwa, Allahabad 211015, UP, India
Multimedia Tools and Applications
1 Introduction The family of eight DCT consists of four even length, and four odd length versions. Similarly, DST is also a family of eight, in which four are even length, and the other four are odd length versions. The combination of both DCT and DST is called DTT [7]. DTT plays an important role in many images transform coding applications [18, 27, 32], but it is not practically applicable in image filtering applications as well as for polynomial multiplication, whereas FFT has suitable for it. Till 1993 many researchers were working on DTT to find is there any convolution exist for DTT, which is capable of finding the polynomial multiplication on DTT. In 1994, Martucci [28] had proposed Symmetric Convolution technique for the DTT family. This symmetric convolution multiplication property behaves similar to the circular convolution of Discrete Fourier transform (DFT). The DFT is also a polynomial multiplication technique. An efficient version of DFT is c
Data Loading...
