Relations among Notions of Security for Public-Key Encryption Schemes

Authors: Mihir Bellare, Anand Desai, David Pointcheval and Phillip Rogaway

Reference: Advances in Cryptology - CRYPTO '98, Lecture Notes in Computer Science, Vol. 1462, H. Krawczyk, ed., Springer-Verlag, 1998.

Abstract: We compare the relative strengths of popular notions of security for public key encryption schemes. We consider the goals of privacy and non-malleability, each under chosen-plaintext attack and two kinds of chosen-ciphertext attack. For each of the resulting pairs of definitions we prove either an implication (every scheme meeting one notion must meet the other) or a separation (there is a scheme meeting one notion but not the other, assuming the first notion can be met at all). We similarly treat plaintext awareness, a notion of security in the random oracle model. An additional contribution of this paper is a new definition of non-malleability which we believe is simpler than the previous one.

Full version available in PDF or PostScript.

Rogaway's home page.