Could NTRU Still Become A PQC Standard and Dump Kyber?

Over the past few weeks, I have been outlining the usage of Kyber for a PQC (Post Quantum Cryptography) replacement for ECDH (Elliptic…

Could NTRU Still Become A PQC Standard and Dump Kyber?

Over the past few weeks, I have been outlining the usage of Kyber for a PQC (Post Quantum Cryptography) replacement for ECDH (Elliptic Curve Diffie Hellman) in key exchange. But did NIST get blinded by selecting the best-performing key exchange method? And, so Kyber was selected, but now there are some doubts, with D. J. Bernstein outlining:

I am thus deeply sceptical of claims that Kyber-{512,768,1024} are as hard to break as AES-{128,192,256} by known attacks, never mind the risks from future attacks. I recommend that NIST withdraw those claims. Furthermore, given the considerable risk of Kyber-512 being weaker than AES-128, I recommend terminating the standardization of Kyber-512

So, which method does the mighty djb recommend? Well, it’s NTRU — and which is (perhaps) a robust method from a security point-of-view [1]:

The NTRU (Nth degree TRUncated polynomial ring) public key method is a lattice-based method which is quantum robust. It uses the shortest vector problem in a lattice and has an underpinning related to the difficulty of factorizing certain polynomials. This page outlines the method used to generate the public key (h). With Lattice encryption, Bob and Alice agree to share N, p and q, and then Bob generates two short polynomials (f and g), and generates his key pair from this. Alice receives this, and she generates a random polynomial and encrypts some data for Bob. Bob then decrypts the message with his private key. We generate the public and private key from N, p and q.

Theory

NTRU is a asymmetric encryption and has been benchmarked as twice as fast as RSA to encrypt, and three times faster to decrypt. It is the public key method which is not based on factorization (RSA) or discrete logs (Elliptic Curve).

The following is taken from Wikipedia and shows the test case [here]:

Bob and Alice agree to share N (the largest polynomial power), p and q, and then Bob generates two short polynomials (f and g), and generates his key pair from this. These polynomials have the co-efficients of -1, 0 and 1. For example, with N=11, p=3 and q=32. If Bob picks values of:

f=[−1,1,1,0,−1,0,1,0,0,1,−1]

Then as a polynomial representation:

f=−1+x+x²−x⁴+x⁶+x⁹−x¹⁰

And then picks g:

g=−1+x²+x³+x⁵−x⁸−x¹⁰

We then should be able to calculate the inverse of f for (modp) and (modq). Thus:

f⋅fp (modp)=1

f⋅fq (modq)=1

Using an inverse function we get [here]:

fp=[9,5,16,3,15,15,22,19,18,29,5]

fp=9x10+5x9+16x8+3x7+15x6+15x5+22x4+19x3+18x2+29x+5

The public key then becomes:

h=p⋅fq.f (modq)

In this case we get:

fq⋅g=[−5,−9,−1,−2,11,12,13,3,22,15,16,29,60,19,−2,−7,−36,−40,−50,−18,−30]

In order to create a ring, we then divide by x^{N−1} and get:

H (Bob's Public Key): [24, 19, 18, 28, 4, 8, 5, 17, 4, 17, 16]

And the private key is f and fq. To encrypt we take Bob’s public key (h), a random polynomial (r) and a message (M), and then compute:

Enc=r⋅h+M

To decrypt, first we multiply by Bob’s private key fq and take (modq):

Dec=(r⋅h+M).f(modq)

and which gives:

Dec=(p⋅r⋅fq⋅g+M).f(modq)

and since (fq.f)(modq)

is 1, we get:

Dec=(p⋅r⋅g+M⋅f)

Finally we multiply by fp (mod p):

Dec=(p⋅r⋅g+M⋅f).fp (mod p)

This will be:

Dec=p⋅r⋅f⋅fp+M⋅f⋅fp (mod p)

And since we have a multipler of p, we will get a zero value for the first term as we have (mod p) operation:

Dec=0+M⋅f⋅fp(modp)

And since f⋅fp(modp) will be 1, we get:

Dec=M

Example values of the parameters are:

  • Minimal security: N=167,p=3,q=128
  • Good security: N=251,p=3,q=128
  • Strong security: N=347,p=3,q=128
  • Excellent security: N=503,p=3,q=256

A test run is [here]:

==== Bob generates public key =====
Values used:
 N= 11
 p= 3
 q= 32
========
Bob picks two polynomials (g and f):
f(x)=  [-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]
g(x)=  [-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1]
====Now we determine F_p and F_q ===
F_p: [1, 2, 0, 2, 2, 1, 0, 2, 1, 2, 0]
F_q: [5, 9, 6, 16, 4, 15, 16, 22, 20, 18, 30]
====And finally h====
f_q x g:  [-5, -9, -1, -2, 11, 12, 13, 3, 22, 15, 16, 29, 60, 19, -2, -7, -36, -40, -50, -18, -30]
H (Bob's Public Key):  [24, 19, 18, 28, 4, 8, 5, 17, 4, 17, 16]
====Let's encrypt====
Alice's Message: [1, 0, 1, 0, 1, 1, 1]
Random:   [-1, -1, 1, 1]
Encrypted message: [8, 2, 10, 23, 16, 7, 26, 2, 8, 3, 28]
====Let's decrypt====
Decrypted message: [1, 0, 1, 0, 1, 1, 1]

This should match the run above.

Code

The code is based on this code [here]

from fracModulo import extEuclidPoly,modPoly,multPoly,reModulo,addPoly,cenPoly, trim
N=11
p=3
q=32
f=[-1,1,1,0,-1,0,1,0,0,1,-1]
g=[-1,0,1,1,0,1,0,0,-1,0,-1]

print("==== Bob generates public key =====")
print("Values used:")
print(" N=",N)
print(" p=",p)
print(" q=",q)
print("========")
print("\nBob picks two polynomials (g and f):")

#f=[-1,0,1,1,-1,0,-1]
#g=[0,-1,-1,0,1,0,1]
d=2
print("f(x)= ",f)
print("g(x)= ",g)

D=[0]*(N+1)
D[0]=-1
D[N]=1

print("\n====Now we determine F_p and F_q ===")
[gcd_f,s_f,t_f]=extEuclidPoly(f,D)
f_p=modPoly(s_f,p)
f_q=modPoly(s_f,q)
print("F_p:",f_p)
print("F_q:",f_q)
x=multPoly(f_q,g)
h=reModulo(x,D,q)
print("\n====And finally h====")
print("f_q x g: ",x)
print("H (Bob's Public Key): ",h)
print("\n====Let's encrypt====")
msg=[1,0,1,0,1,1,1]
randPol=[-1,-1,1,1]
print("Alice's Message:\t",msg)
print("Random:\t\t\t",randPol)
e_tilda=addPoly(multPoly(multPoly([p],randPol),h),msg)
e=reModulo(e_tilda,D,q)
print("Encrypted message:\t",e)
print("\n====Let's decrypt====")
tmp=reModulo(multPoly(f,e),D,q)
centered=cenPoly(tmp,q)
m1=multPoly(f_p,centered)
tmp=reModulo(m1,D,p)
print("Decrypted message:\t",trim(tmp))

And here it is:

Conclusions

Perhaps we have not heard the end of this, and perhaps NTRU will come storming though and move to a standard?

References

[1] Bernstein, D. J., Chuengsatiansup, C., Lange, T., & Van Vredendaal, C. (2016). NTRU Prime. IACR Cryptol. ePrint Arch., 2016, 461.