Public-key cryptosystems provably secure against chosen ciphertext attacks

Abstract

We show how to construct a public-key cryptosystem (as originally defined by DiNe and Hellman) secure against chosen ciphertezt attacks, given a public-key cryptosystern secure against passive eavesdropping and a noninteractive 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.