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.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store