← All notes

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 Rn\mathbb R^n consisting of mm linearly independent vectors b1,…,bmb_1, \dots, b_m. We refer to the matrix B=(b1,…,bm)B = (b_1, \dots, b_m). Then,

L(B)={∑izibi  |  zi∈Z}\mathcal L(B) = \left\{ \sum_i z_i b_i \;\middle|\; z_i \in \mathbb Z \right\}

We usually consider m=nm = n in analysis. For example, in R2\mathbb R^2, b1=(1,2)T,b2=(2,1)Tb_1 = (1, 2)^T, b_2 = (2, 1)^T. This is equivalent to considering the integer grid points in the basis BB. 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 x1b1+x2b2,y1b1+y2b2x_1b_1 + x_2 b_2, y_1 b_1 + y_2 b_2, where x1y2−x2y1=±1x_1y_2 - x_2y_1 = \pm 1 and x1,x2,y1,y2∈Zx_1, x_2, y_1, y_2 \in \mathbb Z will have the same basis.

Consider a few computational problems in Lattices -

  • Given v,Bv, B, compute whether v∈L(B)v \in \mathcal L(B). This is polynomial computable using Gaussian elimination.
  • Given B,B’B, B’, compute whether L(B)=L(B’)\mathcal L(B) = \mathcal L(B’). This is polynomial computable as well, using the above problem. An equivalent way to find this is to consider B’=BUB’ = BU iff UU has integer entries and det⁡(U)=±1\det(U) = \pm 1 as seen above.
  • SVP (Shortest Vector Problem) - Given a basis BB in Rn\mathbb R^n, find a nonzero shortest vector in L(B)\mathcal L(B). This is computationally hard for higher nn (quantumly hard too). An approximation SVPγSVP_\gamma asks for v∈L(B)v \in \mathcal L(B) with ∥v∥≤γλ1(L(B))\|v\| \leq \gamma\lambda_1(\mathcal L(B)), where λ1\lambda_1 is the length of a shortest nonzero lattice vector.
  • CVP (Closest Vector Problem) - Given a basis B∈RnB \in \mathbb R^n and a target t∈Rnt \in \mathbb R^n, find u∈L(B)u \in \mathcal L(B) minimizing ∥t−u∥\|t-u\|. 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) - BB
  • A public key is constructed using a ‘bad’ basis - B’B’
  • Enc(pk,m)→ sample v∈L(B′){\sf Enc} (pk, m) \to \text{ sample } v \in \mathcal L(B') such that vv encodes mm. The cipher text is u=v+ηu = v + \eta where usually η∼N(0,σ2)\eta \sim \mathcal N(0, \sigma^2) so that the problem reduces to CVP
  • Dec(sk,u){\sf Dec}(sk, u) recovers vv using BB.

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 SVP/SVPγSVP/SVP_\gamma and CVP/CVPγCVP/CVP_\gamma. For example, Learning With Errors is much harder problem - it is average case hard if CVPγCVP_\gamma is worst case hard for γ=poly(n)\gamma = {\sf poly}(n). 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 A∈Zqn×mA \in \mathbb Z^{n \times m}_q, A=(a1,…,am),ai∈ZqnA = (a_1, \dots, a_m), \qquad a_i \in \mathbb Z_q^n. The goal is to find z∈Zmz \in \mathbb Z^m such that

    • Az≡0(modq)Az \equiv 0 ({\sf mod } q)
    • zz is ‘short’ - ∥z∥2≤β\|z\|_2 \leq \beta and z∈{−1,0,1}mz \in \{-1, 0, 1\}^m

    The parameters used to define this problem are given by m=poly(n)m = {\sf poly} (n), q=poly(n)q = {\sf poly} (n) and β=cm\beta = c \sqrt{m} for some c∈Rc \in \mathbb R. 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 CVPγCVP_\gamma where γ=O(n)\gamma = \mathcal O(n).

    There is a variant of this problem known as Inhomogeneous Short Integer Solution (ISIS) - We equate Az≡t(modq)Az \equiv t ({\sf mod} q) instead of equating to 00.

    How are these related to lattices? All solutions Az≡0(modq)Az \equiv 0 ({\sf mod } q) form a lattice defined by

    L⊥(A)={z∈Zm∣Az≡0(modq)}L^\perp(A) = \left\{z \in \mathbb Z^m \vert Az \equiv 0 ({\sf mod } q)\right\}

    Consider any z1,z2∈L⊥(A)z_1, z_2 \in \mathcal L^\perp(A), then it is easy to see that for any a,b∈Za, b \in \mathbb Z, A(az1+bz2)≡0(modq)A(az_1 + bz_2) \equiv 0({\sf mod}q). Let us define a cryptographic application to get a gist of how we use these problems -

    1. 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 A∈Zqn×mA \in \mathbb Z_q^{n\times m}, fA(x∈{0,1}m)=Ax(modq)f_A(x \in \{0, 1\}^m) = Ax ({\sf mod} q). Unlike SIS, the input here is binary rather than from Zq\mathbb Z_q.
      • Security - Assume we find x,x’x, x’ such that fA(x)=fA(x’)  ⟹  A(x−x′)≡0(modq)f_A(x) = f_A(x’) \implies A(x - x') \equiv 0 ({\sf mod} q). Since x,x’∈{0,1}mx, x’ \in \{0, 1\}^m, x−x’∈{−1,0,1}mx - x’ \in \{-1, 0, 1\}^m.

      There are other implementations more efficient that this construction, but it acts like a good starting point.

    2. 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 vkvk and a signing key sksk - a trapdoor TT to help us find solutions for ISIS.

      • Sign(sk,m)Sign(sk, m) maps m↦t∈Zqnm \mapsto t \in \mathbb Z_q^n, uses TT to find vv such that Av≡t(modq)Av \equiv t ({\sf mod} q), and sets the signature σ=v\sigma = v.
      • Ver(vk,m,σ)Ver(vk, m, \sigma) maps m↦t∈Zqmm \mapsto t \in \mathbb Z_q^m, check whether Aσ≡t(modq)A \sigma \equiv t ({\sf mod} q) and σ\sigma is ‘short’.

      Intuitively, we are able to find a secret key vv using a trapdoor that satisfied ISIS. The verification procedure is simple wherein vv can be verified to be short and satisfying the modulus equation.

      The research for TT concluded in 2010’s. The gist of the trapdoor is the following - suppose we sample A∈Zqn×mA \in \mathbb Z^{n \times m}_q and t← all short vectorst \gets \text{ all short vectors}. Then, we construct A′=[A∣−At]∈Zqn×(m+1)A' = [A \mid -At] \in \mathbb Z_q^{n \times (m + 1)}. Then t’=(t,1)Tt’ = (t, 1)^T satisfies A’t’≡0(modq)A’t’ \equiv 0({\sf mod} q).

      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 n,m,q,Xn, m , q, \mathcal X where m,q=poly(n)m,q = poly(n) and X\mathcal X is an error probability distribution. The problem is as follows - say there is a uniformly random s∈Zqns \in \mathbb Z_q^n. The goal is to recover ss from m=poly(n)m = poly(n) samples (ai,bi)(a_i,b_i) where bi=⟨ai,s⟩+ηi(modq)b_i = \langle a_i, s\rangle + \eta_i \pmod q, ai∈Zqna_i \in \mathbb Z_q^n, and η∼Xm\eta \sim \mathcal X^m. Note that if there were no error involved, then this problem is very easy - perform Gaussian elimination to recover ss. X\mathcal X is typically chosen as a Gaussian distribution modified to work with the Zq\mathbb Z_q space -

    Ψα=sample v∈Zqw.p. proportional to (e−∣v∣2α2/c)\Psi_\alpha = \text{sample } v \in \mathbb Z_q \\ \text{w.p. proportional to } \left(e^{\frac{-|v|^2}{\alpha^2}}/c\right)

    where α=O(1/n)\alpha = \mathcal O\left(1/\sqrt{n}\right).

    More elegantly, the LWE problem is described using a matrix formulation -

    Given A∈Zqn×mA \in \mathbb Z^{n \times m}_q and e∼Xme \sim X^m , determine s∈Zqns \in Z_q^n from sTA+eT(modq)s^T A + e^T ({\sf mod} q). This is known as the search version of LWE. Distinguish LWE is an equivalent formulation where, given A,e,sA, e, s with the same distributions as before, the goal is to distinguish A,sTA+eTA, s^T A + e^T and A,rTA, r^T where r∈Zqmr \in \mathbb Z^m_q. To get an intuition, we consider the following example schemes -

  1. 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.

    • pk=A,u=sTA+eTpk = A, u = s^T A + e^T

    • sk=ssk = s

    • Enc(pk,m∈{0,1}n):={\sf Enc} (pk, m \in \{0, 1\}^n) := choose x∈{0,1}mx \in \{0, 1\}^m and output c0=Ax(modq),c1=(ux+[q2].m)(modq)c_0 = Ax ({\sf mod} q), c_1 = \left(ux + \left[\frac{q}{2}\right].m \right)({\sf mod} q)

    • Dec(sk,c0,c1):={\sf Dec}(sk, c_0, c_1) := output

      c1−sTc0=(ux+[q2].m−sTAx)modqv=(eTx+[q2].m)modq\begin{align*} c_1 - s^T c_0 &= \left(ux + \left[\frac{q}{2}\right].m - s^T Ax\right) {\sf mod } q \\ v &= \left(e^T x + \left[\frac{q}{2}\right].m \right) {\sf mod } q \end{align*}

      Now, since x∈{0,1}mx \in \{0, 1\}^m and ee is ‘short’, we can bound ∥eTx∥<q/4\|e^Tx \| < q/4 (A loose bound). We have the following range for vv.

      0∣————∣————∣————⏟∣————∣qm=0m=1m=0\begin{align*} 0 |————|\underbrace{————|————}|————| q \\ m = 0 \quad\quad\quad\quad m = 1 \quad\quad\quad\quad m = 0 \quad \end{align*}
    • Security - Consider the following two problems -

      • Given pk=A,u=sTA+eTpk = A, u = s^T A + e^T, and c0=Ax,c1=ux+q2mc_0 = Ax, c_1 = ux + \frac{q}{2} m, find mm.
      • Given pk=A,u=rTpk = A, u = r^T and c0=Ax,c1=ux+q2mc_0 = Ax, c_1 = ux + \frac{q}{2}m, find mm

      Now, distinguishing the above two scenarios is equivalent to solving the DLWE problem! This proves the security.

  2. Key-Agreement Protocol - In this scenario, we want two parties A,BA, B to establish a secret key. Let us say A,BA, B have a common matrix M∈Zqn×nM \in \mathbb Z_q^{n \times n} they agree on.

    • To do so, AA samples r∈Znr \in \mathbb Z^n and BB samples s∈Zns \in \mathbb Z^n such that r,sr, s are short. This ensures that r,sr, s are in ZqnZ_q^n as well. They also have associated error distributions e,e’e, e’ respectively.
    • AA sends uT=rTM+eTu^T = r^T M + e^T and BB sends v=Ms+ev = Ms + e
    • AA computes rTv=rT(As+e’)≈rTAsr^Tv = r^T(As + e’) \approx r^T As
    • BB computes uTs=(rA+eT)s≈rTAsu^T s = (rA + e^T) s \approx r^T As
    • To avoid the small chance of error, A,BA, B choose the first mm 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 uT,vu^T, v 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 0K0K - 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.

Type to search the whole site.