Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR01-072 | 12th December 2001 00:00

Universal Hash Proofs and and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption Revision of: TR01-072

RSS-Feed




Revision #2
Authors: Ronald Cramer, Victor Shoup
Accepted on: 12th December 2001 00:00
Downloads: 2122
Keywords: 


Abstract:

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 an NP 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 systemas 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 Cramer-Shoup encryption scheme
(which up until now was the only practical
encryption scheme that could be proved secure against adaptive chosen
ciphertext attack under a reasonable assumption,
namely, the Decision Diffie-Hellman assumption) is also a special case
of our general theory.


Revision #1 to TR01-072 | 12th December 2001 00:00





Revision #1
Authors: Ronald Cramer, Victor Shoup, Victor Shoup
Accepted on: 12th December 2001 00:00
Downloads: 2027
Keywords: 


Abstract:


Paper:

TR01-072 | 18th October 2001 00:00

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





TR01-072
Authors: Ronald Cramer, Victor Shoup
Publication: 25th October 2001 00:06
Downloads: 2190
Keywords: 


Abstract:

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 an NP 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 systemas 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 Cramer-Shoup encryption scheme
(which up until now was the only practical
encryption scheme that could be proved secure against adaptive chosen
ciphertext attack under a reasonable assumption,
namely, the Decision Diffie-Hellman assumption) is also a special case
of our general theory.



ISSN 1433-8092 | Imprint