CPA-secure PKE ⇔ Forward-secure PKE
Statement
CPA-secure public-key encryption exists if and only if, for every polynomially bounded , forward-secure public-key encryption with periods exists — folklore. From a PKE scheme : the key-evolving samples independent key pairs for and outputs and ; deletes the first remaining key, so that ; period encrypts under and decrypts with . Conversely, the period- algorithms , and of a forward-secure scheme with periods form a CPA-secure PKE scheme.
Sketch
A forward-security adversary with challenge period gives a CPA adversary: sample a guess , embed the challenge public key as , forward the challenge query, and answer the break-in query for period with , which contains no key of index ; on a break-in for a period or a challenge for a period other than , output a uniform bit. The guess is right (, and then by admissibility) with probability , independently of the adversary’s view, so the CPA advantage is the forward-security advantage divided by . Conversely, a CPA adversary’s challenge is posed for period and the reduction breaks in during period .
Notes
- The public key of this construction grows linearly in . The constructions of CHK03 have keys and ciphertexts of size polynomial in and (Selectively secure HIBE ⇒ Forward-secure PKE (Canetti–Halevi–Katz), DBDH ⇒ Forward-secure PKE (Canetti–Halevi–Katz)).