Efficient and Secure Implementation of NTRUEncrypt Using Signed Sliding Window Method
NTRUEncrypt is a public key cryptosystem based on hard problems over lattices. The dominant operation in NTRUEncrypt is convolution, i.e., multiplication over a quotient ring of polynomials. Based on the fact that a convolution has a highly regular structure, Lee et al. proposed the sliding window m...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9137237/ |
| _version_ | 1818608499933839360 |
|---|---|
| author | Taehyun Kim Mun-Kyu Lee |
| author_facet | Taehyun Kim Mun-Kyu Lee |
| author_sort | Taehyun Kim |
| collection | DOAJ |
| description | NTRUEncrypt is a public key cryptosystem based on hard problems over lattices. The dominant operation in NTRUEncrypt is convolution, i.e., multiplication over a quotient ring of polynomials. Based on the fact that a convolution has a highly regular structure, Lee et al. proposed the sliding window method for fast convolution of binary polynomials in 2013, which was then extended to ternary polynomials for ideal lattices by Akleylek, Alkim, and Tok in 2016. These sliding window methods reduce the cost of a convolution operation using look-up tables that store partial computation results related to repeated coefficient patterns. In this paper, we propose a signed sliding window method with side-channel resistance for NTRUEncrypt. The proposed method considers both positive and negative nonzero coefficients when constructing look-up tables. The new method not only accelerates convolution but also enables the application of power analysis countermeasures effectively. According to the experimental results, the constant-time implementation of the proposed method with timing and power analysis countermeasures accelerates the previously developed secure convolution method by up to 20%. |
| first_indexed | 2024-12-16T14:43:37Z |
| format | Article |
| id | doaj.art-6761d046e0174cbc816f50940c1c9475 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-16T14:43:37Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-6761d046e0174cbc816f50940c1c94752022-12-21T22:27:50ZengIEEEIEEE Access2169-35362020-01-01812659112660510.1109/ACCESS.2020.30081829137237Efficient and Secure Implementation of NTRUEncrypt Using Signed Sliding Window MethodTaehyun Kim0Mun-Kyu Lee1https://orcid.org/0000-0003-4423-7467Department of Computer Engineering, Inha University, Incheon, South KoreaDepartment of Computer Engineering, Inha University, Incheon, South KoreaNTRUEncrypt is a public key cryptosystem based on hard problems over lattices. The dominant operation in NTRUEncrypt is convolution, i.e., multiplication over a quotient ring of polynomials. Based on the fact that a convolution has a highly regular structure, Lee et al. proposed the sliding window method for fast convolution of binary polynomials in 2013, which was then extended to ternary polynomials for ideal lattices by Akleylek, Alkim, and Tok in 2016. These sliding window methods reduce the cost of a convolution operation using look-up tables that store partial computation results related to repeated coefficient patterns. In this paper, we propose a signed sliding window method with side-channel resistance for NTRUEncrypt. The proposed method considers both positive and negative nonzero coefficients when constructing look-up tables. The new method not only accelerates convolution but also enables the application of power analysis countermeasures effectively. According to the experimental results, the constant-time implementation of the proposed method with timing and power analysis countermeasures accelerates the previously developed secure convolution method by up to 20%.https://ieeexplore.ieee.org/document/9137237/Public key cryptographyside-channel attacksNTRUEncryptsliding window method |
| spellingShingle | Taehyun Kim Mun-Kyu Lee Efficient and Secure Implementation of NTRUEncrypt Using Signed Sliding Window Method IEEE Access Public key cryptography side-channel attacks NTRUEncrypt sliding window method |
| title | Efficient and Secure Implementation of NTRUEncrypt Using Signed Sliding Window Method |
| title_full | Efficient and Secure Implementation of NTRUEncrypt Using Signed Sliding Window Method |
| title_fullStr | Efficient and Secure Implementation of NTRUEncrypt Using Signed Sliding Window Method |
| title_full_unstemmed | Efficient and Secure Implementation of NTRUEncrypt Using Signed Sliding Window Method |
| title_short | Efficient and Secure Implementation of NTRUEncrypt Using Signed Sliding Window Method |
| title_sort | efficient and secure implementation of ntruencrypt using signed sliding window method |
| topic | Public key cryptography side-channel attacks NTRUEncrypt sliding window method |
| url | https://ieeexplore.ieee.org/document/9137237/ |
| work_keys_str_mv | AT taehyunkim efficientandsecureimplementationofntruencryptusingsignedslidingwindowmethod AT munkyulee efficientandsecureimplementationofntruencryptusingsignedslidingwindowmethod |