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.

Asked by user32186 (680 )
Sep 04, 2020 at 14:52