1
$\begingroup$

Consider the LWE distribution $\{(\pmb{a}_{i},\left<\pmb{a}_{i} , \pmb{s}\right> + e_{i})\}$ where secret $\pmb{s} \in \mathbb{Z}_{q}^{n}$, randomness is $\pmb{a}_{i} \xleftarrow{\$} \mathbb{Z}_{q}^{n}, e_{i} \xleftarrow{\$} \chi$, $q$ is a prime number and $\chi$ is a discrete Gaussian distribution. Grouping $m$ samples we obtain $(\pmb{A},\pmb{A}\pmb{s}+\pmb{e}) \in \mathbb{Z}_{q}^{m \times n}\times \mathbb{Z}_{q}^{m}$.

We can wonder if the (search) Learning With Errors problem has more than one solution (with bounded error terms). We can compute the probability over the choices of $\pmb{a}_{i}$ of the existance of another $\pmb{s}' \neq \pmb{s}$ such that $\pmb{A}(\pmb{s}-\pmb{s}') = \pmb{e}'-\pmb{e}$ has small norm. If we just want to bound the infinity norm it is easy compute this probability for a particular $\pmb{s}'$ and then do a union bound over all possible $\pmb{s}'$. As a result we get that $m\in\mathcal{O}(n)$ is enough to ensure that the problem has a unique solution except with negligible probability in $n$.

I have also read that Chernoff's bounds could be used to analize these probabilities.

Consider now the ring-LWE distribution, $\{(a_{i},a_{i} \cdot s+e_{i})\}$, where $s \in R_{q} = \mathbb{Z}_{q}[x]/\left<x^n+1\right>$, $a_{i} \xleftarrow{\$} R_{q}$ and $e_{i}\in R_{q}$ is obtained sampling its coefficients from $\chi$.

Since we can think of each ring-LWE sample as $n$ LWE samples I would expect only a constant number of samples to ensure that the problem of recovering $s$ has a unique solution with overwhelming probability. However I do not know how to prove it, since now I cannot use that each $\pmb{a}_i$ was independent, and $R_{q}$ can have divisors of zero.

Is there a general way of obtaining the number of samples required for this condition? Or general applications only require that the problem is hard but never require uniqueness?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.