AE ⇒ CCA-secure SKE

Fully-black-box reduction · standard model · BN00, KY00 · security loss: factor 2 in the integrity term: the CCA advantage is at most the CPA advantage plus twice the INT-CTXT advantage, at the same numbers of encryption and decryption queries

Statement

Let be an authenticated encryption scheme, a SKE scheme that is CPA-secure and INT-CTXT-secure. Then is CCA-secure: for every admissible CCA adversary making encryption and decryption queries there are adversaries and , running in about the time of , with

where makes encryption queries and makes encryption and verification queries — BN00. The CCA-secure scheme is itself, so it has the correctness and the message space of — standard. Concurrently and independently, KY00 prove that CPA security and unforgeability of ciphertexts together imply CCA security.

Sketch

Answer every decryption query with . An admissible adversary never queries an output of the encryption oracle, so this changes its view only once it submits a valid ciphertext that the encryption oracle did not output, which detects by forwarding the query to its verification oracle ; the modified game is the CPA game, played by .

Notes

  • INT-PTXT security does not suffice in place of INT-CTXT security, assuming CPA-secure SKE schemes and SUF-CMA-secure MACs exist: some instance of MAC-then-Encrypt is CPA-secure and INT-PTXT-secure but not CCA-secure — BN00.