Efficient Architecture and Implementation for NTRU Based Systems

NTRU (Nth degree Truncated polynomial Ring Units) is probably the only post quantum public key cryptosystem suitable for practical implementation. Recently, several NTRU based systems have also been shown having property of homomorphic encryption with important application in cloud computing security. In this thesis, several efficient algorithms and architectures for NTRUEcrypt system and for NTRU based homomorphic encryption system are proposed. For NTRUEncrypt system, a new LFSR (linear feedback shift register) based architecture is firstly presented. A novel design of the modular arithmetic unit is proposed to reduce the critical path delay. The FPGA implementation results have shown that the proposed design outperforms all the existing works in terms of area-delay product. Secondly, a new architecture using extended LFSR is proposed for NTRUEncrypt system. It takes advantage of small polynomials with many zero coefficients, and thus significantly reduces the latency of the computation with modest increase of the complexity. Thirdly, a systolic array architecture is proposed for NTRUEncrypt. There is only one type of PE (process element) in the array and the PE was designed with optimized arithmetic. The systolic array yields all the output in N clock cycles. Two new architectures are proposed for computation of NTRU based fully homomorphic encryption system. One architecture uses LFSR with a novel design of the modular multiplication unit, and the other proposed architecture is systolic array based which uses two types of PEs