CPA-secure PKE ⇔ Forward-secure PKE

Equivalence · fully-black-box reduction · standard model · folklore · security loss: a factor T from guessing the challenge period, from PKE to forward-secure PKE; none in the other direction

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