Ntru Cryptography: A

Tutorial

Wei Ren, Ph.D

Department of Electrical and Computer Engineering
University of Nevada, Las Vegas

Email: [email protected]
May 23, 2006

http://www.cs.unlv.edu/~renw/ntru-tutorial-slides.pdf
5/23/2006 [email protected] 1
Agenda
„ Algebra Tutorial
… Modular Arithmetic
… Truncated Polynomial Rings
… Inverse in Truncated Polynomial Rings
„ The NTRU Public Key Cryptosystem
… NTRU PKCS Parameters
… Key Generation
… Encryption
… Decryption
… Why It Works
„ Advanced Topics (Optimizations)
„ Implementation Details

5/23/2006 [email protected] 2
Presentation Outline
„ Algebra Tutorial
… Modular Arithmetic
… Truncated Polynomial Rings
… Inverse in Truncated Polynomial Rings
„ The NTRU Public Key Cryptosystem
… NTRU PKCS Parameters
… Key Generation
… Encryption
… Decryption
… Why It Works
„ Advanced Topics (Optimizations)
„ Implementation Details

5/23/2006 [email protected] 3
Modular Arithmetic
„ Division with modulo and keep the remainder
„ e.g. 147 (modulo 17) =?
147=8*17+11 that is 147=11 (modulo 17)
„ In general, the congruence a=b (modulo m) means that a and b leave
the same remainder when they are divided by m.
„ (a modulo m) + (b modulo m)=(a+b modulo m)
„ (a modulo m) * (b modulo m)=(a*b modulo m)
„ If a*b=1 (modulo m), b is an inverse for a (modulo m)
e.g. inverse of 10 (modulo 23) is 7, why?
7*10=1(modulo 23)
„ Euclidean Algorithm can be used to check if a and m have common
factors and compute the inverse of a (modulo m) if they do not have
common factors

5/23/2006 [email protected] 4
Truncated Polynomial Rings
„ Degree N-1 Ring
E.g. a =a0+a1X+a2X2+a3X3+…+aN-2XN-2+aN-1XN-1
„ a+b=(a0+b0)+(a1+b1)X+…(aN-1+bN-1)XN-1
„ XN=1 (mod XN -1)
„ a*b=c0+c1X+c2X2+…+cN-2XN-2+cN-1XN-1
ck=a0bk+a1bk-1+…+akb0+ak+1bN-1+ak+2bN-2+…aN-1bk+1
k N −1
ck = ∑a b
i =0
i k −i+ ∑a b
i = k +1
i N +k −i = ∑a b i j
i + j ≡ k (mod N )

„ a*(b+c)=a*b+a*c
„ Call it Ring of Truncated Polynomials. In terms of modern
abstract algebra, R is isomorphic to the quotient ring Z[X]/(XN-1)

5/23/2006 [email protected] 5
Truncated Polynomial R with
the modular arithmetic
„ Polynomial a modulo an integer q
a (modulo q)
Means to reduce the coefficients of a modulo q

a=b (modulo q)
Means every coefficients of the difference a-b is a multiple of q

„ a =a0+a1X+a2X2+a3X3+…+aN-2XN-2+aN-1XN-1
is conveniently written as the list of N numbers
a=(a0, a1, a2, …..,,aN-2, aN-1)

e.g. when N=7, polynomial a = 3+2X2-3X4+X6 is stored as the list

(3,0,2,0,-3,0,1)

5/23/2006 [email protected] 6
Inverses in Truncated
Polynomial R
„ Inverse modulo q of a polynomial a modulo is a polynomial A with
the property that
a*A=1 (modulo q)
„ Not every polynomial has an inverse modulo q, but it is easy to
determine if a has an inverse and to compute the inverse if it exists

e.g. N=7, q=11, a = 3+2X2-3X4+X6, the inverse of a modulo 11 is

A=-2+4X+2X2+4X3-4X4+2X5-2X6
Since
(3+2X2-3X4+X6)*(-2+4X+2X2+4X3-4X4+2X5-2X6)
= -10+22X+22X3-22X6
=1 (modulo 11)

5/23/2006 [email protected] 7
Presentation Outline
„ Algebra Tutorial
… Modular Arithmetic
… Truncated Polynomial Rings
… Inverse in Truncated Polynomial Rings
„ The NTRU Public Key Cryptosystem
… NTRU PKCS Parameters
… Key Generation
… Encryption
… Decryption
… Why It Works
„ Advanced Topics (Optimizations)
„ Implementation Details

