2
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ 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. $\endgroup$
    – Hhan
    Jun 16, 2022 at 11:55

2 Answers 2

2
$\begingroup$

Your initial question regarding LHL was answered in the comments. I'll just briefly mention that LHL is not required to build PKE from lattices, meaning that there is a (slightly different) construction that solely needs LWE (although it "applies LWE twice", the LHL version "applies LWE once"). The construction without LHL has some conceptual similarities to encryption based on the Diffie Hellman assumption (though here it is "noisy").

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.