Author: Elson Liu

Background

Quantum computing continues to develop at a staggering pace. With traditional cryptographic schemes—like RSA and Elliptic Curve Cryptography (ECC)—going bust in the dooming presence of advanced quantum algorithms (i.e. Shor’s algorithm), cryptographers are in urgent need of a quantum resistant solution. One of the most promising candidates is lattice-based cryptography.

In this article, we’ll introduce the fundamental concepts of lattice-based cryptography and discuss why it’s such a critical technology for “future-proofing” digital security.

The Issue

Quantum computing has the potential to revolutionize computation by solving certain hard mathematical problems at unprecedented speeds. As of July 2024, superconducting qubits are expected to reduce the time required for the factorization of a 576-bit number from months down to 3 hours. For traditional cryptography, this is a looming nightmare; Shor’s algorithm can efficiently factor large numbers, which underpins the security of RSA, and can tackle discrete logarithms used in ECC. As quantum machines mature, these once-unfeasible attacks could become trivial, threatening to unravel the security that underlies the internet, financial transactions, and secure communications.

Lattices: The New Foundation

A lattice, in mathematical terms, can be visualized as a grid of points extending infinitely in multiple dimensions. Each point in this grid is formed by taking integer combinations of a set of basis vectors. Concretely, if you have basis vectors $b_1, b_2, \cdots$ the lattice is the set of all points you can form by summing integer multiples of these vectors. As a quick example, let’s select two linearly independent base vectors in R2 to construct a 2-dimensional lattice: $b_1 = (2,0)$ and $b_2 = (1,2)$.

With these two base vectors as a foundation, we can construct the full lattice by trying all the linear combinations of the base vectors with integer coefficients, also expressed as:

$R=m*b_1 + n*b_2$, where $m$ and $n$ are integers, which satisfies $R=(2m + n, 2n)$ and $(m, n)$ takes on all integer values. This construction creates a discrete set of points in $\mathbb{R}^2$, forming a regular pattern that repeats periodically and infinitely in all directions. Each point in this lattice can be reached by integer combinations of the base vectors $b_1$ and $b_2$.

Hard Problems in Lattices

This geometric structure provides a rich source of hard mathematical problems even for quantum computers. Two of the most celebrated hard problems used in lattice- based cryptography are:

1. Shortest Vector Problem (SVP): Given a lattice, the SVP asks you to find the shortest nonzero vector in that lattice. For example, in the 2D lattice we just defined, we need to consider various combinations:

   • $b_1 = (2, 0)$, length = 2

   • $b_2 = (1, 2)$, length = $\sqrt5$

   • $b_2 − b_1$ $=(−1, 2)$, length = $\sqrt5$

   • $2b_1 − b_2 $ $=(3, −2)$, length = $\sqrt{13}$

   In this case, the shortest non-zero vector is $b_1 = (2,0)$ with length 2.

   Although this process seems intuitive, keep in mind that this is a straightforward 2D lattice with “nice” base vectors. If the base vectors are highly skewed—almost parallel—finding the shortest vector becomes excruciatingly difficult. This is because finding the shortest vector would require a lot more than four checks, increasing the computational effort required. Furthermore, we can make this even harder on top of using nearly parallel vectors by using a higher dimensional lattice. The number of potentially shortest vectors grows exponentially with the dimension, which makes an exhaustive search for high dimensional lattices impractical.

2. Learning with Errors (LWE): The LWE problem revolves around the difficulty of solving systems of linear equations slightly “noised” by small errors, which disables simple algebraic techniques. Specifically, in a finite field defined by the modulus of a random integer, we pick a random vector $a_i$. We then decide on a secret vector, $s$ in the same finite field and use $s$ and $a_i $to generate a vector $b_i$ with a small error, $e_i$ added. The goal is to recover the secret vector $s$. For example, let’s consider the following:

Given:

Modulus $q = 17$

Dimension $n = 2$

Secret vector $s = (3, 5) \in \mathbb{R}^2$ mod $17$

Error distribution χ: uniform from the set {-1, 0, 1}

LWE samples $(a_i, b_i)$, where $a_i$ is random in $\mathbb{R}^2$ mod 17 and $b_i = (a_i * s) + e_i$ mod $17$: $a_1 = (7, 2$), $e_1 = 1$

$b_1 = (7 * 3 + 2 * 5 + 1)$ mod $17 = 32$ mod $17 = 15$ mod $17$

$a_2 = (11, 9)$, $e_2 = -1$

$b_2= (11 * 3 + 9 * 5 - 1)$ mod $17 = 77$ mod $17 = 9$ mod $17$

$a_3 = (4, 13)$, $e_3 = 0$

$b_3 = (4 * 3 + 13 * 5 + 0)$ mod $17 = 77$ mod $17 = 9$ mod $17$

The LWE problem is to recover the secret vector $s = (3, 5)$ given only the samples $(a_i, b_i)$. This is extremely challenging; as the modulus number and the dimensions of the lattice increases, the difficulty of the problem increases exponentially. Furthermore, even the fastest known quantum algorithm solves LWE in exponential time. While there are examples like AlphaQubit, a quantum error correction system developed by Google, that has shown success in decoding the surface code, which is related to error correction in quantum computing, the large-scale decryption remains infeasible. LWE underpins many lattice-based schemes, and its versatility has made it one of the cornerstones of post-quantum cryptography.

These two problems are applied to the famous Goldreich-Goldwasser-Halevi (GGH) encryption. Alice, the receiving party, first picks a “good” pair of base vectors to generate a high dimensional lattice. In this same lattice, structure, a “bad” pair of nearly parallel vectors are used as the public key to generate the cipher text, turning the process of deciphering into a version of solving the SVP. In the process of encryption, a random error is also chosen and incorporated into the cipher text by Bob, the encrypting party, which adds the difficulty of the LWE problem. Since Alice has access to the “good” pair of base vectors, she is able to recover the original message.

