# Is there an adaptive version of LWE assumption with respect to some potentially non-uniform secret distribution?

There is a version of LWE assumption as follow.

Assume that there is a positive number $$n$$, an integer $$q = q(n) \geq 2$$, an error distribution $$\chi = \chi_{n}$$, a vector $$\mathrm{\mathbf{s}} \gets \mathbb{Z}_{q}^{n}$$ and for every efficient algorithm $$\mathcal{A}$$, $$\Pr \left[ A \gets \mathbb{Z}_{q}^{m \times n}, \mathrm{\mathbf{e}} \gets \chi^m,~ \mathrm{\mathbf{b}} \gets A \cdot \mathrm{\mathbf{s}} + \mathrm{\mathbf{e}}: \mathcal{A}(A, \mathrm{\mathbf{b}}) = s \right] \leq \mathrm{nelg}(n)$$

Q1: Why does it say $$m = O(n \log q)$$ in some schemes? I do not find some notes about the range of $$m$$. I think $$m = \mathrm{poly}(n \log q)$$ is OK.

Q2: Is there an adaptive version? Is it still hard to solve?

For example, Let oracle $$\mathcal{O}_{\mathrm{\mathbf{s}}}$$ satisfy that $$\mathcal{O}_{\mathrm{\mathbf{s}}}(\mathrm{\mathbf{a}}) = (\mathrm{\mathbf{a}}, \langle \mathrm{\mathbf{a}}, \mathrm{\mathbf{s}} \rangle + e)$$, where $$e \gets \chi$$. And for every efficient algorithm $$\mathcal{A}$$, $$\Pr \left[ \mathcal{A}^{\mathcal{O}_{\mathrm{\mathbf{s}}}}(1^n) = s \right] \leq \mathrm{nelg}(n)$$ The algorithm $$\mathcal{A}$$ is allowed to ask the access of $$\mathcal{O}_{\mathrm{\mathbf{s}}}$$ for at most $$m$$ times.

Q3: If there are $$l$$ secret vectors and $$S = [\mathrm{\mathbf{s}}_{1}, \mathrm{\mathbf{s}}_{2}, \ldots, \mathrm{\mathbf{s}}_{l}]$$. Is there a version of LWE with respect to some potentially non-uniform secret distribution? (e.g., $$S$$ belongs to the general linear group $$GL_{n}(q)$$ or the orthogonal group $$S \in O_{n}(q)$$)

It means that for every efficient algorithm $$\mathcal{A}$$, $$\Pr \left[ \mathcal{A}^{ \mathcal{O}_{\mathrm{\mathbf{s}}_{1}}, \mathcal{O}_{\mathrm{\mathbf{s}}_{2}}, \ldots, \mathcal{O}_{\mathrm{\mathbf{s}}_{l}} } (1^{nl}) = S \right] \leq \mathrm{nelg}(nl)$$

For Q1, $$m = O(n\log q)$$ is the size required for the leftover hash lemma to kick in and $$Ax$$ to be statistically close to uniform (I believe). See questions like this one.
For Q2, the answer is yes. The hardness of LWE is essentially independent of the dimension $$m$$, as you can generate new LWE samples from a fixed collection of samples with only a mild loss in the error term. See proposition 2.1 of Regev's survey (and the "other implications" discussion after the proof).
• So, for example, one can modify the collection of samples like $A \gets GL_{n}(\mathbb{Z}_{q})$, right? – TeamBright Dec 15 '19 at 9:32
• It would be simpler to rejection sample until this occurs. Fortunately it occurs with quite high probability --- the size of $\mathsf{GL}_n(\mathbb{Z}_q)$ is $\prod_{k = 0}^{n-1}(q^n -q^k)$, so the proportion of random matricies which are invertible ends up being quite large (You can get the lower bound $|\mathsf{GL}_n(\mathbb{Z}_q)| = q^{n^2}(1 - \frac{1}{q-1})$ pretty easily, see for example lemma 4 although the computation is routine and may be found eleswhere). – Mark Dec 15 '19 at 18:01
• One more question, if there is a group of secret vectrors $S = \{s_{1}, s_{2}, \ldots, s_{l} \}$. Does $\Pr [ \mathcal{A}^{\mathcal{O}_{s_1}, \ldots, \mathcal{O}_{s_l}}(1^{nl}) = S ] \leq \mathrm{nelg}(nl)$ hold true? even $s_{i}, s_{j}$ may be not independent. – TeamBright Jan 2 '20 at 6:29
• One can probably try to bound this quantity by realizing all $s_i$ as projections of some fixed $s$. Say that $s = \mathsf{concat}(s_1,\dots,s_\ell)\in\mathbb{Z}_k^{n\ell}$, and define projections $\pi_1,\dots,\pi_\ell$ such that $\pi_i(s) = s_i$. Then one should be able to simulate the oracles $\mathcal{O}_{s_1},\dots,\mathcal{O}_{s_\ell}$ with an oracle to $\mathcal{O}_s$, which is just an oracle for the (standard) LWE problem on $\mathbb{Z}_q^{n\ell}$, although if $s_i$ and $s_j$ are dependent then $s$ will not be drawn from the uniform distribution on $\mathbb{Z}_q^{n\ell}$. Still this ... – Mark Jan 2 '20 at 7:11
• Should let you recast your problem as investigating (standard) LWE with respect to some potentially non-uniform secret distribution. I doubt you can get an upper bound of the form $\mathsf{negl}(n\ell)$ in general (consider the case where $s_1 = s_2 = \dots = s_\ell$), but you might hope some bound in terms of the min-entropy of $s$ to hold. This paper's abstract makes it seem like this hope is false (in the case of R-LWE at least), but whatever your particular question is probably warrants a new question. – Mark Jan 2 '20 at 7:15