Non-Malleable Cryptography

Cynthia Dwork, IBM Almaden Research Center
Tuesday 15 Oct 1996, 4:15pm, Gates 104


The notion of non-malleable cryptography, an extension of semantically secure cryptography, will be defined. Informally, in the context of encryption the additional requirement is that given the ciphertext it is impossible to generate a different ciphertext so that the respective plaintexts are related. Common public key cryptosystems are quite malleable: for example, in RSA it is trivial to compute E(2x) given only E(x). Although defined with public key cryptography in mind, non-malleability issues also arise in private-key cryptography. Indeed, the security of many common protocols, such as Kerberos, relies implicitly on the inability of an adversary to compute E(f(N)) given only E(N), for simple functions f. The talk will focus on non-malleable public key cryptosystems. with a few remarks on non-malleable schemes for private-key cryptography, string commitment, and proofs of possession of knowledge.

This is joint work with Danny Dolev and Moni Naor.