NTRU系統之實作演算法分析

Abstract

在可預期的未來內，量子電腦的技術將漸趨成熟。而秀爾演算法的發現將威脅基於整數分解與離散對數問題的傳統公鑰密碼系統，包含RSA、ElGamal加密以及ECIES。因此，後量子密碼系統必將取代傳統公鑰密碼系統。 在本文中，我們將先介紹作為美國國家標準暨技術研究院（NIST）第三輪後量子密碼競賽候選演算法之一的NTRU密碼系統。其後，將針對兩種參數集——NTRU-HPS以及NTRU-HRSS——討論其密鑰生成時的可逆性並給出解密正確性證明。 在這些數學理論的討論後，我們將把焦點轉往實作上。我們將設計並分析實作NTRU所需使用的演算法。實作的目標參數集設定為具有NIST安全等級3的ntruhps2948677。這部分將包含如何實作多項式反元素、多項式乘法以及如何對有號整數做模3的計算。

In the foreseeable future, quantum computers will be at a stage. Due to Shor’s algorithm, it threatens the safety of traditional public-key-cryptosystem which is based on the hardness of integer factorization and discrete logarithms, including RSA, ElGamal encryption, and ECIES. Therefore, post-quantum cryptography (PQC) must replace these traditional public-key-cryptosystems. In this paper, we will first introduce the NTRU system (N-th degree Truncated polynomial Ring Units), which is a finalist of NIST (National Institute of Standards and Technology}) 3rd round post-quantum cryptography competition. We will study the invertibility in the key generation and also give a correctness proof of two types of parameter sets: NTRU-HPS and NTRU-HRSS. After these mathematical discussions, we will move our attention to the implementation. We aim to design and analyze algorithms for the implementation of NTRU. The target parameter set is ntruhps2948677, which has NIST security level 3. This will include how to implement computations of polynomial inverse, polynomial arithmetic, and reduction modulo 3 of signed integers.