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?


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.