Proving LWE inversion in Micciancio-Peikert-2012 lattice trapdoors

Question

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.

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