Efficient Multiplication Architectures for Truncated Polynomial Ring

In this thesis, four efficient multiplication architectures, named as Multipliers I, II, III, and IV, respectively, for truncated polynomial ring are proposed. Their FPGA implementation results are presented. All of the four proposed multipliers can be used for implementation of NTRUEncrypt public key system. All new multiplication architectures are based on certain extensions to Linear Feedback Shift Register (LFSR). Multiplier I uses x^2-net structure for LFSR, which scans two consecutive coefficients in the control input polynomial r(x) during one clock cycle. In Multiplier II, three consecutive zeros in the control input polynomial r(x) can be processed during one clock cycle. Multiplier III takes advantage of consecutive zeros in the control input polynomial r(x). Multiplier IV is resistant to certain side-channel attacks through controlling the operations for each clock cycle. An FPGA complexity comparison among the proposed multipliers and the existing similar works is made, including number of adaptive logic modules (ALMs), number of registers, number of cycles, maximum operating frequency (FMax) and latency. The FPGA comparison results are given as follows. Multiplier I has smaller latency than any existing works when the first set of parameters from every security level is used (ees401ep1, ees449ep1, ees677ep1, ees1087ep2). Multiplier II is the second best in speed compared to existing works, but has better area-latency product compared to the fastest existing work for the first set of parameters at security level 112-bit, 128-bit and 192-bit. As an enhanced version of Multiplier II, Multiplier III is faster than any existing works in comparison for all IEEE recommended parameter sets. Multiplier IV, designed to be resistant to side channel attacks, also has high speed property that it outperforms all the existing works in terms of latency for all three parameter sets to which it is applicable