Public-key cryptosystems provably secure against chosen ciphertext attacks

Abstract

We show how to construct a public-key cryptosystem (as originally defined by Diffe and Hellman) secure against chosen ciphertext attacks, given a public-key cryptosystem secure against passive eavesdropping and a non-interactive zero-knowledge proof system in the shared string model. No such secure cryptosystems were known before. A concrete implementation can be based on quadratic residuosity intractability.