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

By Ronald Cramer, Victor Shoup. International Conference on the Theory and Application of Cryptographic Techniques, 2001

872 citations recorded by the source corpus.

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 assumption, while another is based in the classical Quadratic Residuosity assumption. The analysis is in the standard cryptographic model, i.e., the security of our schemes does not rely on the Random Oracle model. Moreover, we introduce a general framework that allows one to construct secure encryption schemes in a generic fashion from language membership problems that satisfy certain technical requirements. Our new schemes fit into this framework, as does the Cramer-Shoup scheme based on the Decision Diffie-Hellman assumption.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/4da4f017deffa5a0952ed5b564c97ee1602d6ecf

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Brent Waters
2. Dan Boneh
3. Amit Sahai
4. Shai Halevi
5. Xavier Boyen
6. Craig Gentry
7. Eike Kiltz
8. Chris Peikert

Citations in the corpus

• Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack (2003, background): “Also, the authors of the present paper [ CS01 ] have generalized and extended the basic ideas underlying our encryption scheme, obtaining new and quite practical encryption schemes that are secure against adaptive chosen ciphertext attack under dierent assumptions | one scheme relies on Paillier’s D”
• Computational Differential Privacy from Lattice-Based Cryptography (2017, background): “In a subsequent work [7], a generalisation of the scheme from [21] is obtained based on smooth projective hash functions (see [12]).”
• Public-Key Cryptosystems Resilient to Key Leakage (2009, methodology): “To complement this situation, on the practical side, we prove that variants of the Cramer-Shoup cryptosystem [8] (along the lines of our generic transformation from hash proof systems) are CCA1-secure with any leakage of It is left as an open problem to construct a practical CCA-secure scheme that i”
• Single Database Private Information Retrieval with Logarithmic Communication (2004, methodology): “, the Cramer-Shoup CCA2 encryption scheme in the standard model [7] and the Damg̊ard-Jurik electronic voting scheme [8]), we believe CRA could be a good candidate for hardness assumption.”
• A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications (2003, methodology): “At Eurocrypt’02 Cramer and Shoup [7] proposed a very general and beautiful methodology to obtain security against adaptive chosen-ciphertext attacks from a certain class of cryptosystems with some well-defined algebraic properties.”
• An Algebraic Framework for Diffie–Hellman Assumptions (2013, methodology): “Since the work of Cramer and Shoup [9] it has been recognized that it is useful to view the DDH Assumption as a hard subgroup membership problem in 2.”
• Practical Verifiable Encryption and Decryption of Discrete Logarithms (2003, methodology): “The key ingredients that make our verifiable encryption protocol possible are: • Fujisaki and Okamoto’s method for proving relations on committed values [FO97] (with some refinements, as in [CS00, DF02]), • the related interval proofs [CM98, CFT98], • Paillier encryption [Pai99], and • Cramer and Sh”
• A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data (2013, methodology): “Albeit taking place in the random oracle model [2], it bears similarities with the techniques of Cramer and Shoup [10] (see also [6]) in that it appeals to an information theoretic argument exploiting some entropy hidden in the private key.”
• Security and Privacy in the Internet of Things (2017, background): “[31] proposed a variant of Paillier cryptosystem built from two-trapdoor Paillier [55, 45] with the promising properties: (i) it inherits the additively homomorphic property, and (ii) the ciphertext decryption can be done in a two-stage procedure.”
• Lossy trapdoor functions and their applications (2008, methodology): “The resulting ABO system gives rise to a CCA-secure cryptosystem having comparable performance to that of the Cramer-Shoup [13] projective-hash system when realized with Paillier encryption.”
• Chosen-Ciphertext Security from Identity-Based Encryption (2004, methodology): “The NIZK proofs used by Sahai [51] as well as the smooth hash proof systems used by Cramer and Shoup [21, 22] are shown by Elkind and Sahai to satisfy the appropriate criteria.”
• Direct chosen ciphertext security from identity-based techniques (2005, methodology): “Existing CCA2-secure threshold systems in the standard model, due to Canetti and Goldwasser [12], are based on the Cramer-Shoup system [13]; their system requires inter­action between the decryption parties, due to the fact that in the Cramer-Shoup system only parties possessing the pri­vate key ”
• A Survey of Homomorphic Encryption for Nonspecialists (2007, methodology): “More precisely, it is based on Damg˚ard-Jurik’s (presented above) and Cramer-Shoup’s [55] analyses and variants of Paillier’s scheme, and was proposed by [9].”
• A New Randomness Extraction Paradigm for Hybrid Encryption (2009, methodology): “In contrast, due to the dependence on the target colission resistant hash function, the efficient schemes from [2, 17] cannot be directly explained through Cramer and Shoup’s hash proof system framework [3] and therefore all require separate proofs.”
• Secure Hybrid Encryption from Weakened Key Encapsulation (2007, methodology): “Generalizing [12,21], we prove that computational”