Lattice based cryptography

Lattice based cryptography

With the growing possibility of quantum computing being able to crack RSA encryption (the encryption technique which currently secures most banking and digital communications), the search is underway to find quantum-computing proof encryption.  One potential possibility is lattice based cryptography – so I will explore the basics of this below!

Creating a lattice

To create a 2D lattice we need a basis – that is 2 vectors which will define the points of the lattice.  Let’s say I choose:

These can be geometrically represented by:

and then I plot all the points that can be obtained by the following (when p and q are integers):

This gives the the grid above – i.e the lattice of all integer coordinates.

I can also create more interesting grids with a different change of basis.  For example the following basis:

make the following lattice:

and I can specify 3 basis vectors in 3D such as:

which would create a lattice in 3D space of integer coordinate points:

Lattice cryptography

So how does lattice cryptography work?  The basic idea is that an identical lattice can be formed by different basis.  Some of the basis are “good” insofar as they quickly generate the lattice and some are “bad” insofar as they generate the same lattice very slowly.  A good basis will have vectors closer to orthogonal (at right angles) and a bad basis will have vectors closer to parallel.

Let’s say my good basis is:

and my bad basis is:

Both of these basis will describe the same lattice space. You can see the trend of how this will look below (gaps in the pattern due to not enough values being calculated).

So if Alice and Bob want to communicate they do as follows:

1. Alice chooses a good basis (which she keeps secret) and a bad basis (which is shared publicly)
2. Bob uses the bad basis to generate lattice points 
3. Bob chooses a lattice point (which symbolises a message he wants to transmit).  He keeps this secret – but he sends to Alice a coordinate which is closer to this point that any other lattice points in the grid.
4. Alice then uses her good basis to quickly generate the lattice grid and solve which lattice point is closest to the point that Bob has sent.  This is the secret message.

Using Python to create a decryption tool

I wrote a quick Python code to test this out.  The following code looks to allow Alice to decrypt a message of (103.5, 76) from Bob.  It uses the good basis of:

and then brute forces a large number of different linear combinations of these vectors to find which coordinate in the lattice is closest to Bob’s coordinate:

I’ve added a timer to see how long this process takes.  The code returns the correct solution (105,75) in an average of 12.37 seconds.  I then ran the same code but instead trying to crack this using the bad basis of:

This time it returned the correct answer after an average of 12.62 seconds.  Now this may feel a little underwhelming – all this to reduce the time from 12.62 to 12.37!  But this technique can be extended to as many dimensions as you like – you can have 20 basis vectors in 20 dimensional space.  This then becomes a much more challenging problem to brute force.

So a nice use of vectors and geometry in the never-ending quest to provide secure communications.