Malleability (cryptography) - Example Malleable Cryptosystems

Example Malleable Cryptosystems

In a stream cipher, the ciphertext is produced by taking the exclusive or of the plaintext and a pseudorandom stream based on a secret key, as . An adversary can construct an encryption of for any, as .

In the RSA cryptosystem, a plaintext is encrypted as, where is the public key. Given such a ciphertext, an adversary can construct an encryption of for any, as . For this reason, RSA is commonly used together with padding methods such as OAEP or PKCS1.

In the ElGamal cryptosystem, a plaintext is encrypted as, where is the public key. Given such a ciphertext, an adversary can compute, which is a valid encryption of, for any . In contrast, the Cramer-Shoup system (which is based on ElGamal) is not malleable.

In the Paillier, ElGamal, and RSA cryptosystems, it is also possible to combine several ciphertexts together in a useful way to produce a related ciphertext. In Paillier, given only the public-key and an encryption of and, one can compute a valid encryption of their sum . In ElGamal and in RSA, one can combine encryptions of and to obtain a valid encryption of their product .