Worcester Polytechnic Institute Electronic Theses and Dissertations Collection

Title page for ETD etd-0430102-111906


Document Typethesis
Author NameO'Rourke, Colleen Marie
URNetd-0430102-111906
TitleEfficient NTRU Implementations
DegreeMS
DepartmentElectrical & Computer Engineering
Advisors
  • Berk Sunar, Advisor
  • Fred Looft, Committee Member
  • Donald R. Brown, Committee Member
  • John Orr, Department Head
  • Keywords
  • NTRU
  • cryptography
  • scalable multiplier
  • unified multiplier
  • Montgomery multiplier
  • Date of Presentation/Defense2002-04-23
    Availability unrestricted

    Abstract

    In this paper, new software and hardware designs for the NTRU Public Key Cryptosystem are proposed. The first design attempts to improve NTRU's polynomial multiplication through applying techniques from the Chinese Remainder Theorem (CRT) to the convolution algorithm. Although the application of CRT shows promise for the creation of the inverse polynomials in the setup procedure, it does not provide any benefits to the procedures that are critical to the performance of NTRU (public key creation, encryption, and decryption). This research has identified that this is due to the small coefficients of one of the operands, which can be a common misunderstanding.

    The second design focuses on improving the performance of the polynomial multiplications within NTRU's key creation, encryption, and decryption procedures through hardware. This design exploits the inherent parallelism within a polynomial multiplication to make scalability possible. The advantage scalability provides is that it allows the user to customize the design for low and high power applications. In addition, the support for arbitrary precision allows the user to meet the desired security level.

    The third design utilizes the Montgomery Multiplication algorithm to develop an unified architecture that can perform a modular multiplication for GF(p) and GF(2^k) and a polynomial multiplication for NTRU. The unified design only requires an additional 10 gates in order for the Montgomery Multiplier core to compute the polynomial multiplication for NTRU. However, this added support for NTRU presents some restrictions on the supported lengths of the moduli and on the chosen value for the residue for the GF(p) and GF(2^k) cases. Despite these restrictions, this unified architecture is now capable of supporting public key operations for the majority of Public-Key Cryptosystems.

    Files
  • corourke.pdf

  • Browse by Author | Browse by Department | Search all available ETDs

    [WPI] [Library] [Home] [Top]

    Questions? Email etd-questions@wpi.edu
    Maintained by webmaster@wpi.edu