## Universal Hash Proofs and a Paradigm for Adaptive Chosen
Ciphertext Secure Public-Key Encryption

### Victor Shoup

### IBM Research

We present several new and fairly practical public-key encryption
schemes and
prove them secure against adaptive chosen ciphertext attack. One scheme
is
based on Paillier's Decision Composite Residuosity (DCR) assumption,
while
another is based in the classical Quadratic Residuosity (QR) assumption.
The
analysis is in the standard cryptographic model, i.e., the security of
our
schemes does not rely on the Random Oracle model.

We also introduce the notion of a universal hash proof system.
Essentially,
this is a special kind of non-interactive zero-knowledge proof system
for a
language. We do not show that universal hash proof systems exist for
all NP
languages, but we do show how to construct very efficient universal hash
proof
systems for a general class of group-theoretic language membership
problems.

Given an efficient universal hash proof system for a language with
certain
natural cryptographic indistinguishability properties, we show how to
construct an efficient public-key encryption schemes secure against
adaptive
chosen ciphertext attack in the standard model. Our construction only
uses the
universal hash proof system as a primitive: no other primitives are
required,
although even more efficient encryption schemes can be obtained by using
hash
functions with appropriate collision-resistance properties.

We show how to construct efficient universal hash proof systems for
languages
related to the DCR and QR assumptions. From these we get corresponding
public-key encryption schemes that are secure under these assumptions.
We also
show that the original Cramer-Shoup encryption scheme is also a special
case of
our general theory.

This is joint work with Ronald Cramer.

Gates 4B (opposite 490), **Friday** 2/22/02, 4:30 PM