LWE assumption in cryptographic applications

Question

The LWE assumption states that it is hard to distinguish LWE samples from uniformly distributed samples. That is, the distinction $(A,b)$ with $A$ and $b$ uniformly distributed, is hard to distinguish from $(A,b=As+e)$, where $A$, $s$ are uniformly distributed and $e$ follows a different distribution.

However, in cryptographic applications, we have an additional message $m$ that we want to hide within the $As+e$ construction, so we end up with something like $As + e + m$

My question is, why can we still use the LWE assumption for this and say that this is also hard to distinguish from a uniform distribution? Is there perhaps a rationale for this, that adding a constant (consider message $m$ as a constant), does not significantly change the distribution?

Answer 1

The following is a good general result to keep in mind, and a good exercise to prove if you don't see why it might be true.

Let $G$ be a finite group. Let $\mathcal{D}$ be a distribution on $G$ that is "shift-invariant", meaning

$$\forall m,k\in G: \Pr_{h\sim \mathcal{D}}[h = k] = \Pr_{h\sim\mathcal{D}}[h +m = k].$$

Define a private-key cryptosystem where

• $\mathsf{KeyGen}$ samples $sk\sim\mathcal{D}$
• $\mathsf{Enc}_{sk}(m) = sk + m$
• $\mathsf{Dec}_{sk}(c) = (-sk) + c$

Then $(\mathsf{KeyGen}, \mathsf{Enc}, \mathsf{Dec})$ is a perfectly-secure encryption scheme.

Typically you see this for the group $(\mathbb{F}_2^n, \oplus)$, where $\oplus$ is XOR. The resulting scheme is the one-time pad, and the security proof follows from Shannon's initial argument regarding the security of the one-time pad.

Note that for finite groups, the only shift-invariant distributions are uniform distributions on $G$. The more general property is known as $G$ being a "Haar measure", but this isn't cryptographically useful --- you should only ever use the above for finite groups.

Anyway, in terms of the above, the way to show the construction you discuss is secure is the following.

1. Consider an alternative cryptosystem, where you encrypt with $(A, u + m)$ rather than $(A, As + e + m)$
2. Show that encrypting with $(A, u + m)$ is an instantiation of the above result for the group $\mathbb{Z}_q^n\times \mathbb{Z}_q$ (technically you are only encrypting messages in the sub-group $\{0\}^n\times \mathbb{Z}_q$ of this group but whatever, that doesn't hurt security).

The adversary cannot attack the second scheme (it's information theoretically secure). You can then bound the advantage of an adversary in attacking your cryptosystem by the advantage of an adversary in distinguishing your cryptosystem from the cryptosystem of 1. It should be routine to verify this advantage is precisely the advantage of the adversary in solving the LWE problem.

With respect to your comment to the other answer, the point isn't to compare the distributions $N(\mu,\sigma^2)$ and $N(\mu+c,\sigma^2)$, as they may be distinguishable for $\sigma^2$ small. Instead, you compare the distributions $U(G)$ and $U(G)+m$, which are exactly the same distribution for any $m\in G$.

Answer 2

Adding a constant with wrap-around (or more generally, applying any bijection to a finite set) preserves the collection of probabilities of any discrete distribution on that finite set. Naturally, this includes both the uniform distribution and any distribution that approximates the uniform. Difficulty of distinguishing under addition of message data is therefore a straightforward equivalent to the original formulation. The original formulation involves fewer variables and is therefore to be preferred.