在FPGA上實作NTRU Prime密碼系統

An FPGA implementation of the NTRU Prime Cryptosystem

劉軒竹(Hsuan-Chu Liu)

指導教授 ： 鄭振牟

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

https://doi.org/10.6342/NTU202003012

摘要

現在，量子計算機即將成為現實，傳統的密碼系統將逐漸變得不安全。因此，後量子密碼系統日漸重要。並且，如何有效地實現後量子密碼系統同樣重要。有效率的後量子密碼系統可以在較短的時間內完成相同安全級別的加密，換言之，它也可以在相同的時間內獲得較高的安全級別。本篇論文將NTRU Prime密碼系統以FPGA實現。此外，本篇論文也在FPGA上有效率的實作多項式乘法（金鑰封裝和解封裝中最耗時的運算）

關鍵字

美國國家標準暨技術研究院 ； FPGA實作 ； 多項式乘法 ； 後量子密碼學 ； NTRU ； NTRU Prime

並列摘要

Now that quantum computers are about to become a reality, traditional cryptosystems will gradually become insecure. Therefore, it is important to have a post-quantum cryptosystem. And, how to efficiently implement the post-quantum cryptosystem is equally important. The efficient post-quantum cryptosystem can complete the encryption of the same security level in a faster time, in other words, it can also get a higher security level in the same amount of time. In this paper, the NTRU Prime cryptosystem is implemented on the FPGA. Furthermore, low-complexity polynomial multiplication, the most time-consuming operation in the key encapsulation/decapsulation algorithm, are proposed to implement efficiently on FPGA.

並列關鍵字

NIST ； FPGA implementation ； polynomial multiplication algorithm ； post-quantum cryptography ； NTRU ； NTRU Prime

參考文獻

[1] P. W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring," Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 1994, pp. 124-134, doi: 10.1109/SFCS.1994.365700.

[2] NIST, “Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms,” 81 FR 92787, pp. 92787-92788, Dec. 2016.

[3] Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja Lange, Christine van Vredendaal. “NTRU Prime: reducing attack surface at low cost,” Aug. 2017. https://ntruprime.cr.yp.to/papers.html#ntruprime-paper

[4] N. Zhang, B. Yang, C. Chen, S. Yin, S. Wei, and L. Liu, “Highly Efficient Architecture of NewHope-NIST on FPGA using Low-Complexity NTT/INTT”, TCHES, vol. 2020, no. 2, pp. 49-72, Mar. 2020.

[5] Daniel J. Bernstein. “Divergence bounds for random fixed-weight vectors obtained by sorting,” Apr. 2018. https://ntruprime.cr.yp.to/papers.html#divergence