Implementation of the Number Theoretic Transform

Abstract

I denne oppgaven skriver vi om implementering av Number Theoretic Transform, NTT. NTT er en algoritme for å multiplisere polynomer kjappere. I denne oppgaven ser vi på hvordan NTT fungerer, og hvorvidt denne faktisk multipliserer kjappere. Motivasjonen vår for å bruke dette er for kjappere lattice-basert kryptografi. I denne oppgaven ser vi på polynomer i R_q=Z_q[X]/〈X^N+1〉, og observerer at NTT multipliserer kjappere, spesielt når N blir større. Vi ser på hvordan NTT påvirker kjøretiden til NTRU, som bruker multiplikasjon av polynomer i nøkkelgenerering, kryptering og dekryptering. Vi ser også på hvordan NTT påvirker kjøretiden til et commitment scheme hvor multiplikasjon av en matrise og en vektor med polynomer blir brukt. Resultatet var at NTT fikk multiplisert mye raskere, både i NTRU og i commitment scheme.

This thesis is about implementation of the Number Theoretic Transform, NTT. NTT is an algorithm for multiplying polynomials faster, and through this paper we look at how it is able to do this, and to what extent it computes multiplication faster. Our motivation is to use this for faster lattice-based cryptography. In this paper we have implemented NTT for polynomials in R_q=Z_q[X]/〈X^N+1〉, and discovered that it does multiply faster, especially when N gets bigger. We have looked at how it would affect the running time of NTRU, which uses multiplication of polynomials in the key generation, encryption and decryption. We have also looked at how it affects the running time of a commitment scheme that uses multiplication of a matrix times a vector where all the inputs are polynomials in R_q. The result showed us that multiplication was much faster, both in NTRU and in the commitment scheme.