Improved Plantard Arithmetic for Lattice-based Cryptography
This paper presents an improved Plantard’s modular arithmetic (Plantard arithmetic) tailored for Lattice-Based Cryptography (LBC). Based on the improved Plantard arithmetic, we present faster implementations of two LBC schemes, Kyber and NTTRU, running on Cortex-M4. The intrinsic advantage of Plant...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2022-08-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/9833 |
| _version_ | 1797326092006064128 |
|---|---|
| author | Junhao Huang Jipeng Zhang Haosong Zhao Zhe Liu Ray C. C. Cheung Çetin Kaya Koç Donglong Chen |
| author_facet | Junhao Huang Jipeng Zhang Haosong Zhao Zhe Liu Ray C. C. Cheung Çetin Kaya Koç Donglong Chen |
| author_sort | Junhao Huang |
| collection | DOAJ |
| description |
This paper presents an improved Plantard’s modular arithmetic (Plantard arithmetic) tailored for Lattice-Based Cryptography (LBC). Based on the improved Plantard arithmetic, we present faster implementations of two LBC schemes, Kyber and NTTRU, running on Cortex-M4. The intrinsic advantage of Plantard arithmetic is that one multiplication can be saved from the modular multiplication of a constant. However, the original Plantard arithmetic is not very practical in LBC schemes because of the limitation on the unsigned input range. In this paper, we improve the Plantard arithmetic and customize it for the existing LBC schemes with theoretical proof. The improved Plantard arithmetic not only inherits its aforementioned advantage but also accepts signed inputs, produces signed output, and enlarges its input range compared with the original design. Moreover, compared with the state-of-the-art Montgomery arithmetic, the improved Plantard arithmetic has a larger input range and smaller output range, which allows better lazy reduction strategies during the NTT/INTT implementation in current LBC schemes. All these merits make it possible to replace the Montgomery arithmetic with the improved Plantard arithmetic in LBC schemes on some platforms. After applying this novel method to Kyber and NTTRU schemes using 16-bit NTT on Cortex-M4 devices, we show that the proposed design outperforms the known fastest implementation that uses Montgomery and Barrett arithmetic. Specifically, compared with the state-of-the-art Kyber implementation, applying the improved Plantard arithmetic in Kyber results in a speedup of 25.02% and 18.56% for NTT and INTT, respectively. Compared with the reference implementation of NTTRU, our NTT and INTT achieve speedup by 83.21% and 78.64%, respectively. As for the LBC KEM schemes, we set new speed records for Kyber and NTTRU running on Cortex-M4.
|
| first_indexed | 2024-03-08T06:18:35Z |
| format | Article |
| id | doaj.art-922ba4537ad647daa62fc29649dc7a4c |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-03-08T06:18:35Z |
| publishDate | 2022-08-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-922ba4537ad647daa62fc29649dc7a4c2024-02-04T16:20:45ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252022-08-0120224Improved Plantard Arithmetic for Lattice-based CryptographyJunhao Huang0Jipeng Zhang1Haosong Zhao2Zhe Liu3Ray C. C. Cheung4Çetin Kaya Koç5Donglong Chen6Guangdong Provincial Key Laboratory of Interdisciplinary Research and Application for Data Science, BNU-HKBU United International College, Zhuhai, ChinaNanjing University of Aeronautics and Astronautics, Nanjing, ChinaGuangdong Provincial Key Laboratory of Interdisciplinary Research and Application for Data Science, BNU-HKBU United International College, Zhuhai, ChinaNanjing University of Aeronautics and Astronautics, Nanjing, China; Zhejiang Lab, Hangzhou, ChinaCity University of Hong Kong, Hong Kong, ChinaUniversity of California Santa Barbara, Santa Barbara, USA; Nanjing University of Aeronautics and Astronautics, Nanjing, ChinaGuangdong Provincial Key Laboratory of Interdisciplinary Research and Application for Data Science, BNU-HKBU United International College, Zhuhai, China This paper presents an improved Plantard’s modular arithmetic (Plantard arithmetic) tailored for Lattice-Based Cryptography (LBC). Based on the improved Plantard arithmetic, we present faster implementations of two LBC schemes, Kyber and NTTRU, running on Cortex-M4. The intrinsic advantage of Plantard arithmetic is that one multiplication can be saved from the modular multiplication of a constant. However, the original Plantard arithmetic is not very practical in LBC schemes because of the limitation on the unsigned input range. In this paper, we improve the Plantard arithmetic and customize it for the existing LBC schemes with theoretical proof. The improved Plantard arithmetic not only inherits its aforementioned advantage but also accepts signed inputs, produces signed output, and enlarges its input range compared with the original design. Moreover, compared with the state-of-the-art Montgomery arithmetic, the improved Plantard arithmetic has a larger input range and smaller output range, which allows better lazy reduction strategies during the NTT/INTT implementation in current LBC schemes. All these merits make it possible to replace the Montgomery arithmetic with the improved Plantard arithmetic in LBC schemes on some platforms. After applying this novel method to Kyber and NTTRU schemes using 16-bit NTT on Cortex-M4 devices, we show that the proposed design outperforms the known fastest implementation that uses Montgomery and Barrett arithmetic. Specifically, compared with the state-of-the-art Kyber implementation, applying the improved Plantard arithmetic in Kyber results in a speedup of 25.02% and 18.56% for NTT and INTT, respectively. Compared with the reference implementation of NTTRU, our NTT and INTT achieve speedup by 83.21% and 78.64%, respectively. As for the LBC KEM schemes, we set new speed records for Kyber and NTTRU running on Cortex-M4. https://tches.iacr.org/index.php/TCHES/article/view/9833KyberNTTRUNTTCortex-M4modular arithmeticlattice-based cryptography |
| spellingShingle | Junhao Huang Jipeng Zhang Haosong Zhao Zhe Liu Ray C. C. Cheung Çetin Kaya Koç Donglong Chen Improved Plantard Arithmetic for Lattice-based Cryptography Transactions on Cryptographic Hardware and Embedded Systems Kyber NTTRU NTT Cortex-M4 modular arithmetic lattice-based cryptography |
| title | Improved Plantard Arithmetic for Lattice-based Cryptography |
| title_full | Improved Plantard Arithmetic for Lattice-based Cryptography |
| title_fullStr | Improved Plantard Arithmetic for Lattice-based Cryptography |
| title_full_unstemmed | Improved Plantard Arithmetic for Lattice-based Cryptography |
| title_short | Improved Plantard Arithmetic for Lattice-based Cryptography |
| title_sort | improved plantard arithmetic for lattice based cryptography |
| topic | Kyber NTTRU NTT Cortex-M4 modular arithmetic lattice-based cryptography |
| url | https://tches.iacr.org/index.php/TCHES/article/view/9833 |
| work_keys_str_mv | AT junhaohuang improvedplantardarithmeticforlatticebasedcryptography AT jipengzhang improvedplantardarithmeticforlatticebasedcryptography AT haosongzhao improvedplantardarithmeticforlatticebasedcryptography AT zheliu improvedplantardarithmeticforlatticebasedcryptography AT raycccheung improvedplantardarithmeticforlatticebasedcryptography AT cetinkayakoc improvedplantardarithmeticforlatticebasedcryptography AT donglongchen improvedplantardarithmeticforlatticebasedcryptography |