5/23/2006 [email protected] 8
NTRU PKCS Parameters
„ Ring R that consists of all truncated polynomials of
degree N-1 having integer coefficients:

a =a0+a1X+a2X2+a3X3+…+aN-2XN-2+aN-1XN-1

„ N: the polynomials in the truncated polynomial ring have

degree N-1
„ q: large modular, the coefficients of the truncated
polynomials will be reduced mod q
„ p: small modular, as the final step in decryption, the
coefficients of the message are reduced mod p

5/23/2006 [email protected] 9
NTRU PKCS Parameters
Security N q p
Level
Moderate 167 128 3
Standard 251 128 3
High 347 128 3
Highest 503 256 3
From www.ntru.com, ntru tutorial
Ntru167ÙECC112ÙRSA512
Ntru263ÙECC168ÙRSA1024 In this tutorial, N=11, q=32, p=3
Ntru503ÙECC196ÙRSA2048

5/23/2006 [email protected] 10
Key Generation
„ Randomly Choose two “small” polynomials f and g and
keep them private
„ Randomly means coefficients is randomly distributed in p
or q, small means the coefficients are much smaller than
p or q
„ Compute the inverse of f modulo q and the inverse of f
modulo p
f*fq=1 (modulo q) and f*fp=1 (modulo p)

„ Public Key is: h=pfq*g (modulo q)

5/23/2006 [email protected] 11
Key Generation Example
„ N=11, q=32, p=3
Some method to generate f and g:
„ df: The polynomial f has df coefficients equal to +1 and
df -1 coefficients equal to -1, and all the rest are 0
„ dg : The polynomial g has dg coefficients equal to +1
and dg coefficients equal to -1, and all the rest are 0
„ The reason: f and g are “small” polynomials, f has to be
inverse while g doesn’t
„ df=4 dg=3
f=-1+X+X2-X4+X6+X9-X10
g=-1+X2+X3+X5-X8-X10

5/23/2006 [email protected] 12
Key Generation Example (cont.)
„ fp=1+2X+2X3+2X4+X5+2X7+X8+2X9

„ fq=5+9X+6X2+16X3+4X4+15X6+22X7+20X8+18X9+30X10

How to generate fp and fq? Discuss it later.

„ H=pfq*g (modulo q) q=32, p=3

„ g=-1+X2+X3+X5-X8-X10 (in previous slide)

H=8+25X+22X2+20X3+12X4+24X5+15X6+19X7+12X8+19
X9+16X10

5/23/2006 [email protected] 13
Is fp really inverse of f , fp*f=1 (mod
p) p=3 ? Verification
„ XN=1 (mod XN -1)
„ a*b=c0+c1X+c2X2+…+cN-2XN-2+cN-1XN-1 k N−1
ck=a0bk+a1bk-1+…+akb0+ak+1bN- ck = ∑a b i k −i + ∑a b i N + k −i = ∑a b i j
1+ak+2bN-2+…aN-1bk+1 i=0 i=k+1 i+ j≡k(modN)

„ fp=1+2X+2X3+2X4+X5+2X7+X8+2X9
„ f = -1+X+X2-X4+X6+X9-X10

e. g.
(1, 2, 0, 2, 2, 1, 0, 2, 1, 2, 0)
c0=1*(-1)+2*(-1)+0*1+2*0+2*0+1*1+
0*0+2*(-1)+1*0+2*1+0*1=
(-1)+(-2)+1+(-2)+2= -2 (-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1)

Since p=3
(-2) =1 (mod 3)

5/23/2006 [email protected] 14
How to compute H=pfq*g (mod q)
q=32, p=3
„ Low Hamming Weight Polynomials
Reference: J.Hoffstein, J.Silverman, “Random Small Hamming
Weight Products With Applications to Cryptography,”
http://www.ntru.com/cryptolab/articles.htm, Last Access, May
19,2006
e.g. (4,5,7)*(5,3,2)
=4*(5,3,2)+5*(2,5,3)+7*(3,2,5)
=(20,12,8)+(10,25,15)+(21,14,35)
=(20+10+21, 12+25+14, 8+15+35)
= (51,51,56)

