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.

enter image description 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.


1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$
    – kibuff
    Mar 1, 2021 at 10:25
  • $\begingroup$ 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. $\endgroup$ Mar 1, 2021 at 13:53

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.