Factoring ⇒ CPA-secure PKE (Blum–Goldwasser)
Statement
Let sample independent uniform -bit primes and output , a Blum integer, and . To encrypt , the Blum–Goldwasser scheme, in its one-bit-per-squaring form, samples a uniform , sets for , and outputs ; decryption recovers from with , since squaring permutes , and recomputes the pad. If factoring Blum integers is hard, the scheme is a semantically secure, equivalently CPA-secure, PKE — BG84.
Sketch
The pad is the Blum–Blum–Shub output on and is the next state. The proof of Factoring ⇒ PRG predicts each output bit from the state after it, so under the same assumption the pad together with is indistinguishable from a uniform string together with , and the ciphertext is then independent of — standard.
Notes
- A ciphertext is the message length plus one element of . Encryption costs about one squaring modulo per message bit — standard. Decryption adds one exponentiation modulo each of and , which computes directly from — BG84.
- Flipping bits of the masked part flips the same plaintext bits, so the scheme is malleable and not CCA-secure — standard.
- Under the quadratic residuosity assumption, bitwise Goldwasser–Micali encryption is also CPA-secure (QR ⇒ PKE), at a cost of one element of per plaintext bit — GM84.