5/23/2006 [email protected] 15
How to compute H=pfq*g (mod q)
q=32, p=3 (cont.)
„ Using Low Hamming Weight Polynomials
fq=5+9X+6X2+16X3+4X4+15X5+16X6+22X7+20X8+18X9+30X10
g=-1+X2+X3+X5-X8-X10
H=pfq*g (mod q) p=3, q=32

„ (-1,0,1,1,0,1,0,0,-1,0,-1)*(5,9,6,16,4,15,16,22,20,18,30)=
„ (-5,-9,-6,-16,-4,-15,-16,-22,-20,-18,-30)+
„ (18,30,5,9,6,16,4,15,16,22,20)+
„ (20,18,30,5,9,6,16,4,15,16, 22)+ H=8+25X+22X2+20X3+12X4+24X5+15
X6+19X7+12X8+19X9+16X10
„ (16,22,20,18,30,5,9,6,16,4,15)+
„ (-16,-4,-15,-16,-22,-20,-18,-30,-5,-9)+
„ (-9,-6-16,-4,0,-15,-16,-22,-20,-18,-30,-5)=(24,51….)
-5+18+20+16-16-9=24 24*3=72 72=8 (mod 32)
5/23/2006 [email protected] 16
Encryption
„ m is plaintext in the form of a polynomial whose
coefficients are “small” mod q
„ Randomly choose another “small” polynomial r
„ r is “blinding value” which is used to obscure the
message (similar to the way that ElGamal
algorithm use a one-time random value when
encrypting)
„ e = r*h +m (modulo q),
e is encrypted message, m is plaintext, h is
public key

5/23/2006 [email protected] 17
Encryption Example
„ r has dr coefficients equal to 1, dr-1 coefficients equal to -
1, and all others are 0
„ dr=3, r=-1+X2+X3+X4-X5-X7
„ m=-1+X3-X4-X8+X9+X10
„ h=8+25X+22X2+20X3+12X4+24X5+15X6+19X7+12X8+19
X9+16X10
„ e=r*h+m (mod q)
=(-1, 0,1,1,1,-1,0,-1,0,0,0)*(8,25,22,20,12,24,15,19,12,19,16)+
(-1,0,0,1,-1,0,0,0,-1,1,1)
=14+11X+26X2+24X3+14X4+16X5+30X6+7X7+25X8+6X9+19X10

5/23/2006 [email protected] 18
Decryption
„ a = f*e (mod q), MUST choose coefficients of a
to lie between -q/2 and q/2, e.g. for q=32,
coefficients must lie in [-15, 16]
„ b = a (mod p), MUST choose coefficients of b
between -p/2 and p/2, for p=3, the range is [-1,1]
„ c = fp*b (mod p), MUST choose coefficients of c
between -p/2 and p/2, for p=3, the range is [-1,1]

5/23/2006 [email protected] 19
Decryption Example: a=f*e (mod q)
„ e=14+11X+26X2+24X3+14X4+16X5+30X6+7X7+25X8+6
X9+19X10
„ f = -1+X+X2-X4+X6+X9-X10

„ (-1,1,1,0,-1,0,1,0,0,1,-1)*
(14,11,26,24,14,16,30,7,25,6,19)
„ mod 32, change coefficients to [-15,16]
„ a=3-7X-10X2-11X3+10X4+7X5+6X6+7X7+5X8-3X9-7X10
denoted by (3,-7,-10,-11,10,7,6,7,5,-3,-7)

5/23/2006 [email protected] 20
Decryption Example: b=a (mod p)
„ a=3-7X-10X2-11X3+10X4+7X5+6X6+7X7+5X8-3X9-7X10
(3,-7,-10,-11,10,7,6,7,5,-3,-7)

„ b=a (mod 3), change coefficients to [-1,1]

„ b=-X-X2+X3+X4+X5+X7-X8-X10 (mod 3)
(0,-1,-1,1,1,1,0,1,-1,0,-1)

5/23/2006 [email protected] 21
Decryption Example: c=fp*b (mod
p)
„ fp=1+2X+2X3+2X4+X5+2X7+X8+2X9
(1,2,0,2,2,1,0,2,1,2,0)
„ b=-X-X2+X3+X4+X5+X7-X8-X10
(0,-1,-1,1,1,1,0,1,-1,0,-1)

