# Why do we need the leftover hash lemma for this hybrid proof (Learning with Errors)?

I've been reading about Learning with Errors here. On p. 7 there's a proof for the security of the PKE scheme, that goes through the leftover hash lemma, in order to prove that: $$(pk, Enc(0))\equiv (pk, Enc(1))$$ (Hybrid 2 and 3 there, for example).

I don't understand why we need that transition at all. Why can't we just use the decision-LWE assumption, i.e. using their notation:

If: $$pk=(A, b^T)$$ $$Enc(0)=(Ar, b^Tr)$$ $$Enc(1)=(Ar, b^Tr+\lceil q/2\rceil)$$ then, using '$$\sim$$' to denote computationally indistinguishable, and $$u$$ - a random uniform vector that has the same length of $$b$$, why can't we say:

$$(A, b^T, Ar, b^Tr) \sim (A, u^T, Ar, u^Tr) \sim (A, u^T, Ar, u^Tr+\lceil q/2\rceil)\sim (A, b^T, Ar, b^Tr+\lceil q/2 \rceil)$$

It seems obvious that the middle '$$\sim$$' holds, no? All we're doing there is adding some constant value to something random - it should remain indistinguishable from random. This is the part that was replaced by another step using the leftover hash lemma and I would love to understand why.

• The first three terms have some information about $r,u$ so that the middle $\sim$ becomes nontrivial. Consider an extreme case that the third term is just $r$, not $Ar$, where you can distinguish both cases. The leftover hash lemma resolves this problem, showing the correlation is negligible in the original case.
– Hhan
Jun 16, 2022 at 11:55

In fact, every lattice-based NIST PQC round 3 candidate that I know of (Saber, Kyber, FrodoKEM) uses this strategy. I won't copy over the precise algorithm description (it can be found here), but the idea behind encryption is that an LWE (public) key looks like $$(A, As + e)$$. Therefore, if you make another LWE sample of the form $$(A^t, A^t r + e_r)$$, then the people who know $$r$$ and $$s$$ and (approximately) agree on the value of $$r^tAs$$, and use this to encrypt (up to low order error terms that can be dealt with). If one didn't have to deal with noise, this way of computing $$r^tAs$$ in "two different ways" would be analogous to how in DH-based schemes one computes $$(g^a)^b = g^{ab} = (g^b)^a$$ in "two different ways", hence the name.
Given random A (public) and r, LHL assures that (A, Ar) is statistically $$\epsilon$$-close to (A,u). In the middle $$\sim$$, the indistinguishability holds if $$u^Tr$$ on both sides are different randoms. Otherwise, they are always $$\lceil q/2 \rceil$$-apart. This is why we use LHL to show H2 $$\sim$$ H3 and H3 $$\sim$$ H4 as in L13.pdf.