Factoring + UOWHF ⇒ CCA-secure PKE (Hofheinz–Kiltz)

Standard model · HK09 · security loss: polynomial: the hard-core-bit step to factoring loses a polynomial factor, and the chosen-ciphertext simulation adds the target-collision advantage

Statement

If factoring Blum integers is hard and target-collision-resistant hash functions exist, there is an IND-CCA2-secure PKE scheme in the standard model, a variant of Blum–Goldwasser encryption — HK09. For arbitrary Blum integers the encapsulated key is extracted by the Goldreich–Levin predicate under a public random seed — HK09, GL89; in the original version, whose key is a block of Blum–Blum–Shub generator output, the factors of the modulus are safe primes — HK09.

Sketch

The reduction plants its challenge so that it can decrypt every ciphertext except those carrying the challenge’s tag, an all-but-one decryption mechanism, with tags computed by a target-collision-resistant hash — HK09.

Notes

• The proof of the Blum–Blum–Shub version needs its input nearly uniform in ${\mathrm{QR}}_N$ through powers of a generator, a property that safe-prime factors provide — HK09. For general Blum integers ${\mathrm{QR}}_N$ need not be cyclic: for $N=7\cdot 19$, ${\mathrm{QR}}_N\cong C_3\times C_9$ has $27$ elements but no cyclic subgroup larger than $9$ — standard.
• Target-collision-resistant hashing follows from factoring through OWF ⇒ UOWHF — Rom90.
• Earlier practical standard-model CCA2 schemes rest on decisional assumptions, DDH and quadratic residuosity — CS98, CS02; HK09 give the first practical one from factoring — HK09.