The Times They Are A-Changing: Post Quantum Cryptography Brings Rings and Fully Homomorphic…
The Times They Are A-Changing: Post Quantum Cryptography Brings Rings and Fully Homomorphic Encryption
Just imagine, a future where all our data is encrypted, and where we can still process it. Seems like science fiction, but it is not.
Basically, over the next decade or so, we will say goodbye to our “flawed” public key methods of RSA and ECC (Elliptic Curve Cryptography), and say hello to methods that are provably hard, such as those based on lattices and learning with errors (LWE). Overall, RSA and ECC have done us well, and have allowed us to build with PKI and with blockchains, but they are at risk from quantum computers.
Introduction
Our existing public key methods have allowed us to build a more trusted Internet and create blockchain-based methods, but they are flawed. For one, they can be cracked by quantum computers, and for two, they did not implement full homomorphic encryption. But, things are changing, and the usage of lattice methods will scale public key methods into full homomorphic encryption. One of these methods is BFV (Brakerski/Fan-Vercauteren):
With homomorphic encryption, we see the rise of the Ring Learning With Errors (RLWE) problem. This involves adding noise in the encryption and key generation phases. As we do our computations, this noise increases, and we thus need to make sure that our ciphertext modulus (Q) needs to be large enough to cope with this noise growth. Otherwise, we can use a bootstrapping method to reset the noise (and where Q can then be relatively small).
Learning With Errors
The Microsoft SEAL library can support a range of homomorphic encryption methods, and which use Learning With Errors (LWE). In this case, we will implement homomorphic encryption using the BFV (Brakerski/Fan-Vercauteren) method. Overall, BFV is a ring LWE method, and where we have a public modulus of Q. We then have a secret key of s ( which is between 0 and Q-1), and a random polynomial value of A. We also have an error polynomial of e. For the public key, we create a polynomial of:
The polynomial values of A and B are then the public key, and s is the private key. To encrypt, we basically take samples from A and B and compute values of ai and bi:
and where M_i is the message bits (0 or 1). To decrypt (a,b), we perform:
Thus:
We then round each coefficient of m to either q/2 or zero. A value of q/2 is 1, and a value of zero is 0. This will work as e will be much smaller than q/2. A demonstration of this is here:
A very simple example is [here]:
Message to send: 0
Public Key (A): [80, 86, 19, 62, 2, 83, 25, 47, 20, 58, 45, 15, 30, 68, 4, 13, 8, 6, 42, 92]
Public Key (B): [15, 45, 2, 20, 13, 30, 32, 45, 4, 3, 34, 78, 55, 51, 23, 67, 44, 34, 17, 75]
Errors (e): [3, 3, 4, 1, 3, 3, 4, 4, 1, 4, 3, 3, 2, 2, 3, 2, 4, 4, 1, 3]
Secret key: 5
Prime number: 97
-----------------------
Sampling [18, 5, 8, 13, 11]
U is 34
V is 83.0
Message is a 0
And a message of 1 [here]:
------Parameters and keys-------
Message to send: 1
Public Key (A): [47, 27, 72, 89, 19, 64, 26, 79, 68, 83, 1, 76, 25, 65, 55, 82, 85, 14, 92, 5]
Public Key (B): [45, 41, 73, 61, 0, 33, 35, 10, 53, 31, 7, 92, 30, 38, 83, 24, 41, 71, 74, 27]
Errors (e): [4, 3, 4, 4, 2, 4, 2, 3, 4, 4, 2, 3, 2, 4, 2, 2, 4, 1, 2, 2]
Secret key: 5
Prime number: 97
------Sampling Process from public key-------
Sampling [7, 5, 16, 8, 2]
[ 79 10 ] [ 64 33 ] [ 85 41 ] [ 68 53 ] [ 72 73 ]
------Calculation of u and v -----------------
u: 77
v: 64.0
Result is 67.0
Message is a 1
Practical implementation of BFV
While the core code for the Microsoft SEAL (Simple Encrypted Arithmetic Library) library is in C++ and C#, we can convert this to be used with Node.js [here]:
This code will perform a homomorphic add, subtract and multiply of two cipher values. A sample run with a 2,048 bit public modulus is [here]:
Plaintext 1: Int32Array [ 2, 5, 3, 4, 5 ]
Plaintext 2: Int32Array [ 3, 5, 9, 11, 2 ]
Decrypted (Homomorphic Add): Int32Array [
5, 10, 12, 15, 7, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0,
... 3996 more items
]
Decrypted (Homomorphic Subtract): Int32Array [
-1, 0, -6, -7, 3, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0,
... 3996 more items
]
Decrypted (Homomorphic Multiplication): Int32Array [
6, 25, 27, 44, 10, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0,
... 3996 more items
]
Conclusions
It is as if we have put in place a temporary solution for over 40 years, and just waiting for learning with errors and lattices. One thing that is for sure, is that RSA and ECC will be leaving us within the next two decades, and lattice methods (with their polynomial representations) are likely to replace them. One of the key strengths is that we will be able to use homomorphic encryption to still compute on encrypted values. That will bring a whole new data world.
Here’s to a lattice future!