LWE with identity sub-matrix and reused sampled from [MP12]: why is it secure?

Question

I studied this paper a while ago, but now I'm confused by the paper Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller by Micciancio and Peikert. Page 24 and 25, they present an algorithm that explains how to sample a pseudo random matrix $\mathbf{A}$ with a trapdoor.

Short presentation of this section

Basically, the idea is to sample first a matrix $\mathbf{A}$ uniformly at random, sample a matrix $\mathbf{R}$ according to some distribution $\mathcal{D}$, and then compute $\mathbf{A} = [\bar{\mathbf{A}} | \mathbf{G} - \bar{\mathbf{A}}\mathbf{R}]$ where $\mathbf{G}$ is a fixed matrix easy to invert even in the presence of noise (and I don't need the tag $\mathbf{H}$, so $\mathbf{H} = \mathbf{I}$). They, if I understood correctly, they say that $\mathbf{A}$ looks random if $[\bar{\mathbf{A}} | \bar{\mathbf{A}}\mathbf{R}]$ looks random, which makes sense, especially when we removed the tag. So from that point $\mathbf{G}$ is not useful anymore to study the indistinguishability property.

Then, they present two ways to sample $\mathbf{R}$ and choose the dimensions of $\mathbf{A}$, depending on whether you want statistical or computational indistinguishability for $\mathbf{A}$. However, the computational version looks a bit strange to me: instead of sampling $\bar{\mathbf{A}}$ uniformly at random, they seem to sample instead another matrix $\hat{\mathbf{A}} \in \mathbb{Z}_q^{n \times n}$ uniformly at random, and set $\bar{\mathbf{A}} = [\mathbf{I} | \hat{\mathbf{A}}]$. They also sample $\mathbf{R} = \begin{bmatrix}\mathbf{R}_1\\\mathbf{R}_2\end{bmatrix}$ according to a discrete Gaussian. Then it means that $[\bar{\mathbf{A}} | \bar{\mathbf{A}}\mathbf{R}] = [\mathbf{I}|\hat{\mathbf{A}}|\hat{\mathbf{A}}\mathbf{R}_2+\mathbf{R}_1]$. And they say this matrix (up to the identity) is indistinguishable from random because it is an instance of LWE in its normal form.

My (maybe elementary?) questions

So I have two questions:

• First, why isn't it a problem to have a matrix identity in the final matrix $\mathbf{A}$? I have the feeling that it leaks much more information about the secret $\mathbf{s}$, since you learn basically $\mathbf{s}^t\mathbf{I}+\mathbf{e}^t = \mathbf{s}^t+\mathbf{e}^t$ for some small error $\mathbf{e}$. In particular, you learn the most significant bits of $\mathbf{s}$ right? I don't see how you could learn this same information from $\mathbf{s}^t\mathbf{A}+\mathbf{e}^t$ when $\mathbf{A}$ is truly random. I guess you can try to do some columns operations to recover the identity, but I would expect this to increase the noise significantly.
• Secondly, why is $[\hat{\mathbf{A}}|\hat{\mathbf{A}}\mathbf{R}_2+\mathbf{R}_1]$ even pseudo-random? The way I understand the normal form of LWE is that you are allowed to sample $\mathbf{s}$ directly from a small Gaussian instead of uniformly at random as explained here slide 10/15. So I would agree that $[\hat{\mathbf{A}}|\hat{\mathbf{A}}\mathbf{R}_2+\mathbf{R}_1]$ is pseudo random if $\mathbf{R}$ was a vector. However, $\mathbf{R}$ is a matrix, so it means that each line of $\hat{\mathbf{A}}$ will be used to produce several samples (one for each column or $\mathbf{R}$). So it suggests that LWE is secure also if we reuse the $\mathbf{a}$ samples several times... Am I right or did I miss something? If yes, do we know that LWE is secure when these samples are reused several times?

Thanks!

EDIT: answer to Mark

Thanks for your answer. Thank you very much for the [PW07] reference: Lemma 6.2 is exactly what I need: it is very helpful and answers perfectly my second question! (+1)

Concerning the first question, I did try to read the relevant section of [MR09] (the important part is at the very end and a bit in the beginning). However, it still looks a bit cryptic to me. I guess maybe because I'm not yet used to this link between the matrix and the lattice. And I still don't understand if I can use $\mathbf{A}$ "as it" (strange due to the "attack" I mention), or if I need some special care when using it, like sampling $s$ from a small error set (also strange not to mention it at all in the paper: later $g_{\mathbf{A}}$ is defined on all $s$), or if I can just get rid of the identity and use the rest (but then I'm not sure the correctness applies).

Concerning the reference [MR09], for example, I'm not sure how they derive page 24 the expression for $P'$. Just to make sure, when they say "Reducing the columns of E modulo the HNF", they mean some sort of LLL reduction? And after that line, the rest is quite specific to there own strange construction and I'm not sure what I can say from that. I've the feeling that this Hermitian matrix is just a convenient, efficient, representation of A in the lattice space, but that using this matrix instead of A requires some adaptation (maybe, as you say, to sample using a small $s$ instead of a uniform element, which may be the case of the [MR09] paper because they use an $a$ sampled uniformly between $-r$ and $r$... and I've the feeling that they also need to update their way of sampling $E$, by doing this reduction first). So if I need to adapt my method to use $\mathbf{A}$, then I'm surprised they don't mention it in the paper, and just define $g_\mathbf{A}$ for all $s$.

Any clarification would be greatly appreciated, thanks a lot!

Answer 1

As a quick aside, while Hermite refers to the same person, "Hermitian" means something different for matrices than "Hermite Normal Form". HNF is essentially "Row Echelon Form/Gaussian Elimination where you can't divide".

---

HNF Optimization:

First, we can discuss "Reducing the columns of $E$ modulo the HNF", which does not mean running LLL reduction or something. [MR2009] implicitly defines this notation on page 15:

In [47] it is proposed to select the vector $v$ such that all the coordinates of $(r+v)$ are reduced modulo the corresponding element along the diagonal of the HNF public basis $H$. The vector $(r+v)$ resulting from such a process is denoted $r\mod H$, and it provably makes cryptanalysis hardest because $r\mod H$ can be efficiently computed from any vector of the form $(r+v)$ with $v\in \mathcal{L}(B)$. So, any attack on $r\mod H$ can be easily adapted to work on any vector of the form $r+v$ by first computing $(r+v) \mod H=r\mod H$. Notice that $r\mod H$ can be computed directly from $r$ and $H$ (without explicitly computing $v$) by iteratively subtracting multiples of the columns of $H$ from $r$. Column $h_{i}$ is used to reduce the $i$th element of $r$ modulo $h_{i,i}$.

This is fairly typical for what "reducing mod a lattice means". Any lattice partitions space into the union of translates a (non-unique) "fundamental domain" by lattice points. Reducing mod a lattice roughly means (for some fundamental domain) shifting a point in space by lattice points (which preserves the relative position in the fundamental domain) until one gets to the fundamental domain associated with 0. If you have a CVP oracle, these fundamental domains are Voronoi cells, but there are efficient algorithms for "worse" fundamental domains (one is described on page 25 of [MR2009] if you are interested).

This is to say that "reducing mod a lattice" shifts by lattice vectors until you are near the origin while maintaining your relative position within some tiling of space. This is best demonstrated by reduction mod $q$, which has a natural interpretation of reducing mod the lattice $q\mathbb{Z}^n$. The fundamental domain here is $[-q/2, q/2)^n$ (which is the Voronoi cell of the cubic lattice $q\mathbb{Z}^n$), and it maps you from some arbitrary point in space $x = q\vec{y} + e$, where $q\vec{y}\in q\mathbb{Z}^n, e \in[-q/2, q/2)^n$ to $e\in [-q/2, q/2)^n$, where the "relative position being preserved" means that the part of $x$ in the fundamental domain ($e$) is not changed. Note that for an arbitrary point in space $x$, the "$e$ part" is uniquely determined (as the lattice partitions the space into translates of the fundamental domain), so preserving the $e$ part is meaningful.

Returning to page 24, start by considering the public key:

$$[\mathbf{A}, \mathbf{A}\mathbf{S} + \mathbf{E}]$$

The idea behind the HNF optimization is two-fold:

1. Replace $\mathbf{A}$ with a "succinct" description of the lattice that $\mathbf{S}$ is encoded under

2. Reduce $\mathbf{AS} + \mathbf{E}$ mod the lattice to force $\mathbf{AS} + \mathbf{E}$ to be contained in some "smaller" space, while "preserving the $\mathbf{E}$ part"

Both use the HNF in a key way. Consider the HNF of the basis of the lattice $\Lambda_q(\mathbf{A}^t)$ again. This can be computed by column-reducing a generating set for the lattice $\Lambda_q(\mathbf{A}^t) = \mathcal{L}(\mathbf{A}) + q\mathbb{Z}^n$, which is given by $[\mathbf{A}, q\mathbf{I}]$. Under the "standard assumptions" on $\mathbf{A}$ (which are listed on the bottom of page 23), this yields a basis of the form:

$$\mathbf{H} = \begin{pmatrix}\mathbf{I} & \mathbf{0}\\ \mathbf{A}' & q\mathbf{I}\end{pmatrix}$$

Note that changing to this basis does not require modifying our public key in some way. If $\mathbf{A} = \mathbf{H}\mathbf{U}$ is our expression of the HNF $\mathbf{H}$ in terms of the initial basis and a unimodular matrix, then we simplistically have that:

$$[\mathbf{H}\mathbf{U}, \mathbf{H}\mathbf{U}\mathbf{S} + \mathbf{E}]$$

But $\mathbf{H}$ and $\mathbf{H}\mathbf{U}$ both generate the same lattice, so we can freely replace $\mathbf{H}\mathbf{U}$ with $\mathbf{H}$. I will next write $\mathbf{P} = \mathbf{U}\mathbf{S}$, which is uniformly random iff $\mathbf{S}$ is ($\mathbf{U}$ is invertible). We therefore have that the public key is of the form:

$$[\mathbf{H}, \mathbf{H}\mathbf{P} + \mathbf{E}]$$

Examine this second part of the equation now:

$$\mathbf{H}\mathbf{P} + \mathbf{E} = \begin{pmatrix} \mathbf{I} & \mathbf{0} \\ \mathbf{A}' & q\mathbf{I}\end{pmatrix}\begin{pmatrix}\mathbf{P}''\\\mathbf{P}'\end{pmatrix} + \begin{pmatrix}\mathbf{E}'' \\ \mathbf{E}'\end{pmatrix}$$

One can do block-matrix multiplication to get the two equations:

$$\begin{pmatrix}\mathbf{P}'' + \mathbf{E}'' \\ \mathbf{A}'\mathbf{P}'' + q\mathbf{P}' + \mathbf{E}'\end{pmatrix}$$

The idea here will be to reduce mod the lattice to zero out the "top" part of the last equation. If you look at the form of $\mathbf{H}$, this can easily be done without knowing $\mathbf{P}''$ or $\mathbf{E}''$ (the relevant section of $\mathbf{H}$ contains an identity matrix, add columns from that until it is zero).

As I mentioned though, this kind of technique changes the particular lattice point that is being encoded. As $\mathbf{P}'' + \mathbf{E}'' = 0$, when we zero it out we will have that the encoded point $\mathbf{P}'' = -\mathbf{E}''$ now, yielding the equation:

$$\begin{pmatrix}-\mathbf{E}'' + \mathbf{E}'' \\ -\mathbf{A}'\mathbf{E}'' + q\mathbf{P}' + \mathbf{E}'\end{pmatrix} = \begin{pmatrix}\mathbf{0} \\ -\mathbf{A}'\mathbf{E}'' + q\mathbf{P}' + \mathbf{E}'\end{pmatrix}$$ Considered $\bmod q$, this lets one write the public key as:

$$\left[\begin{pmatrix}\mathbf{I} & \mathbf{0}\\ \mathbf{A}' & q\mathbf{I}\end{pmatrix}, \begin{pmatrix}\mathbf{0} \\ -\mathbf{A}'\mathbf{E}'' + \mathbf{E}'\end{pmatrix}\right]$$

This is easily compressible to the pair $[\mathbf{A}', -\mathbf{A}'\mathbf{E}'' + \mathbf{E}']$, which is where one gets the efficiency gain. Also note that if one can break this LWE instance, they can break LWE. Consider search LWE for simplicity --- breaking it here lets you recover $\mathbf{E}', \mathbf{E}''$, which is the entirety of $\mathbf{E}$ in the initial LWE instance. From that you can reduce $[\mathbf{A}, \mathbf{AS} + \mathbf{E}]\mapsto [\mathbf{A}, \mathbf{AS}]$, which is trivially breakable. This technique can also be used to reduce LWE with Uniform errors to LWE with Gaussian errors. I think if one truly wants uniform errors you could re-randomize this by adding $-\mathbf{A}'\mathbf{U}'$ for uniform $\mathbf{U}'$, but have not thought through this much (also Gaussian errors will be "shorter" on average, so up to issues with sampling discrete Gaussians they often lead to slower error growth).

---

Reusing a Random Matrix:

You can reuse the random pad. Reusing it $\ell$ times roughly gives adversaries an $\ell$ times greater advantage by a simple hybrid argument. So if $\ell$ is polynomially-sized (which is the largest it can be for honest parties to be able to compute on it) everything is fine. Details can be found in section 6.2 of PW2007. This is what is referred to on slide 8 of the linked slides as well by "multiple secrets" (if you collect the multiple secrets into a matrix, it is precisely your situation). Note that one of course must reuse $\mathbf{A}$ with independent keys.