Cryptography
homomorphic-encryption lattice-crypto trapdoor
Updated Sun, 26 Jun 2022 17:46:14 GMT

# Proving LWE inversion in Micciancio-Peikert-2012 lattice trapdoors

I'm looking through the lattice trapdoor construction in https://eprint.iacr.org/2011/501.

To summarize, assume we have a matrix $$G$$ where, on input $$b$$, we can efficiently find $$(s,e)$$ such that $$s^TG+e^T=b^T$$. Then for an invertible $$H$$, and a random $$\overline{A}$$, we produce a matrix $$A$$ by $$A = [\overline{A} | HG - \overline{A}R]$$ for some random $$R$$. This has the property that $$A\begin{pmatrix} R\\ I\end{pmatrix} = HG$$.

Then the LWE inversion for $$A$$ is given as follows: We start with some $$b$$. We first compute $$\hat{b}^T = b^T\begin{pmatrix} R\\ I\end{pmatrix}$$. Then we find $$(\hat{s},\hat{e})$$ such that $$\hat{s}^TG+\hat{e}^T=\hat{b}T$$. Then we let $$s^T = \hat{s}^TH^{-1}$$ and $$e^T = b^T - s^TA$$ be the LWE sample $$(s,e)$$ satisfying $$s^TA+e^T = b^T$$ with $$e$$ small.

It's clear to me that by the definition of $$e^T$$, $$s^TA+e^T=b^T$$ holds. In fact that would work for any $$s$$. So the hard part is to show that $$e$$ is small, and that's what I can't figure out.

One thing I can show is that \begin{align} e^T\begin{pmatrix} R \\ I\end{pmatrix} = & b^T\begin{pmatrix} R \\ I \end{pmatrix} - s^TA\begin{pmatrix} R \\ I\end{pmatrix}\\ = & \hat{b}^T - \hat{s}^TH^{-1}HG\\ =& \hat{b}^T - \hat{s}^TG\\ = & \hat{b}^T - \hat{b}^T + \hat{e}^T\\ = & \hat{e}^T \end{align}

So if $$R$$ were invertible and diagonalizable, I could argue that $$e^T$$ must be small in terms of the smallest singular value of $$R$$ and the size of $$\hat{e}^T$$. However, that doesn't seem to be the approach of the paper, which focuses instead on the largest singular value of $$R$$. Their proof of Theorem 5.4 doesn't make sense to me: I don't understand what they are trying to prove, and why they are not showing that $$e$$ is small.

## Solution

We are given some $$b^t = s^t A + e^t$$ for $$A$$ of the above form and short $$e$$, and wish to recover $$s$$ (which will immediately give us $$e$$ as well). If $$e$$ is short enough, then $$\hat{b}^t = (s^t H) G + \hat{e}$$ for some sufficiently short $$\hat{e}$$. (This is where we use the bound on the expansion, or top singular value, of $$R$$.) Therefore, the LWE inverter for $$G$$ will recover $$s^t H$$ (and $$\hat{e}$$), from which the original $$s$$ can be recovered via $$H^{-1}$$.

Its very important that $$e$$ is short enough to ensure that $$\hat{e}$$ is short enough. If the latter is too long, then the LWE inverter for $$G$$ might return the wrong answer for $$s^t H$$, leading to a wrong $$s$$ and thereby a wrong, probably very long $$e$$.