Abstract: We consider the problem of defining and achieving plaintext-aware encryption without random oracles in the classical public-key model. We provide definitions for a hierarchy of notions of increasing strength: PA0, PA1 and PA2, chosen so that PA1+IND-CPA => IND-CCA1 and PA2+IND-CPA => IND-CCA2. Towards achieving the new notions of plaintext awareness, we show that a scheme due to Damgard, denoted DEG, and the ``lite'' version of the Cramer-Shoup scheme, denoted CSL, are both PA0 under the KEA0 assumption of Damgard, and PA1 under an extension of this assumption called KEA1. As a result, DEG is the most efficient proven IND-CCA1 scheme known.
Ref: An extended abstract of this paper appeared in Advances in Cryptology - Asiacrypt 2004 Proceedings, Lecture Notes in Computer Science Vol. 3329, P. J. Lee ed, Springer-Verlag, 2004. Full paper available below.
Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).