On the Security Notions for Public-Key Encryption Schemes.

Duong Hieu Phan and David Pointcheval.

Abstract: In this paper, we revisit the security notions for public-key encryption, and namely indistinguishability. We indeed achieve the surprising result that no decryption query before receiving the challenge ciphertext can be replaced by queries (whatever the number is) after having received the challenge, and vice-versa. This remark leads to a stricter and more complex hierarchy for security notions in the public-key setting: the (i; j)-IND level, in which an adversary can ask at most i (j resp.) queries before (after resp.) receiving the challenge. Excepted the trivial implications, all the other relations are strict gaps, with no polynomial reduction (under the assumption that IND-CCA2 secure encryption schemes exist.) Similarly, we define different levels for non-malleability.

Ref: Proceeding of SCN '04, Lecture Notes in Computer Science Vol. 3352, pages 33-47, Springer-Verlag, 2004.

Available: pdf.