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.


1 Answer 1


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}$.

It’s 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.