Lattices in Cryptography and Quantum Computers
Lattices
Lattices are the most promising candidate for quantum security. We have been studying these problems since many years, and there is a significant amount of research in this topic. There are other schemes based on other assumptions like code based cryptographies, etc. These are important in the case Lattices are broken since these have completely independent assumptions.
What is Lattice? A Lattice is defined over a space consisting of linearly independent vectors . We refer to the matrix . Then,
We usually consider in analysis. For example, in , . This is equivalent to considering the integer grid points in the basis . This is a countable space unlike a normal vector space. A lattice is not unique to set of basis vectors! Any basis of the form , where and will have the same basis.
Consider a few computational problems in Lattices -
- Given , compute whether . This is polynomial computable using Gaussian elimination.
- Given , compute whether . This is polynomial computable as well, using the above problem. An equivalent way to find this is to consider iff has integer entries and as seen above.
- SVP (Shortest Vector Problem) - Given a basis in , find a nonzero shortest vector in . This is computationally hard for higher (quantumly hard too). An approximation asks for with , where is the length of a shortest nonzero lattice vector.
- CVP (Closest Vector Problem) - Given a basis and a target , find minimizing . CVP is closely related to SVP, but is a distinct problem.
Conjectures - SVP and CVP are quantumly hard!
Can we use NP-complete problems for cryptography? Most of these problems are worst-case hard, and there are good approximation algorithms for the average case. So with these problem constructions, we are looking for average-case hard complexity. The knapsack problem, for example, is related to Lattice problems.
How can we construct public key cryptography schemes with lattices? The basis assumption is that computing a ‘good’ basis from a ‘bad’ basis is intractable. For example, consider the following
- A secret key is constructed using a ‘good’ basis (for CVP) -
- A public key is constructed using a ‘bad’ basis -
- such that encodes . The cipher text is where usually so that the problem reduces to CVP
- recovers using .
There are more computationally hard problems like the SIS (Shortest Integer Solution) and LWE (Learning with Errors). SIS and LWE can be reduced to one another and both of them are harder than and . For example, Learning With Errors is much harder problem - it is average case hard if is worst case hard for . These problems, especially LWE, present a new paradigm in cryptography known as homographic encryption. The idea is that any operations performed on the messages (decrypted space) can be reflected in the encrypted space. For example, say we are encrypting photos uploaded to the cloud. If you are adding a new picture, then we should be able to encrypt the new data alongside the old one without recomputing the encryption for the data as a whole again. In homographic encryption, we need not perform the encryption again for all the set of pictures, but rather just on the new picture and append it to the old data.
Let us see the definitions of these problems -
-
Shortest Integer Solution - Let , . The goal is to find such that
- is ‘short’ - and
The parameters used to define this problem are given by , and for some . These parameter choices can be chosen to be something else if the theoretical bounds exist, but this particular set of parameters can be reduced to where .
There is a variant of this problem known as Inhomogeneous Short Integer Solution (ISIS) - We equate instead of equating to .
How are these related to lattices? All solutions form a lattice defined by
Consider any , then it is easy to see that for any , . Let us define a cryptographic application to get a gist of how we use these problems -
-
Collision-Resistant Hash Function - The security for such a function is that, given the description of such a hash function, it is difficult to find a collision. Using Grover’s Algorithm, typical hash functions can be broken with a quadratic speed-up as compared to classical algorithms. Here, we construct a hash function using SIS that cannot be broken with Grover’s -
- Construction - Sample , . Unlike SIS, the input here is binary rather than from .
- Security - Assume we find such that . Since , .
There are other implementations more efficient that this construction, but it acts like a good starting point.
-
Signatures (GPV Signature) - Unlike the previous case, this is the most efficient construction we know for public key cryptography. For a signature, we need to define the constructions for a verification key and a signing key - a trapdoor to help us find solutions for ISIS.
- maps , uses to find such that , and sets the signature .
- maps , check whether and is ‘short’.
Intuitively, we are able to find a secret key using a trapdoor that satisfied ISIS. The verification procedure is simple wherein can be verified to be short and satisfying the modulus equation.
The research for concluded in 2010’s. The gist of the trapdoor is the following - suppose we sample and . Then, we construct . Then satisfies .
The National Institute of Standards and Technology (NIST) submitted FALCON and DILITHIUM based on GPV signatures along with other building blocks for post-quantum cryptography.
The SIS problem still has limited structure limiting its applications. Next, we shall see LWE which allows us to construct many cryptographic schemes.
-
Learning With Errors (LWE) - The parameters used in this problem are where and is an error probability distribution. The problem is as follows - say there is a uniformly random . The goal is to recover from samples where , , and . Note that if there were no error involved, then this problem is very easy - perform Gaussian elimination to recover . is typically chosen as a Gaussian distribution modified to work with the space -
where .
More elegantly, the LWE problem is described using a matrix formulation -
Given and , determine from . This is known as the search version of LWE. Distinguish LWE is an equivalent formulation where, given with the same distributions as before, the goal is to distinguish and where . To get an intuition, we consider the following example schemes -
-
Public-key Encryption -
Kyber is one such scheme, motivated from this, which is now being used by Apple (as of 2024) to encrypt messages on iMessage. SABER, NTRU are other public-key encryption schemes.
-
-
-
choose and output
-
output
Now, since and is ‘short’, we can bound (A loose bound). We have the following range for .
-
Security - Consider the following two problems -
- Given , and , find .
- Given and , find
Now, distinguishing the above two scenarios is equivalent to solving the DLWE problem! This proves the security.
-
-
Key-Agreement Protocol - In this scenario, we want two parties to establish a secret key. Let us say have a common matrix they agree on.
- To do so, samples and samples such that are short. This ensures that are in as well. They also have associated error distributions respectively.
- sends and sends
- computes
- computes
- To avoid the small chance of error, choose the first bits of the obtained values. The error will most likely not affect these bits, and both parties obtain the same key.
- For an eavesdropper, both are completely random and the security is guaranteed by LWE.
LWE has properties such begin fully homomorphic and identity-based (encrypt the message for a specific group of secret-keys). LWE can also be used for the proof of quantumness.
The bigger picture has more problems as compared to LWE. However, the theory for LWE is robust and therefore is widely used in post-quantum cryptographic protocols.
Quantum Computers
How do we make qubits, gates and quantum computers. The first Turing complete programmable computer is the ENIAC. It was built using vacuum tubes and occupied a lot of space. After that we transitioned to transistors, and the growth has been exponential. Since 1950’s to 2010’s, we were able to progress from 1 transistor to 1-trillion transistors packed in the same area. This was correctly predicted by the Moore’s law - the number of transistors in an integrated circuit doubles roughly every two years (or eighteen months).
In quantum computers, we are currently at the initial stage like the ENIAC - trying to figure out how to efficiently store the qubits. The following technologies are being experimented with -
- Atoms - Trapped Ions, Cold Atoms - We prepare individual wells or prisons where ions are trapped electromagnetically. Two ions trapped can represent an entangled state. Lasers are used to control the properties of these ions. The qubits remain coherent for an impressive amount of time - for a few minutes. Typically, qubits are heavily influenced by the environment - the environment gets decohered easily. However, this technology is not easy to scale - the best we can do is 30 qubits. Also, applying 2-qubit gates using lasers is quite difficult.
- Superconductors - The idea is to cool certain metals to - The materials then lose their electromagnetic properties. When two metals close together are cooled down, then they form a qubit due to quantum tunnelling effect. The operations are still conducted by lasers but the scalability is better. The quantum computers currently being used by Google and IBM are made from this technology. The accuracy is not high but scalability is easy (these companies use those big numbers to increase stock prices). The longevity is in the order of microseconds!
- Photons - There are some controversies with photons, with regards to using them as universal qubits. The qubits are formed using circulating in waveguides using the polarity of photons. This are difficult to scale and it is difficult to use them for ‘quantum speedup’ algorithms.
- Silicon dots - Artificial atoms made by adding an electron to silicon and these are controlled by microwaves. This is still in the experimental stage.
Currently, the accuracy for quantum gates is not as good for consumer use - the accuracy is 99.9%. IonQ based on trapped ions is currently at around ~35 qubits whereas IBM based on superconducting technology is at a 1000 qubits. However, the error per qubit in the latter case is around 2% making it infeasible to do any practical applications with these chips. Both these strides in accuracy and size are needed to reach quantum supremacy. How many years would it take to reach fault-tolerant quantum computers with a million qubits? We are not sure. The problem is not with the technology, but with the engineering - quantum computers require a lot of calibration to work with a good accuracy.
Recently, a few noisy qubits (53 in total) were able to outperform the fastest classical computers on the Poisson sampling problem. The fastest classical computers would take around 10,000 years to solve this problem!1 This shows promise in the era of quantum computing.
1: IBM showed that this result is feasible using their classical supercomputer which took 2 days to solve the problem. Even then, a few qubits solved this in minutes, so quantum supremacy is still a promising avenue.