NTRU 密碼系統之同態運算及其分析

Homomorphism and Cryptanalysis of NTRU

江政融(Jeng-Rung Jiang)

指導教授 ： 陳君明

國立臺灣大學/理學院/數學研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.01900

摘要

首先，本論文將介紹NTRU公鑰系統的基本運作，隨即以密碼分析的角度帶出lattice結構的一些相關知識，並且描述和證明LLL演算法，以說明現今攻擊NTRU系統的主要方法。最後將NTRU系統做更進一步的推廣，於參數上使用一些限制條件，賦予加密函數同態的特性。

關鍵字

多項式環 ； NTRU ； lattice ； LLL演算法 ； apprSVP ； homomorphic encryption

並列摘要

This thesis introduces how the NTRU cryptosystem works and an elementary cryptanalysis about lattice. After ntroducing NTRU, we briefly describe the lattice structure and LLL, the lattice reduction algorithm from a cryptanalytic point of view, and then express the relations between NTRU and the lattice structure. Finally, we extend the system by adjusting the key space, parameters and message space with
appropriate restrictions to endow NTRU encryption with various properties of ring homomorphism.

並列關鍵字

Polynomial rings ； NTRU ； lattice ； LLL algorithm ； apprSVP ； homomorphic encryption

參考文獻

[1] W. Diffie and M. Hellman, New directions in cryptography, IEEE Transactions

on Information Theory IT-22, 644-654, 1976.

signatures and public-key cryptosystems, Commun. ACM 21, 120-126, 1978.

[3] J. Hoffstein, J. Pipher and J. H. Silverman, NTRU, A Ring-Based Public Key

Cryptosystem, Algorithmic Number Theory (ANTS III), Portland, OR, June