3
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.