Here’s a run through:

1. Key Generation: Alice chooses a private "good" basis $B$: $B = \begin{bmatrix} 17 & 0 \\ 0 & 19 \end{bmatrix}$

2. She then selects a unimodular matrix $U$ (its inverse also has all integer entries): $U = \begin{bmatrix} 2 & 3 \\ 3 & 5 \end{bmatrix}$

3. The public "bad" basis $B'$ is computed as $B' = U * B$. First, compute $U * B$:

   $U * B = \begin{bmatrix} (217 + 30) & (20 + 319) \\ (317 + 50) & (30 + 519) \end{bmatrix}$

   Calculate the entries: $U * B = \begin{bmatrix} 34 & 57 \\ 51 & 95 \end{bmatrix}$

   So, $B' = \begin{bmatrix} 34 & 57 \\ 51 & 95 \end{bmatrix}$

4. Encryption

   Bob wants to encrypt the message $m = (2, -5)$. He chooses a random error vector $e = (1, -1)$. Compute $c = m \cdot B' + e$. First, calculate $m \cdot B': m \cdot B' = \begin{bmatrix} 2 \\ -5 \end{bmatrix} \cdot \begin{bmatrix} 34 & 57 \\ 51 & 95 \end{bmatrix}$

   This is a 1 x 2 vector times a 2 x 2 matrix: $m \cdot B' = \begin{bmatrix} (2*34 + (-5)51) \\ (2 * 57 + (-5)*95) \end{bmatrix} = \begin{bmatrix} (68 - 255) \\ (114 - 475) \end{bmatrix}$

   = $\begin{bmatrix} -187 \\ -361 \end{bmatrix}$. Now add the error vector $e = (1, -1): c = (-187, -361) + (1, -1) = (-187 + 1, -361 - 1) = (-186, -362)$.

   So, the cipher text $c$ is $(-186, -362)$.

5. Decryption

   Alice receives $c = (-186, -362)$. To recover m, Alice uses $B^{-1}$. Since $B = \begin{bmatrix} 17 & 0 \\ 0 & 19 \end{bmatrix}$, its inverse is: $B^{-1} = \begin{bmatrix} 1/17 & 0 \\ 0 & 1/19 \end{bmatrix}$. Compute $c \cdot B^{-1}$: $c \cdot B^{-1}$ = $\begin{bmatrix} -186 \\ -362 \end{bmatrix} \cdot \begin{bmatrix} 1/17 & 0 \\ 0 & 1/19 \end{bmatrix}$ = $\begin{bmatrix} (-186)\cdot (1/17) + (-362)*0 \\ (-186)0 + (-362)(1/19) \end{bmatrix}$ = $\begin{bmatrix} (-186)/17 \\ (-362)/19 \end{bmatrix}$ ≈ $\begin{bmatrix} -10.94 \\ -19.05 \end{bmatrix}$.

   Round each component to the nearest integer: $(-10.94, -19.05)$ → $(-11, -19)$.

   Now, multiply by $U^{-1}$. Since $U = \begin{bmatrix} 2 & 3 \\ 3 & 5 \end{bmatrix}$, you can find $U^{-1}$ (the inverse of U). The inverse of U is $\begin{bmatrix} 5 & -3 \\ -3 & 2 \end{bmatrix}$ (divided by the determinant 1, since U is unimodular: $U^{-1} = \begin{bmatrix} 5 & -3 \\ -3 & 2 \end{bmatrix}$. Compute $m = (-11, -19) \cdot U^{-1}$
   $m = \begin{bmatrix} (-11)* 5 + (-19)(-3) \ (-11)*(-3) + (-19)*2 \end{bmatrix}$= $\begin{bmatrix} (-55) + 57 \\ 33 + (-38) \end{bmatrix}$ = [2, -5].

   This returns the original message $m = (2, -5)$.

Implementations

1. Oasis Labs: Oasis Labs is a pioneer in blockchain privacy technology founded Berkeley professor, Dr. Dawn Song. By leveraging Secure Multi-Party Computation (SMPC) techniques (which can be built on lattice-based foundations), Oasis Labs protects users’ sensitive data— such as ethnicity information on Instagram—without revealing it to third parties. Crucially, they created the idea of “smart privacy”, which allowed privacy features to be implemented on existing smart contracts through Sapphire, a confidential EVM (Ethereum Virtual Machine) that enables granular privacy control.

2. CRYSTALS-Dilithium: This post-quantum digital signature scheme is built on lattice problems and offers smaller private keys and faster signatures than many traditional alternatives. It’s already gaining traction as one of the leading candidates for future authentication standards after submitting to NIST's post-quantum cryptography standardization process and becoming a finalist.

3. QAN Platform: QAN is a quantum-resistant blockchain platform that incorporates lattice-based cryptography to secure decentralized applications and financial transactions against future quantum threats. This ensures that the integrity of blockchain systems remains robust, even as quantum machines scale up. They developed the QAN virtual machine (QAN) that enables the execution of contracts in multiple different languages while ensuring compatibility with EVM.

A Final Note

As the world braces for the quantum computing revolution, it’s becoming increasingly clear that lattice-based cryptography shines as a beacon of hope. Whether it’s through the GGH scheme or other integrations, the mathematical complexity of lattices allows for a range of challenging problems even for the future. As we advance our understanding on both the quantum and the lattice frontier, I remain hopeful that more efficient and secure scheme will emerge to create a privacy preserving future.

Thanks for reading!