„ (0,-1,-1,1,1,1,0,1,-1,0,-1)*(1,2,0,2,2,1,0,2,1,2,0)=
„ (0,-1,-2,0,-2, -2,-1,0,-2,-1,-2,0)+
„ (0,0,-1,-2,0,-2, -2,-1,0,-2,-1,-2)+
„ (1,2,0,1,2,0,2,2,1,0,2)+
„ (2,1,2,0,1,2,0,2,2,1,0)+
„ (0,2,1,2,0,1,2,0,2,2,1)+ m = (-1,0,0,1,-1,0,0,0,-1,1,1)
„ (2,1,0,2,1,2,0,1,2,0,2)+
„ (-2,-2,-1,0,-2,-1,-2,0,-1,-2,0)+ equal
„ (-2,0,-2,-2,-1,0,-2,-1,-2,0,-1)
„ mod 3, change to [-1,1], therefore c = (-1,0,0,1,-1,0,0,0,-1,1,1)

5/23/2006 [email protected] 22
Summary
„ Parameters: N, p (small prime), q (big number, power of
2, gcd(p,q)=1)
„ Private Key: Two randomly generated “small”
polynomials f, g
„ Computing fq, fp, fq*q=1 (mod q), fp*p=1(mod p)
„ Public key: h=pfq*g (mod q)
„ Encryption: randomly generated “small” polynomial r as
blind value
e=r*h+m (mod q), e is cipher text, m is plaintext
„ Decryption: a=f*e (mod q), b=a (mod p), c=fp*b (mod p),
change the coefficients, c is the result, which should be
equal to m

5/23/2006 [email protected] 23
Why it Works
„ a=f*e (mod q) [e=r*h+m (mod q)]
„ =f*(r*h+m) (mod q) [h=pfq*g (mod q)]
„ =f*(r*pfq*g+m) (mod q) [f*fq=1 (mod q)]
„ =pr*g+f*m (mod q)
The polynomial r, g, f, m all have coefficients that are quite small, so the
coefficients of r*g and f*m are also quite small, at least in comparison to
q. Since prime p is also small compared to q, this means the polynomial
pr*g+f*m lie between –q/2 and q/2, so reducing the coefficients mod q
has no effect.

b=a=f*m (mod p)
c=fp*b=fp*f*m=m (mod p) [since fp*f=1 (mod p)]
5/23/2006 [email protected] 24
Presentation Outline
„ Algebra Tutorial
… Modular Arithmetic
… Truncated Polynomial Rings
… Inverse in Truncated Polynomial Rings
„ The NTRU Public Key Cryptosystem
… NTRU PKCS Parameters
… Key Generation
… Encryption
… Decryption
… Why It Works
„ Advanced Topics (Optimizations)
„ Implementation Details

5/23/2006 [email protected] 25
Optimizations
Reference:
„ J. Hoffstein, J. Silverman, “Optimizations for NTRU,” In:
Proc. of Public-Key Cryptography and Computational
Number Theory (Warsaw, September 11-15, 2000),
Walter de Gruyter, Berlin-New York, 2001.
„ J. Hoffstein, J. Silverman, “Random Small Hamming
Weight Products with Applications to Cryptography,” In:
Proc. of Com2MaC Workshop on Cryptography
(Pohang, Korea, June 2000), Discrete Mathematics, to
appear.

5/23/2006 [email protected] 26
Optimizations (cont.)
„ Polynomial Multiplication
… Low Hamming Weight Polynomials
e.g. m, f, g, r,
… Products of Small Hamming Weight Polynomials
e.g. h=pfq*g (mod q), e=r*h+m (mod q), a=f*e (mod q)
… Instead of taking f to be a single small polynomials,
form it by combining several even smaller
polynomials
e.g. in full-size versions of the cryptosystem, with
N=251, usually take small polynomials so that about
one third of the coefficients are non-zero

5/23/2006 [email protected] 27
Optimizations (cont.)
„ e.g. for computing i*a, i=[1,0,1,1,1,1,1,1,0,0,1,1,0]
„ i=i1*i2=[1,0,1,0,0,0,0,1,0,0,0,0,0]*
„ [1,0,0,1,1,0,0,0,0,0,0,0,0]
„ I has 9 ones, so i*a take 9 additions pre coefficient
„ If we instead I with i1 and i2
„ First calculate i2*a, it take 3 additions pre coefficient,
then calculate i1*(i2*a), it take another 3 additions per
coefficient, so the total is 6 additions per coefficient, only
take 2/3 as long

