4
$\begingroup$

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)$$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$
6
  • $\begingroup$ So, for example, one can modify the collection of samples like $A \gets GL_{n}(\mathbb{Z}_{q})$, right? $\endgroup$
    – Blanco
    Commented Dec 15, 2019 at 9:32
  • $\begingroup$ 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). $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Dec 15, 2019 at 18:01
  • $\begingroup$ 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. $\endgroup$
    – Blanco
    Commented Jan 2, 2020 at 6:29
  • $\begingroup$ 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 ... $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Jan 2, 2020 at 7:11
  • $\begingroup$ 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. $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Jan 2, 2020 at 7:15

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.