Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks

       Moni Naor      Moti Yung


We show how to construct a public-key cryptosystem that is semanitcally secure against  chosen ciphertext attacks in the following sense: the attackers, get to encrypt or decrypt any sequence of plaintext/ciphertext of their choice. Then they are faced with a challenge: distinguish between the ciphertexts of two messages (again of their choice). The attackers should not have any non-negligible advantage in distinguishing the ciphertexts. Such an attack is known as 'chosen ciphertext in the preprocessing mode' or `lunchtime'. It is relevant in many situation, e.g. proving.identification based on the ability ot decrypt.

The construction is based on (i) a public-key cryptosystem secure against passive eavesdropping (ii) a non-interactive zero-knowledge proof system in the shared string model. No such secure cryptosystems were known before.

Postscript, gzipped Postscript

Related On-Line Papers:

Back to On-Line Publications

Back Home