Computations for NTRU

Math 302 Cryptography, April 26, 2017
T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Define some useful functions for NTRU

t[d1,d2,n] returns a random polynomial in T(d1,d2) ⊂ R
polyInverse[poly, n, mod] returns the multiplicative inverse of poly in R_mod
centerLift[poly, mod] returns the center lift of poly from R_p to R

t[d1_,d2_,n_]:=
x^Range[0,n-1].RandomSample[Join[ConstantArray[1,d1],ConstantArray[-1,d2],ConstantArray[0,n-(d1+d2)]]];
polyInverse[poly_,n_, mod_]:=PolynomialMod[PolynomialExtendedGCD[poly, x^n - 1,x][[2,1]],mod];
centerLift[poly_,mod_]:= x^Range[0,Length[CoefficientList[poly,x]]-1].Mod[CoefficientList[poly,x],mod,-Floor[(mod-1)/2]];

NTRU example with N=13, p=7, q=97, d=2

n=13;p=7;q=97;d=2;
f=x^2 - x^3 + x^4 + x^10 - x^11
PolynomialGCD[f,x^n-1,Modulus-> p]
PolynomialGCD[f,x^n-1,Modulus-> q]

Notice f ∈ T(3,2) and f is invertible in R_p and R_q
Alice picks g ∈ T(2,2) and computes fq, fp, and public key h

g=x+x^2-x^5-x^7
fq=polyInverse[f,n,q]
fp=polyInverse[f,n,p]
h=PolynomialMod[fq*g,x^n-1,Modulus->q]

Bob encodes m ∈ R_p 
Notice m is a center lift to R since its coefficients are in the range {-3, -2, -1, 0, 1, 2, 3}
We’ll pick an ephemeral r  ∈ T(d,d)

m=2-2 x-(x^2)-3 (x^3)-2 (x^4)-3 (x^5)-2 (x^6)+2 (x^7)-3 (x^8)-2 (x^9)+3 (x^10)+(x^11)
(*r=t[d,d,n]*)
r=-1+(x^4)-(x^6)+(x^10)
e=PolynomialMod[p*r*h+m,x^n-1,Modulus->q]

Alice decrypts

fe = PolynomialMod[f*e,x^n-1,Modulus->q]
a=centerLift[fe,q]
centerLift[PolynomialMod[fp*a, x^n-1,Modulus->p],p]

Look at p g(x) r(x) + f(x) m(x)

Expand[ p*g*r+f*m]

CoefficientList[%,x]

Yay! All coefficents are in the range (-q/2, q/2]  !!!