Lossy trapdoor functions ⇒ IND-CCA PKE

Fully-black-box reduction · standard model · PW08, MY10 · security loss: for PW08’s construction, a constant number of hybrids plus a statistical leftover-hash term

Statement

Lossy trapdoor functions imply IND-CCA-secure PKE: PW08 construct it from lossy TDFs of sufficient lossiness — PW08 — and MY10 from every lossy TDF, and even from slightly lossy ones that lose only a noticeable fraction of one bit — MY10. The first step is an IND-CPA scheme: the public key is an injective-mode index $s$ and a pairwise-independent hash $h$, and $m$ is encrypted as $(F_s(x),h(x)\oplus m)$ for uniform $x$. The IND-CCA scheme adds an all-but-one lossy TDF, which PW08 build from lossy TDFs of sufficient lossiness, and a strongly unforgeable one-time signature.

Sketch

Switching $s$ to a lossy index is indistinguishable by lossy-TDF security; in lossy mode $F_s(x)$ leaves $x$ with min-entropy at least the lossiness $k$, so by the leftover hash lemma $h(x)$ is statistically close to uniform and the IND-CPA ciphertext statistically hides $m$.

Notes

• The loss is one injective-to-lossy hop plus the leftover-hash term for the IND-CPA scheme; the IND-CCA proof adds a constant number of hops, for one-time-signature unforgeability and all-but-one branch hiding — PW08.