Non-malleable cryptography

The notion of non-malleable cryptography, an extension of semantically secure cryptography, is defined. Informally, the additional requirement is that given the ciphertext it is impossible to generate a diflerent ciphertext so that the respective plaintexts are related. The same concept makes sense in the contexts of string commitment and zero-knowledge proofs of possession of knowledge. Non-malleable schemes for each of these three problems are presented. The schemes do not assume a trusted center; a user need not know anything about the number or identity of other system users. The results can be applied to contract bidding, even when the nonfaulty bidders are unaware of the existence of the faulty bidders, and the problem of a "transparent intermediary" in a zero-knowledge proof of possession of knowledge is solved.