# 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 "tuple" $$\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 & R_2 \\ I_n & R_1 \\ 0 & I \end{pmatrix} = [I_n \mid G'] = G,$$ which is the desired "trapdoor" 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 "short" 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 "most-significant bits" of the entries of $$s$$ are zero because $$s$$ is short, so to recover $$s$$ from the "noisy" $$s^t G'$$, we don't need the "noisy" $$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 "large" entries. It's not clear to me whether this can be done efficiently in general.

• Thank you so much for your answer! I've got two follow-up questions for my understanding. 1. Do you mean with "short" $s$ that $s$ is drawn from the error distribution as mentioned both in web.eecs.umich.edu/%7Ecpeikert/pubs/slides-barilan5.pdf, slide 10 and citeseerx.ist.psu.edu/viewdoc/…? And 2., May I still use for my encryption scheme the whole parity-check matrix $A$ as pk and is it still secure or should I drop $I_n$ and use $A'$? I'm not quite sure whether the construction still holds since $A'$ might not be primitive anymore. – kibuff Mar 1 at 10:25
• Q1: Well, the algorithm works for any short enough $s$. But for security, yes, one would typically draw $s$ from the error distribution. Q2: I am not entirely sure what you’re asking. We certainly should not reveal $s^t I_n + e^t$ (for independent $s,e$), because that reveals useful information about $s$. You probably don’t explicitly need $A’$ to be primitive for any functional purpose, since with the trapdoor you can do LWE inversion for it. – Chris Peikert Mar 1 at 13:53