Abstract: A popular paradigm for achieving privacy plus authenticity is to append some ``redundancy'' to the data before encrypting. The redundancy is computed by applying a redundancy function to the data. We investigate the security of this paradigm at both a general and a specific level. We consider various possible notions of privacy for the base encryption scheme, and for each such notion we provide a condition on the redundancy function that is necessary and sufficient to ensure authenticity of the encryption-with-redundancy scheme. We then consider the case where the base encryption scheme is a variant of CBC called NCBC, and find sufficient conditions on the redundancy functions for NCBC encryption-with-redundancy to provide authenticity. Our results highlight an important distinction between public redundancy functions, meaning those that the adversary can compute, and secret ones, meaning those that depend on the shared key between the legitimate parties.
Ref: Extended abstract in Advances in Cryptology - Eurocrypt 2001 Proceedings, Lecture Notes in Computer Science Vol. 2045 , B. Pfitzmann ed, Springer-Verlag, 2001. Full paper available below.
Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).