使用Armv7-M、Armv7E-M、Armv8-A 實作數論變換之案例研究

Case Studies on Implementing Number-Theoretic Transforms with Armv7-M, Armv7E-M, and Armv8-A

黃柏文(Vincent Bert Hwang)

指導教授 ： 李彥寰

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2022年)

https://doi.org/10.6342/NTU202200738

摘要

這篇論文收集在碩士研究中所發表或是投稿的相關論文。 我們專注於數論變換在 Cortex-M3、Cortex-M4、Cortex-A72 上的組合語言實作。 在 Cortex-M3 上，我們用 Armv7-M 來實作;在 Cortex-M4 上，我們用 Armv7E-M 來實作;在 Cortex- A72 上，我們用 Armv8.0-A 來實作。為了呈現優化的效果，我們將數論變換的實作應用於 Dilithium、Kyber、NTRU、NTRU Prime 和 Saber 這些晶格密碼系統中。
我們在 Cortex-M3 上實作了 Saber;在 Cortex-M4 上實作了 NTRU、NTRU Prime 和 Saber;在 Cortex-A72 上實作了 Dilithium、Kyber 和 Saber。 我們針對速度、記憶體和程式碼大小來優化 Saber 在 Cortex-M3 和 Cortex-M4 上的實作、 針對速度和程式碼大小來優化 NTRU 和 NTRU Prime 在 Cortex-M4 上的實作、 針對速度來優化 Dilithium、Kyber 和 Saber 在 Cortex-A72 上的實作。

關鍵字

晶格密碼系統 ； 數論變換 ； 快速傅立葉變換 ； Arm 組合語言 ； Cortex-M3 ； Cortex-M4 ； Cortex-A72

並列摘要

This thesis collects selected works published or submitted during the study of the master’s program. We focus on the assembly realizations of number–theoretic transforms (NTTs) on Cortex-M3, Cortex-M4, and Cortex-A72. In particular, we implement the NTTs in Armv7-M for Cortex-M3, Armv7E-M for Cortex-M4, and Armv8.0- A for Cortex-A72. To demonstrate the optimizations, we select the lattice-based cryptosystems Dilithium, Kyber, NTRU, NTRU Prime, and Saber for evaluation.
We apply our optimizations to Saber on Cortex-M3; NTRU, NTRU Prime, and Saber on Cortex-M4; and Dilithium, Kyber, and Saber on Cortex-A72. We optimize Saber on Cortex-M3 and Cortex-M4 for speed, memory usage, and code size; NTRU and NTRU Prime on Cortex-M4 for speed and code size; and Dilithium, Kyber, and Saber on Cortex-A72 for speed.

並列關鍵字

lattice-based cryptosystem ； number–theoretic transform ； fast Fourier transform ； Arm assembly ； Cortex-M3 ； Cortex-M4 ； Cortex-A72

參考文獻

[Für09] Martin Fürer. Faster Integer Multiplication. SIAM Journal on Computing, 39(3):979–1005, 2009. https://doi.org/10.1137/070711761.

[GS66] W. M. Gentleman and G. Sande. Fast Fourier Transforms: For Fun and Profit. In Proceedings of the November 7-10, 1966, Fall Joint Computer Conference, AFIPS’66 (Fall), pages 563–578. Association for Computing Machinery, 1966. https://doi.org/10.1145/1464291.1464352.

[ABB+20] Nicolas Aragon, Paulo Barreto, Slim Bettaieb, Loic Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Phillipe Gaborit, Shay Gueron, Tim Guneysu, Carlos Aguilar Melchor, Rafael Misoczki, Edoardo Persichetti, Nicolas Sendrier, Jean-Pierre Tillich, Gilles Zemor, Valentin Vasseur, Santosh Ghosh, and Jan Richter-Brokmann. BIKE. Submission to the NIST Post-Quantum Cryptography Standardization Project [NIS], 2020. https://bikesuite.org/.

[ABC+20] Martin R. Albrecht, Daniel J. Bernstein, Tung Chou, Carlos Cid, Jan Gilcher, Tanja Lange, Varun Maram, Ingo von Maurich, Rafael Misoczki, Ruben Niederhagen, Kenneth G. Paterson, Edoardo Persichetti, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, Cen Jung Tjhai, Martin Tomlinson, and Wen Wang. Classic McEliece. Submission to the NIST Post-Quantum Cryptography Standardization Project [NIS], 2020. https://classic.mceliece.org/.

[ABCG20] Erdem Alkim, Yusuf Alper Bilgin, Murat Cenk, and François Gérard. Cortex-M4 optimizations for {R, M} LWE schemes. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020(3):336–357, 2020. https://tches.iacr.org/index.php/TCHES/article/view/8593.