Score:2

Why use small error vectors in LWE instead of big ones?

so flag

In LWE systems, why is it recommended to add only small error vectors to the system of equations and not big error vectors? Can someone come up with an example?

Score:3
ng flag

Bigger errors in LWE make the assumption more secure --- it also makes it harder (and eventually impossible!) to build cryptography from it.

First, recall that the LWE assumption can be phrased as distinguishing samples of the form

$$(\vec a, \langle \vec a, \vec s\rangle + e)\in\mathbb{Z}_q^n\times\mathbb{Z}_q$$

from samples of the form

$$(\vec a, u)\in\mathbb{Z}_q^n\times\mathbb{Z}_q,$$

where

  • $\vec a\in\mathbb{Z}_q^n$ is uniform
  • $\vec s$ is a fixed vector (typically uniform, or from the same distribution as $\vec e$), i.e. is consistent across all samples
  • $e\in\mathbb{Z}_q$ is "small". Say it is $\mathcal{N}(0, \sigma_0^2)$.
  • $u\in\mathbb{Z}_q$ is uniform, independent of all the above quantities.

Note that in isolation (i.e. when $a$ is not given to an adversary) $b := \langle \vec a, \vec s\rangle + \vec e$ can be shown to be very close to uniform in a statistical sense. So the main novelty in the LWE assumption is that when this $\vec a$ is leaked, it is still hard to distinguish $\langle \vec a, \vec s\rangle + \vec e$ from unifom without access to $\vec s$.

Note that given access to a sample of the above form, an adversary may add independent noise $\mathcal{N}(0, \sigma_1^2)$ to the second component. This will

  • Uniform Case: Yield uniformly random samples, and
  • LWE Case: Yield LWE samples with error drawn from $\mathcal{N}(0, \sigma_0^2+\sigma_1^2)$.

i.e. solving large-error LWE is not easier than solve small-error LWE.

So why do we want to keep the LWE error small? Typically, to encrypt with LWE, we encode messages $m\in\{0,1\}$ via the error-tolerant encoding $m\mapsto (q/2)m$. This is such that we can decode

$$(q/2)m+e\mapsto m$$

provided that $|e| < q/4$. So if our error is too large, despite being more secure, we can no longer decrypt correctly. In particular, if we added uniform noise to the second component of $(\vec a, b)$, we would be information theoretically secure, yet we also could not decrypt correctly anymore.

Error often grows fairly quickly with homomorphic operations. So starting with initially small error can be quite important to building a cryptosystem with more homomorphic capabilities.

Zpeed78 avatar
sa flag
Why is it possible to hide the message within the structure $As + e$?
Mark avatar
ng flag
Under the LWE assumption, $(A, As + e)$ is pseudorandom, i.e. no adversary can tell the difference between it and $(A, u)$, for uniformly-random $u$. Then we are just hiding the message using a uniformly-random mask $u$, i.e. doing something roughly equivalent to the one-time pad.
Zpeed78 avatar
sa flag
Hi Mark, So we exploit the pseudo randomness to hide our message in there? But why exactly can we do that? See also my question here https://crypto.stackexchange.com/questions/107303. It's still a little unclear to me why you can do that.
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.