5/23/2006 [email protected] 28
Optimizations (cont.)
„ For commercial ntru, N=251
„ Short vector have about 72 non-zero coefficients
„ For decryption, a = f*e (mod q), let f=1+p*F
„ dF=72, f=1+p*((f1*f2)+f3)
„ df1=8,df2=8,df3=8, so it takes 24 additions pre
coefficients, not 72
„ For encryption, e=r*h+m (mod q), let r=(r1*r2)+r3
dr1=8, dr2=8, dr3=8, so it takes 24 additions pre
coefficients, not 72

5/23/2006 [email protected] 29
Presentation Outline
„ Algebra Tutorial
… Modular Arithmetic
… Truncated Polynomial Rings
… Inverse in Truncated Polynomial Rings
„ The NTRU Public Key Cryptosystem
… NTRU PKCS Parameters
… Key Generation
… Encryption
… Decryption
… Why It Works
„ Advanced Topics (Optimizations)
„ Implementation Details

5/23/2006 [email protected] 30
Implementation Details
„ Source code:
www.cs.unlv.edu/~renw/ntru_v22.c
„ Document:
www.cs.unlv.edu/~renw/ntru-tutorial-impl.pdf
„ Language: ANSI C
„ Compile: gcc ntru_v22.c –o ntru
„ Usage: ntru plaintext (max length is 11, ‘0’ and
‘1’ character)
eg. Ntru 11111000001

5/23/2006 [email protected] 31
Functions in Program
„ GF_Ntru_ParameterSetup(11,32,3);
„ GF_Ntru_PrivateKeyGen();
„ GF_Ntru_PublicKeyGen();
„ GF_Ntru_BlindValueGen();
„ GF_Ntru_GetPlainText();
„ GF_Ntru_Encrypt();
„ GF_Ntru_Decrypt();
„ GF_Debug_Check_Result();

5/23/2006 [email protected] 32
Program Organizations

Function-Calling Graph Data Flow Diagram

GF_Ntru_ParameterSetup(11,32,3)

GF_Ntru_PrivateKeyGen() GF_Ntru_ParameterSetup

GF_Ntru_PublicKeyGen() GF_Ntru_PrivateKeyGen GF_Ntru_Encrypt

GF_Ntru_BlindValueGen() GF_Ntru_PublicKeyGen
Main() GF_Ntru_Decrypt
GF_Ntru_GetPlainText() GF_Ntru_BlindValueGen

GF_Ntru_Encrypt() GF_Ntru_GetPlainText

GF_Ntru_Decrypt()

GF_Debug_Check_Result()

5/23/2006 [email protected] 33
Implementation Details (cont.)
Low weight hamming polynomial product, e.g. e=r*h + m (mod q)
„ for(t=0;t<GV_N;t++) //using low weight hamming polynomial multiplication
„ {
„ if (r[t]==1)
„ {
„ for(i=0;i<GV_N;i++)
„ e[i]=e[i]+h[i];
„ }
„ if (r[t]==-1)
„ {
„ for(i=0;i<GV_N;i++)
„ e[i]=e[i]-h[i];
„ }
„ // h[ ] one right shift
„ int swaptemp=h[GV_N-1];
„ for (i=GV_N-1;i>0;i--)
„ {
„ h[i]=h[i-1];
„ }
„ h[0]=swaptemp;
„ }

5/23/2006 [email protected] 34
What’s Next
„ Implement commercial version, NTRU503, (on-
going, in debugging stage)
„ Hardware-software co-design Optimization
… montogomery multiplication hardware implementation
(VHDL, ModelSim)
„ Performance comparison between RSA, ECC in
sensor network platform
„ Scrutiny of NTRU security (Lattices)
„ Ntru-based Key management (authentication,
signature) for wireless sensor network security

5/23/2006 [email protected] 35
Acknowledgement

I would like to thank Prof. Yoohwan Kim, Prof.

Mei Yang and Prof. Yingtao Jiang for the
insightful comments and discussions.

5/23/2006 [email protected] 36
References
„ The NTRU Public Key Cryptosystem – A Tutorial,
http://www.ntru.com/cryptolab/tutorials.htm, last access is May 19,
2006

The End and Thanks

5/23/2006 [email protected] 37