Lattice Encryption: NTRU Key Generation
Lattice Encryption: NTRU Key Generation
I have created a demonstrator of the method here.
Introduction
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 article 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:
==== 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]
Implementation
NTRU is a asymmetric encryption and has been benchmarked as twice as fast as RSA to encrypt, and three times faster to decrypt. NTRU was 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]:
I have created a demonstrator here. An outline of the code is code [here]:
Conclusions
If quantum computers are built at scale, say goodbye to RSA, Discrete Logarithm and Elliptic Curve methods. Lattice methods provide one way to define a hard problem, that even quantum computers would find difficult.