Fun paper time! Often, we only think about theoretical security guarantees of cryptosystems. For example, Kyber512 offers approximately the same security as AES128. However, in practice with leakage the security can often drop.
Current state of the art theoretical estimates are predicted using the LWE Estimator. However, in a concrete setting, decryption failures and fault attacks can leak some information about our cryptosystem. In this post I will discuss the revolutionary method used by [DDGR20] and [DGHK22] to integrate this extra information into security estimation, provided in the leaky LWE estimator.
Background: Lattices
Lattices are a discrete additive subgroup spanned by a set of independent basis vectors. A lattice $\mathcal{L}(\bm{B})$ is the set of all integer linear combinations of those basis vectors.
Definition (Lattice). A lattice $\mathcal{L}(\bm{B})$ is defined as the set of points
$$\mathcal{L}(\bm{B}) = \left\{ \sum_{i=1}^{k} z_i\bm{b}_i : z_i \in \mathbb{Z} \right\} $$
Note that multiple bases can span the same lattice.
Theorem. Two bases $\bm{B}_1, \bm{B}_2$ span the same lattice if and only if $\bm{B}_1 = \bm{B}_2\bm{U}$, such that $|\det \bm{U} | = 1$ and $\bm{U}$ contains only integers.
Definition (Volume). The volume of a lattice spanned by a basis $\bm{B}$ is given by $$\sqrt{\bm{B}^T\bm{B}}$$
The volume of a lattice is independent of the choice of basis for our lattice. We see this as $$ \sqrt{\det\left(\bm{B}_2^T\bm{B}_2\right)} = \sqrt{\det\left(\bm{U}^T\bm{B}_1^T\bm{B}_1\bm{U}\right)} = \sqrt{\det\left(\bm{B}_1^T\bm{B}_1\right)} $$
One important property of lattices for cryptography is the difficulty of the Shortest Vector Problem. Given a lattice spanned by an arbitrary basis, the goal is to find the shortest nonzero vector. State of the art SVP solvers involve an algorithm known as BKZ, which has a parameter $\beta$ known as the blocksize. Larger lattices require a higher $\beta$ to solve, and BKZ runs exponentially in $\beta$.
Importantly, we can predict the blocksize of BKZ to find the shortest vector using just the volume of a lattice and its dimension.
Learning with Errors
Current post quantum cryptosystems rely on the Learning with Errors hardness assumption. Both Kyber and Dilithium, which are NIST finalists in the post quantum competition, use (variants) of this standard assumption.
Definition (Learning with Errors).
Let $n, m$ be positive integers, and let $q$ be a prime. Let $\chi$ be a short distribution over $\mathbb{Z}_q$. The Search LWE problem is:
Given the pair $\left(\bm{A} \in \mathbb{Z}^{m\times n}_q, \bm{b} = \bm{s}\bm{A}^T + \bm{e} \in \mathbb{Z}^m_q\right)$ such that
- $\bm{A}$ is sampled uniformly at random,
- $\bm{s}$ is sampled from $\chi^n$ and $\bm{e}$ is sampled from $\chi^m$,
Find $\bm{s}$.
In essence, what this problem is stating is to find a vector given some product with some small amount of noise added to it. This has been used to build a multitude of cryptographic protocols, including signatures, public key cryptography, fully homomorphic encryption, and more.
Importantly, note that a Learning with Errors instance can be reduced to an instance of the Shortest Vector Problem.
Definition (Kannan's Embedding).
Let $(\bm{A}, \bm{b})$ be an LWE instance with parameters $n, m, q, \chi$. Then solving the Shortest Vector Problem for the lattice spanned by the following basis solves the LWE instance. $$ \begin{bmatrix} -\bm{A}^T & \bm{0} \\ \bm{b} & M \end{bmatrix} $$
Note that
$$ \begin{bmatrix} \bm{s} & 0 \end{bmatrix} \begin{bmatrix} -\bm{A}^T & \bm{0} \\ \bm{b} & M \end{bmatrix} = \begin{bmatrix} \bm{e} & 0 \end{bmatrix} $$
Therefore, $(\bm{e}, 0)$ is a short vector in this lattice, and so we can solve for $\bm{e}$ using BKZ, which allows us to solve the LWE instance.
Using this, we can predict the hardness of specific LWE instances by using the volume and dimension to predict BKZ runtime for our specific lattice.
Integrating Extra Knowledge
Notice however that integrating extra knowledge (for example, approximate information on a coordinate of $\bm{s}$) is not immediately possible with this. However, [DDGR20] and [DGHK22] give a method to add these hints.
The key method is to convert the LWE problem into another intermediate problem. Applying hints to this intermediate problem reduces the hardness of this problem.
Definition (Ellipsoidal Bounded Distance Decoding). Let $\Lambda$ be a lattice, $\bm{\Sigma}$ be an $n\times n$ symmetric matrix, and $\bm{\mu}$ be a vector of length $n$.
Let $E(\bm{\mu}, \bm{\Sigma})$ denote the ellipsoid defined by
$$E(\bm{\mu}, \bm{\Sigma}) := \left\{(\bm{x} \in \text{Span}(\bm{\Sigma}) | (\bm{x} - \bm{\mu})\bm{\Sigma}^{-1}(\bm{x} - \bm{\mu})^T \le 1 \right\}$$
Given $\bm{\mu}, \bm{\Sigma}$, and a basis of $\Lambda$, find the unique vector $\bm{x} \in \Lambda \cap E(\bm{\mu}, \bm{\Sigma})$.
Geometrically, we can think of this as trying to find a single lattice point within some ellipsoidal region of space.
The goal is to find the singular lattice point within this ellipsoidal region which is centered at the value $\bm{\mu}$.
Embedding LWE
Just like how a Learning with Errors instance can be reduced to an instance of the SVP, we can also reduce it to the EBDD problem. The variance of the secret is captured by the ellipsoid matrix (which is why it is $\bm{\Sigma}$).
We can first rewrite the LWE equation to the following: $$ \bm{s}\bm{A}^T + \bm{e} - q\bm{c} = \bm{b} $$
Note that given $\bm{c}$ and $\bm{s}$, we can quite trivially find $\bm{e}$.
Consider the following matrix:
$$ \bm{B} = \begin{bmatrix} q\bm{I}_m & \bm{0} \\ -\bm{A}^T & \bm{I}_n \end{bmatrix} $$
Then we see that $(\bm{c}||\bm{s})\bm{B} + (\bm{b}||\bm{0}) = (\bm{e}||\bm{s})$, where $||$ denotes concatenation. Note that $\bm{e}$ and $\bm{s}$ are short. Therefore, we obtain a statistical bounding: $$ \lVert (\bm{c}||\bm{s})\bm{B} + (\bm{b}||\bm{0})\rVert^2 \le \sigma^2(n + m) $$
where $\sigma$ is the variance of a coefficient drawn from the distribution. Now, this inequality on the norm forms an ellipsoid in our space, defined by the following: $$ \bm{\mu} = -(\bm{b}||\bm{0})\bm{B}^{-1} $$ $$ \bm{\Sigma} = \sigma^2(\bm{B}\bm{B}^T)^{-1} $$
We see that $(\bm{c} || \bm{s})$, and so we have an instance of the EBDD problem. Therefore, we can convert the LWE problem to an EBDD problem.
Solving EBDD
Now note that the ellipsoid is just an affine transformation of a sphere. If we have an EBDD instance, we can then convert it down to a shortest vector problem. Given an EBDD instance $(\Lambda, \bm{\mu}, \bm{\Sigma})$, we can first center the ellipsoid at $\bm{0}$ by doing the following: $$ (\Lambda, \bm{\mu}, \bm{\Sigma}) \mapsto (\Lambda, \bm{0}, \bm{\Sigma} + \bm{\mu}^T \cdot \bm{\mu}) $$
An important note here is that this image is somewhat wrong: the lattice is no longer a lattice if centered at $\bm{0}$. What is really happening here is we have added a dimension so that the lattice remains a lattice. However, the best way to visualize it is to "shift" the ellipse over to the origin.
The next step is to convert our homogenized ellipse into a ball. Since the ellipse is a linear transformation, we can similarly apply the inverse linear transformation on the lattice to convert our ellipse into a ball, while keeping our lattice point inside.
$$ (\Lambda, \bm{0}, \bm{\Sigma}) \mapsto (\Lambda \cdot \sqrt{\bm{\Sigma}}^{-1}, \bm{0}, \sqrt{\bm{\Sigma}}^{-1}\bm{\Sigma}\sqrt{\bm{\Sigma}}^{-1})$$
Now we see that this is just the shortest vector problem, as we are guaranteed a single vector inside this ball at the origin. Therefore, we can apply known techniques such as BKZ to find this shortest vector. The volume of this ball gives us the approximate runtime of solving this SVP problem, and so equivalently the volume of the ellipse gives us an estimate of the security.
Adding Hints: Reducing the volume
Say we have some extra information, for example say we know that $$b \le \bm{s}\cdot\bm{l} \le a$$ for some $\bm{l}, a$, and $b$.
This arises when a decryption failure occurs when using an LWE based cryptosystem.
When converted to the EBDD space, this corresponds to a two sided inequality.
This hint tells us that the lattice point must lie in between these two lines. Therefore, we can take the intersection between this ellipsoid and region to get a new, smaller region.
However, with this smaller region, we no longer have an ellipsoid! Therefore, we need to figure out how to convert this smaller region into an ellipsoid. To do this we can use an algorithm from linear programming to find Lowner-John circumscribing ellipsoid of that region.
Now the volume of the new ellipse is smaller, which provides an easier instance to solve. Therefore, we apply these hints to reduce the hardness of the LWE problem!
So we can now reduce the hardness of the LWE problem if given some hints to it. Along with that, we can easily predict this hardness, by giving a runtime estimate based on the volume of our ellipse. Through this, we can tell how much an LWE problem has degraded based on extra information.
Conclusion
This was a little tour of the toolkits used to estimate the security of current LWE problems with leaks. There is still quite a bit we don't know: Can we make hints commute with each other? Can we batch hint aggregation? Are there ways to incorporate Ring LWE and Module LWE with closed form hint estimation?
In this post I tried to hide most of the math from the paper itself such as the reduction from LWE$\to$EBDD$\to$SVP and the method for updating the ellipses. However, if you would like to learn more about the details, make sure to check out the papers below!