LWE with the matrix A repeated

Question

Consider the following version of Learning With Errors.

You are either given $(A, As_1 + e_1, As_2 + e_2, \ldots, As_k + e_k)$ or $(A, u_1, u_2, \ldots, u_k)$, where

• $A$ is an $m \times n$ matrix whose entries come from the field $\mathbb{Z}_q$ --- the entries are sampled uniformly at random.
• $u_1, u_2, \ldots, u_k$ are $m \times 1$, each of whose entries come from the field $\mathbb{Z}_q$ uniformly at random.
• Each $e_1$, $e_2$, $\ldots$, $e_k$ is an $m \times 1$ Gaussian noise vector.
• Each $s_1, s_2, \ldots, s_k$ is an $n \times 1$ secret string.

You are told to distinguish between these two cases.

Assuming standard LWE is hard, is this problem also hard?

---

In general, a different matrix $A$ is sampled for each LWE sample. Here, we have the same matrix $A$ but $k$ different secrets. Does that change anything about the setting?

Answer 1

You've not fully stated the problem, but I shall assume that it is to distinguish the set constructed from $\mathbf s_k$ values.

In the usual formulation of LWE we are given $m$ samples corresponding to different $n$-long vectors. These could be combined into an $m\times n$ matrix $A$ so that the "standard" LWE decisional problem is to distinguish $(A,A\mathbf s_1+\mathbf e_1)$ from $(A,\mathbf u_1)$.

Given such a problem an adversary could generate their own $\mathbf s_j$, $\mathbf e_j$ and $\mathbf u_k$ for $j=2,\ldots k$ and create two putative instances of your problem by combining the two inputs to decisional LWE with their own inputs i.e. $\{(A,A\mathbf s_1+\mathbf e_1,A\mathbf s_2+\mathbf e_2,\ldots A\mathbf s_K+\mathbf e_k),(A,\mathbf u_1,\ldots,\mathbf u_k)\}$ and $\{(A,A\mathbf s_1+\mathbf e_1,\mathbf u_2,\ldots,\mathbf u_k),(A,\mathbf u_1,A\mathbf s_2+\mathbf e_2,\ldots,A\mathbf s_K+\mathbf e_k)\}$. If there were a method to solve your problem, it should work in the first case to distinguish the set with $\mathbf s_1$ in it thus solving the original decisional LWE. There's a question as to how the solver behaves if given invalid input, but again we should be able to distinguish with advantage.

Answer 2

Yes, it is still hard via a simple hybrid argument. Essentially, for $i\in[k]$ define the "mixed distribution"

$$H_i = (A, A\vec s_1 + \vec e_1,\dots, A\vec s_i + \vec e_i, \vec u_{i+1},\dots, \vec u_k).$$

Then, the problem of distinguishing between $H_i$ and $H_{i+1}$ can be seen to be reducible to the LWE problem. When using this to concretely analyze things, this allows one to bound the advantage of distinguishing between $H_0$ and $H_k$ by $k$ times the advantage of an LWE distinguisher.

This argument (and more generally technique of reusing $A$) dates back to at least Lossy Trapdoor Functions and Their Applications by Peikert and Waters in 2008. It has some mild plausible benefits, namely:

1. one could in principle standardize a single matrix $A$ that all users use (similar to how DDH groups were standardized), or even
2. one could "reuse" a single $A$ over a relatively short, but still non-trivial time period, say 1 hour.

It isn't generally appealed to much anymore though. This is for two main reasons

1. one can get comperable reductions in the size of $A$ by appealing to structured versions of LWE (while improving the efficiency of relevant operations), and
2. in practice one does not often send $A\in\mathbb{Z}_q^{n\times m}$ at the cost of $nm\log_2q$ bits (which is large, leading to one searching for amortization arguments like the one you propose). Instead, you can simply send a "seed" $\{0,1\}^\lambda$, which is expanded into a random matrix $A$ using an extensible output function at the destination. Most NIST PQC candidates use this approach.

It is also worth mentioning that the above idea of a "standardized LWE instance" has a few practical reasons why it is perhaps not smart over long time-scales, namely

1. it opens you up to precomputation attacks (similarly to other DDH-group standardizations, say the LogJam attack), and more importantly

2. one can construct "backdoored LWE instances" --- roughly a distribution of random matrices $A$ that are computationally indistinguishable from random, but have a "trapdoor" that allows one to break LWE.

The backdoored LWE instance is relatively straightforward (I do not remember who to attribute it to unfortunately). Recall that the NTRU assumption generates keys a public key $h$, and secret key $f$, such that $hf = g$ is "small". By using an appropriate "matrix" form of things, we get matrices $H, F$ such that:

• $HF = G$ is small, and
• $H$ is computationally indistinguishable from uniformly random.

Then, if we use $H^t$ as the random matrix of an LWE instance, e.g. get a sample $(H^t, H^t s + E)$, we can easily break the LWE assumption using this random matrix, as $F^t H^t s + F^t E = Gs + F^t E$ is "small" (I believe). This is all with the matrix $H$ being computationally indistinguishable from random under NTRU, e.g. this backdooring of $H$ is hard to detect.