Computational LWE-Trapdoor without tag In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller, Micciancio and Peikert mention that it is possible to save an additive $n$ term in the dimension $\bar{m}$  in paragraph $\textbf{Further optimizations}$ in section 5.2 if we use a single tag $H=I$. I want to use this together with the computational instantiation but I do not get how to reduce this case to the LWE-problem here.

We can obtain a gadget-matrix $G' = \left[ I \  | \ \tilde{G} \right]$ with an identity submatrix by a unitary transformation $G' = G \cdot U$ where $G$ is the gadget-matrix mentioned in the paper. Thus, $S' = U ^{-1}S$ is an adequate basis for $G'$ where $S$ is the basis from the paper.
Next, we let $\bar{A} =  \hat{A} \xleftarrow{$} \mathbb{Z}_q^{n \times n}$ and $R \xleftarrow{} D$ be random and then we obtain a &quot;tuple&quot; $\left[ \bar{A} \ | \ 0 \right] T^{-1} = \left[ \bar{A} | -\bar{A}R  \right]$ or the parity-check matrix
$A = \left[ \hat{A} \ | \ G' - \hat{A}R \right]$. But in this case I don't how to use this as an instance of decision-LWE.
Here is the optimization in more detail. Start with $[\bar{A} \mid I_n \mid G']$ where $\bar{A} \in \mathbb{Z}_q^{n \times n}$ and $G = [I_n \mid G']$ (where $I_n$ is the $n$-by-$n$ identity matrix).
Note that the concrete gadget matrices $G$ constructed in the paper already contain an identity submatrix (up to reordering of columns). But in general, $G$ will have an invertible $n$-by-$n$ submatrix $K$, which we can move to the leftmost columns, and then replace $G$ with $K^{-1} G = [I_n \mid G']$. This is just as good of a gadget matrix as the original $G$, because it has the same kernel lattice $\Lambda^\perp(G)$ (up to permutation of coordinates).
Now we can build a public matrix $A = [\bar{A} \mid I_n \mid G' - (\bar{A} R_2 + R_1)]$ for secret short $R_1, R_2$ whose entries are drawn from $\mathcal{D}$, which will serve as the trapdoor. (In fact we really only need to store $R_2$; see below.)
The $[\bar{A} \mid \bar{A}R_2 + R_1]$ part is an LWE instance and hence pseudorandom by assumption, so $A$ is indistinguishable from uniform (apart from its $I_n$ submatrix). We also have $$ A \begin{pmatrix} 0 &amp; R_2 \\ I_n &amp; R_1 \\ 0 &amp; I \end{pmatrix} = [I_n \mid G'] = G, $$ which is the desired &quot;trapdoor&quot; relation. (Of course we can treat the $0$ and $I$ submatrices in that block matrix as implicit.)
We are basically done, but note that LWE instances constructed from $A$ should ignore its $I_n$ submatrix (see also this question and my comment); let's make this explicit. By dropping the $I_n$ submatrix from $A$ we get $A' = [\bar{A} \mid G' - (\bar{A}R_2 + R_1)]$ and $$ A' \begin{pmatrix} R_2 \\ I \end{pmatrix} = G' - R_1 .$$ This is a good enough approximation to the trapdoor relation when we use only &quot;short&quot; LWE secrets $s$ and the identity tag: given $b^t = s^t A' + e^t$ for sufficiently short $s,e$, we can use the trapdoor $R_2$ to compute $$ b^t \begin{pmatrix} R_2 \\ I \end{pmatrix} = (s^t A' + e^t) \begin{pmatrix} R_2 \\ I \end{pmatrix} = s^t (G' - R_1) + e^t \begin{pmatrix} R_2 \\ I \end{pmatrix} \approx s^t G',$$ from which we can recover $s$ and then $e$.
Importantly, the &quot;most-significant bits&quot; of the entries of $s$ are zero because $s$ is short, so to recover $s$ from the &quot;noisy&quot; $s^t G'$, we don't need the &quot;noisy&quot; $s^t I_n$ subvector that is now missing due to omitting $I_n$ from $G$. If we were to use a non-identity invertible tag $H$, then we would need to recover $s$ from a noisy $(s^t H)G'$, which is trickier because $s^t H$ can have &quot;large&quot; entries. It's not clear to me whether this can be done efficiently in general.