Score:0

Is $0/1$ error ok in LWE?

ru flag

Can the error in LWE or ringLWE schemes be from $\{0,1\}$? If not why and what is the best attack in this case?

Score:2
ru flag

I can't see a reason a priori why one would not be able to construct a (R)LWE scheme where errors are drawn from a $\{0,1\}$ set, but this does not mean that it easy to write a secure version of this. One certainly should not take an existing (R)LWE scheme, switch out the error distribution and expect it to have similar security and correctness properties. Existing tooling for estimating the security of lattice-based schemes may be able to cope with schemes, but finding the best attack for any given combination of dimension, modulus and error rate is likely to be a big search.

Some properties of the the underlying lattice problems that would be affected by such a distribution include a change in the entropy of error vectors (the maximum entropy definitely becomes smaller and other entropy measure almost certainly decrease as well). One would need to be sure that the dimension was large enough that the minimum entropy of the error distribution is greater than the security parameter in order to defeat naive guessing. There also could be gains in exploiting the off-centre distribution of the error for close vector problem purposes. In centred LWE problems with small solutions, one can solve by considering the lattice generate by the rows of the matrix $$\begin{pmatrix}I&A\\ 0&qI\end{pmatrix}$$ and looking for a vector close to $(\mathbf 0^T|\mathbf b^T)$ where the entries in the difference vectors are drawn from the error distribution. In an off-centred system, there may be a small advantage in instead looking for a vector close to $ \mathbf\delta^T|(\mathbf b+\mathbf\delta)^T)$ where $\delta$ is a centering vector so that entries f the difference vector have a tighter distribution.

There may of course be other effects.

Turbo avatar
ru flag
How about for secret? Can it also be from $\{0,1\}$?
Daniel S avatar
ru flag
@Turbo again I cannot think of a reason why one could not construct such a scheme, but the security assessment process is complex and arcane.
Score:2
ng flag

The security of $\{0,1\}$ error LWE depends heavily on the number of samples you get access to. By this, for a standard "LWE sample"

$$(A, As + e)$$

where $A\in\mathbb{Z}_q^{m\times n}$, $s\in\mathbb{Z}_q^n$, $e\in\mathbb{Z}_q^m$, I mean the parameter $m$.

This heavy dependence is because for $m = \Omega(n^2)$ there are polynomial-time attacks, i.e. it is completely insecure. Alternatively, things are thought to be ok for $m = O(n)$. From this, we see that

(Heuristically) for any $\epsilon > 0$, binary error LWE can be solved in polynomial time $n^{O(1/\epsilon)}$ given $\epsilon\cdot n^2$ samples, and for $0 < \alpha < 1$ it can be solved in sub-exponential time $2^{O(n^{1-\alpha})}$ time given $n^{1+\alpha}$ samples.

This is for algebraically unstructured LWE. For algebraically structured LWE, weaker results are known (see this, though I will not summarize it here as it is quite technical).

You also asked about choosing the secret from $\{0,1\}$. This is much better supported theoretically, though there are some caveats

  • For (plain) LWE (i.e. algebraically unstructured), there is no security loss provided you increase the dimension to componsate, i.e. use dimension $n\log_2 q$ rather than dimension $n$
  • For algebraically structured LWE, there is plausibly a security loss. Still, using ternary secrets $\{-1,0,1\}$ is quite common, and was standardized in the Homomorphic Encryption standard (binary secrets were not).
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.