Public key encryption is a fundamental part of decentralized blockchain development. When we discussed this topic previously, I concluded with selecting Elliptic Curve Cryptography as the basis for the Seed blockchain project.
In my previous research, I was specifically looking at common place cryptography schemes, and comparing between them. We failed to look at so called "quantum proof" or "quantum resistant" cryptography. We are now going to look into an alternative type of cryptography and see whether it is a valid alternative for us to consider.
Previous posts I've written about cryptography in blockchain systems
Lattice Based Cryptography
Now, we're going to look into a specific type of cryptography known as Lattice Based Cryptography. This will be a large topic that will be split into two posts. Today we are first going to establish what makes our current cryptography work, what the potential flaw is in our currency systems, and what makes lattices an alternative. After that, we will go into a sample problem and see how lattices can be used for a (simple) cryptography scheme.
Part two will focus on comparing this alternative to Elliptic Curve Cryptography in detail, determining if Seed should become quantum-proofed with lattices or stick to the tried-and-problem traditional route.
Core of Cryptography
Cryptographic schemes are designed around computational hardness, a section of Computational Complexity Theory. In short, this theory of study is focused around the complexity of work in computing and how algorithms of a certain structure behave compared to others. Cryptography specifically focuses on a subset of problems within this theory known as "Hard Problems".
What Is A Hard Problem?
A "Hard Problem" is a problem which is computationally difficult to solve for traditional computers. These are problems which may be easy or difficult to build, however once the problem is built, there is no theorized solution to solve it in less than exponential-time.
Exponential-time simply means that how long it takes to crack the algorithm goes up in difficulty exponentially. If I said "prove to me that every person has green eyes", the difficulty at solving this problem goes up linearly, as adding one more person to check adds one more check for you to do. An exponential problem is one where, for each extra "person" to check, the amount of overall checks goes up exponentially. Maybe 5 people meant 25 checks, 10 people meant 100 checks, and 100 people meant 10,000 checks.
P vs NP Problem
Almost all of our current cryptography is based around a specific group of Hard Problems known as "P vs NP Problems". This is an open question, which could become a series of posts on their own. To keep this short, these problems are effectively a type of problem which are very easy to built, and hard to solve. They are categorized in a venn diagram like system where certain problems are NP Problems, NP-Hard and NP-Complete.
The important take away from these problems is this debated theory that if you can solve a NP-Hard problem in less than exponential time, an algorithm exists for every NP-Hard problem which can solve it in the same time. If you can break one of these problems, you can break them all. So far, in traditional computing, no such algorithm exists.
Quantum Computing Threat
As stated above, if an algorithm can reduce the complexity of a NP-Hard problem in less than exponential time, all of such problems are potentially at risk. In the field of Quantum Computing, there are two Quantum Computing algorithms that have shown we can solve certain NP-Hard problems in polynomial time (which is less than exponential time).
The main one that I want to discuss is Shor's algorithm, which shows us how to solve the factoring problem in polynomial time, assuming a quantum computer exists which is powerful enough to utilize this algorithm. Factoring is a problem which relies on the P vs NP problem, and is at the heart of all RSA encryption. If quantum computers one day become common place, all RSA encryption is at risk. This also theoretically proves that Elliptic Curve Cryptography may be at risk to, as it could mean another algorithm exists which breaks the P vs NP problem it relies on.
Lattice - Solution For The Post-Quantum World
The heart of the problem is that quantum computers could break the type of hard problems we have relied on to date when building cryptographic systems. However, cryptography can be built on a number of hard problems. We simply need to find "Hard Problems" which are hard for both traditional computing and quantum computing.
Lattices are the most common alternative looked into to date.
What Is A Lattice?
Lattices have many meanings in mathematics, however the usage of lattices we are going to speak about today is a particular type in linear algebra. If you are familiar with vector spaces or matrices, lattices are similar, and the natural successor to matrices.
To build a three-dimensional lattice, take any two vectors going in differing direction. For example, V1(1,0,0), V2(0,1,0) and V3(0,0,1). To build a lattice, we take these vectors and create a point on a place for each possible coefficient of X or Y that can be multiplied in. For example, for the above vectors, they build a lattice where:
| (1,0,0) | (0,1,0) | (0,0,1) | (15,3,20) | (30,50,120) | (-99,-99,-99) |
|---|
are all valid points on the lattice.
Lattice Hard Problems
We can build problems around these lattices that are proven to be hard enough to base cryptography around. These problems are all proven to be hard by both standard computing and quantum computers. Hard Problems we can build around these lattices include the Shortest Vector Problem, Closest Vector Problem, Bounded Distance Decoding and Covering Radius Problem.
Usage In Cryptography
So far, using the four listed above hard problems, cryptographic systems have been built to prove one-way hashing, symmetric encryption, and public-key encryption among others. Not every usage has been recreated using lattices yet, however every use case which cryptocurrencies use has.
Example of Lattice Cryptography
To show how lattices can be used in cryptography, we're going to show a relatively simple public-key encryption system built around lattices. This example is difficult, and is simplified for this post. Truthfully, this is where my knowledge becomes fuzzy and I must trust the experts who devote their lives to studying these schemes.
The following example is how Alice and Bob use lattices to encrypt one bit of information, for Alice to decrypt after and determine what Bob sent.
Pre-Setup
At the start, our two users Alice and Bob agree on a two-dimensional lattice A[mn]*, where m is the maximum width and n is the maximum height. They also degree on some large variable Q, where each vector inside the lattice is determine from a modulus operation on Q.
- A and Q are public for everyone to see
- Q is larger nuber than any vertex in the lattice.
- E.g. For the lattice is "2x+y" where m is 2 and n is 3
- Q > 8
- E.g. For the lattice is "2x+y" where m is 2 and n is 3
Alice's Private Key & Public Key
Alice creates a secret vector (her private key) X of size m, and publishes U (her public key)
- Each entry in X is either a 0 or a 1
U = (lattice A) * (vector X)
Note: X ?= (A^-1)*U
X is protected by a collision resistance hash function, which is the public lattice multiplied by the private vector. This is a "hard problem" that is difficult for both standard and quantum computers to inverse.
Bob's Private-Key & Message
Bob creates a secret vector (private key) S of length m.
For his message, he then creates two error vectors (E1 and E2), and two lattice basis' B1 and B2
- Each entry in E1/E2 are much smaller than Q/2
B1 = (lattice A) * (vector s) + E1
B2 = (lattice U) * (vector s) + E2 + [bit to send] * (Q/2)
Bob then publishes B1 and B2 for all to see
Decryption
To decrypt Bob's message, Allice simply uses the formula:
B2 - B1 * X = (S * U) + E2 + [unknown bit] * (Q / 2) - (S * U) + (E1 * X)
Now, the positive (S * U) subtracts with the negative one, leaving Alice with the final result
B2 - B1 * X = (E2 - E1 * X) + [unknown bit] * (Q / 2)
What's interesting is that this is all we need to solve the problem. Due to the nature of the setup, (E2 - E1 * X) will be a very very small number, close to zero. Because a bit can either be a zero or a one, [unknown bit] * (Q / 2) will either be zero or a very large number.
Therefore, when Alice does B2 - B1 * X, if she gets a number close to zero, she can infer that Bob sent a zero. If she gets a large number, she can infer that Bob sent a one. She has successfully decrypted his message.
How Is This Example & Algorithm Hard?
There were two pieces of "secret" information that was protected during this problem.
Private Key to Public Key Hashing
When turning the "secret vector" into the public key, we multiplied the secret vector by the agreed upon lattice A.
U = (lattice A) * (vector X)
requires solving
X ?= (A^-1)*(U)
This is a collision resistant one-way hashing algorithm that takes exponential-time to break for both standard computers and quantum computers.
Encryption: Learn With Error Problem
The encryption mechanism used in this example is one theorized to be as hard as the Learn With Error Problem in cryptography. This problem takes exponential time, and is NOT an P vs NP Problem. To date, this problem is still believed to be quantum resistant on its own.
Therefore, the hiding of the unknown data within the algorithm was done in a way which keeps it quantum resistant, only to be decoded by someone who has the secret vector X.
Is Lattice Based Cryptography Valid?
Lattice based cryptography appears to be a valid alternative to traditional cryptography. Many developers refer to cryptocurrencies that rely on lattice cryptography as "quantum proof", however many experts would argue that claim to be overly ambitious. In truth, we don't know everything, and are merely speculating on the future power of quantum computers. We know enough to know that this is a very real threat that is worth finding alternatives for, however we don't know enough to guarantee that lattice cryptography is in-fact quantum proof. Until we have a higher degree of certainty, I believe experts should keep trying to find more problems, and build a diverse set of post-quantum cryptographies rather than put all of our eggs in one basket.
Thank you for reading and sticking through a rather intensive post. I am not an expert on cryptography, and may have made a mistake here or there during the documenting of my research. If I have made any flaws, I encourage you to call me out in the comments.
Part 2 will focus on comparing Lattice cryptography to Elliptic Curve Cryptography directly. Comparing the amount of bits required for public keys, the differences in efficiency, and determine whether Seed should adopt Lattice cryptography or stick to the traditional ECC route.