IEICE TRANSACTIONS on Fundamentals
Efficient Implementation of NTRU Cryptosystem Using Sliding Window Methods
Summary :
NTRU is a public key cryptosystem based on hard problems over lattices. In this paper, we present efficient methods for convolution product computation which is a dominant operation of NTRU. The new methods are based on the observation that repeating patterns in coefficients of an NTRU polynomial can be used for the construction of look-up tables, which is a similar approach to the sliding window methods for exponentiation. We provide efficient convolution algorithms to implement this idea, and we make a comprehensive analysis of the complexity of the new algorithms. We also give software implementations over a Pentium IV CPU, a MICAz mote, and a CUDA-based GPGPU platform. According to our analyses and experimental results, the new algorithms speed up the NTRU encryption and decryption operations by up to 41%.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E96-A No.1 pp.206-214
- Publication Date
- 2013/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E96.A.206
- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)
- Category
- Implementation
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Mun-Kyu LEE, Jung Woo KIM, Jeong Eun SONG, Kunsoo PARK, "Efficient Implementation of NTRU Cryptosystem Using Sliding Window Methods" in IEICE TRANSACTIONS on Fundamentals,
vol. E96-A, no. 1, pp. 206-214, January 2013, doi: 10.1587/transfun.E96.A.206.
Abstract: NTRU is a public key cryptosystem based on hard problems over lattices. In this paper, we present efficient methods for convolution product computation which is a dominant operation of NTRU. The new methods are based on the observation that repeating patterns in coefficients of an NTRU polynomial can be used for the construction of look-up tables, which is a similar approach to the sliding window methods for exponentiation. We provide efficient convolution algorithms to implement this idea, and we make a comprehensive analysis of the complexity of the new algorithms. We also give software implementations over a Pentium IV CPU, a MICAz mote, and a CUDA-based GPGPU platform. According to our analyses and experimental results, the new algorithms speed up the NTRU encryption and decryption operations by up to 41%.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E96.A.206/_p
Copy
@ARTICLE{e96-a_1_206,
author={Mun-Kyu LEE, Jung Woo KIM, Jeong Eun SONG, Kunsoo PARK, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Implementation of NTRU Cryptosystem Using Sliding Window Methods},
year={2013},
volume={E96-A},
number={1},
pages={206-214},
abstract={NTRU is a public key cryptosystem based on hard problems over lattices. In this paper, we present efficient methods for convolution product computation which is a dominant operation of NTRU. The new methods are based on the observation that repeating patterns in coefficients of an NTRU polynomial can be used for the construction of look-up tables, which is a similar approach to the sliding window methods for exponentiation. We provide efficient convolution algorithms to implement this idea, and we make a comprehensive analysis of the complexity of the new algorithms. We also give software implementations over a Pentium IV CPU, a MICAz mote, and a CUDA-based GPGPU platform. According to our analyses and experimental results, the new algorithms speed up the NTRU encryption and decryption operations by up to 41%.},
keywords={},
doi={10.1587/transfun.E96.A.206},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Efficient Implementation of NTRU Cryptosystem Using Sliding Window Methods
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 206
EP - 214
AU - Mun-Kyu LEE
AU - Jung Woo KIM
AU - Jeong Eun SONG
AU - Kunsoo PARK
PY - 2013
DO - 10.1587/transfun.E96.A.206
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E96-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2013
AB - NTRU is a public key cryptosystem based on hard problems over lattices. In this paper, we present efficient methods for convolution product computation which is a dominant operation of NTRU. The new methods are based on the observation that repeating patterns in coefficients of an NTRU polynomial can be used for the construction of look-up tables, which is a similar approach to the sliding window methods for exponentiation. We provide efficient convolution algorithms to implement this idea, and we make a comprehensive analysis of the complexity of the new algorithms. We also give software implementations over a Pentium IV CPU, a MICAz mote, and a CUDA-based GPGPU platform. According to our analyses and experimental results, the new algorithms speed up the NTRU encryption and decryption operations by up to 41%.
ER -
English
