Polynomial Multiplication in NTRU Prime
This paper proposes two different methods to perform NTT-based polynomial multiplication in polynomial rings that do not naturally support such a multiplication. We demonstrate these methods on the NTRU Prime key-encapsulation mechanism (KEM) proposed by Bernstein, Chuengsatiansup, Lange, and Vreden...
| Main Authors: | , , , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2020-12-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://ojs-dev.ub.rub.de/index.php/TCHES/article/view/8733 |
| _version_ | 1818945362443894784 |
|---|---|
| author | Erdem Alkim Dean Yun-Li Cheng Chi-Ming Marvin Chung Hülya Evkan Leo Wei-Lun Huang Vincent Hwang Ching-Lin Trista Li Ruben Niederhagen Cheng-Jhih Shih Julian Wälde Bo-Yin Yang |
| author_facet | Erdem Alkim Dean Yun-Li Cheng Chi-Ming Marvin Chung Hülya Evkan Leo Wei-Lun Huang Vincent Hwang Ching-Lin Trista Li Ruben Niederhagen Cheng-Jhih Shih Julian Wälde Bo-Yin Yang |
| author_sort | Erdem Alkim |
| collection | DOAJ |
| description | This paper proposes two different methods to perform NTT-based polynomial multiplication in polynomial rings that do not naturally support such a multiplication. We demonstrate these methods on the NTRU Prime key-encapsulation mechanism (KEM) proposed by Bernstein, Chuengsatiansup, Lange, and Vredendaal, which uses a polynomial ring that is, by design, not amenable to use with NTT. One of our approaches is using Good’s trick and focuses on speed and supporting more than one parameter set with a single implementation. The other approach is using a mixed radix NTT and focuses on the use of smaller multipliers and less memory. On a ARM Cortex-M4 microcontroller, we show that our three NTT-based implementations, one based on Good’s trick and two mixed radix NTTs, provide between 32% and 17% faster polynomial multiplication. For the parameter-set ntrulpr761, this results in between 16% and 9% faster total operations (sum of key generation, encapsulation, and decapsulation) and requires between 15% and 39% less memory than the current state-of-the-art NTRU Prime implementation on this platform, which is using Toom-Cook-based polynomial multiplication. |
| first_indexed | 2024-12-20T07:57:55Z |
| format | Article |
| id | doaj.art-e69f228a2a1542ee90132c5ae5a29923 |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-12-20T07:57:55Z |
| publishDate | 2020-12-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-e69f228a2a1542ee90132c5ae5a299232022-12-21T19:47:36ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252020-12-0120211Polynomial Multiplication in NTRU PrimeErdem Alkim0Dean Yun-Li Cheng1Chi-Ming Marvin Chung2Hülya Evkan3Leo Wei-Lun Huang4Vincent Hwang5Ching-Lin Trista Li6Ruben Niederhagen7Cheng-Jhih Shih8Julian Wälde9Bo-Yin Yang10Ondokuz Mayıs University, Samsun, Turkey; Fraunhofer SIT, Darmstadt, GermanyAcademia Sinica, Taipei, Taiwan; National Taiwan University, Taipei, TaiwanAcademia Sinica, Taipei, TaiwanFraunhofer SIT, Darmstadt, GermanyAcademia Sinica, Taipei, TaiwanAcademia Sinica, Taipei, Taiwan; National Taiwan University, Taipei, TaiwanAcademia Sinica, Taipei, Taiwan; National Taiwan University, Taipei, TaiwanUniversity of Southern Denmark, Odense, DenmarkAcademia Sinica, Taipei, TaiwanFraunhofer SIT, Darmstadt, GermanyAcademia Sinica, Taipei, TaiwanThis paper proposes two different methods to perform NTT-based polynomial multiplication in polynomial rings that do not naturally support such a multiplication. We demonstrate these methods on the NTRU Prime key-encapsulation mechanism (KEM) proposed by Bernstein, Chuengsatiansup, Lange, and Vredendaal, which uses a polynomial ring that is, by design, not amenable to use with NTT. One of our approaches is using Good’s trick and focuses on speed and supporting more than one parameter set with a single implementation. The other approach is using a mixed radix NTT and focuses on the use of smaller multipliers and less memory. On a ARM Cortex-M4 microcontroller, we show that our three NTT-based implementations, one based on Good’s trick and two mixed radix NTTs, provide between 32% and 17% faster polynomial multiplication. For the parameter-set ntrulpr761, this results in between 16% and 9% faster total operations (sum of key generation, encapsulation, and decapsulation) and requires between 15% and 39% less memory than the current state-of-the-art NTRU Prime implementation on this platform, which is using Toom-Cook-based polynomial multiplication.https://ojs-dev.ub.rub.de/index.php/TCHES/article/view/8733NTTpolynomial multiplicationCortex-M4NTRU PrimePQC |
| spellingShingle | Erdem Alkim Dean Yun-Li Cheng Chi-Ming Marvin Chung Hülya Evkan Leo Wei-Lun Huang Vincent Hwang Ching-Lin Trista Li Ruben Niederhagen Cheng-Jhih Shih Julian Wälde Bo-Yin Yang Polynomial Multiplication in NTRU Prime Transactions on Cryptographic Hardware and Embedded Systems NTT polynomial multiplication Cortex-M4 NTRU Prime PQC |
| title | Polynomial Multiplication in NTRU Prime |
| title_full | Polynomial Multiplication in NTRU Prime |
| title_fullStr | Polynomial Multiplication in NTRU Prime |
| title_full_unstemmed | Polynomial Multiplication in NTRU Prime |
| title_short | Polynomial Multiplication in NTRU Prime |
| title_sort | polynomial multiplication in ntru prime |
| topic | NTT polynomial multiplication Cortex-M4 NTRU Prime PQC |
| url | https://ojs-dev.ub.rub.de/index.php/TCHES/article/view/8733 |
| work_keys_str_mv | AT erdemalkim polynomialmultiplicationinntruprime AT deanyunlicheng polynomialmultiplicationinntruprime AT chimingmarvinchung polynomialmultiplicationinntruprime AT hulyaevkan polynomialmultiplicationinntruprime AT leoweilunhuang polynomialmultiplicationinntruprime AT vincenthwang polynomialmultiplicationinntruprime AT chinglintristali polynomialmultiplicationinntruprime AT rubenniederhagen polynomialmultiplicationinntruprime AT chengjhihshih polynomialmultiplicationinntruprime AT julianwalde polynomialmultiplicationinntruprime AT boyinyang polynomialmultiplicationinntruprime |