The Gap-Problems: A New Class of Problems for the Security of Cryptographic Schemes

By Tatsuaki Okamoto, David Pointcheval. International Conference on Theory and Practice of Public Key Cryptography, 2001

504 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/bf70cf725910def1ea3cbbd44970b8691043d046

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. Dan Boneh
2. Brent Waters
3. Hovav Shacham
4. Alfred J. Menezes
5. David Pointcheval
6. Craig Gentry
7. Kristin E. Lauter
8. Gilles Barthe

In Computational Theory and Mathematics

1. Dan Boneh
2. Kristin E. Lauter
3. Hovav Shacham
4. Alfred J. Menezes
5. Ben Lynn
6. David Pointcheval
7. Scott A. Vanstone
8. Darrel Hankerson

Citations in the corpus

• Stronger Security of Authenticated Key Exchange (2006, methodology): “The GDH assumption was introduced by Okamoto and Pointcheval [17] and is now a standard cryptographic assumption used to establish the security of many protocols.”
• Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack (2003, background): “Our presentation here was somewhat inuenced by the paper [ OP01 ], which formally introduces the notion of the CDH assumption relative to an oracle for the DDH problem.”
• Short Signatures from the Weil Pairing (2001, methodology): “Okamoto and Pointcheval [ 20 ] commented that a Gap Diffie-Hellman group gives rise to a signature scheme.”
• Formal Proofs for the Security of Signcryption (2002, methodology): “In this paper, we only recall the Gap Diffie-Hellman (GDH) problem, among the various gap problems discussed in [16], on which the confidentiality of signcryption is based.”
• A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications (2003, background): “More recently Paillier [21] proposed a generalization of the Okamoto-Uchiyama cryptosystem that works in the multiplicative group Z * N 2 and allows to consider N as a standard RSA modulus.”
• HMQV: A High-Performance Secure Diffie-Hellman Protocol (2005, background): “For this latter property, and only for it, we need to resort to two strong assumptions: Gap Diffie-Hellman [37] ; in return we get a guarantee that not even the session key computed using the exposed exponent is compromised by this leakage.”
• Formal certification of code-based cryptographic proofs (2009, background): “1Groups where DDH is easy and CDH is believed to be hard are of practical importance in cryptography and are called Diffie-Hellman gap groups [Okamoto and Pointcheval 2001].”
• A Proposal for an ISO Standard for Public Key Encryption (2001, unknown): “This latter assumption is called the gap-CDH assumption, and is studied in detail in [ OP01 ].”
• A Formal Security Analysis of the Signal Messaging Protocol (2017, background): “(iii) Gap Diffie-Hellman (GDH) [59]: it is hard to compute the value g αβ from ( g α , g β ) even when given black box access to a DDH oracle, i.e., (cid:15) GDH ( D ) is negligible in log( q ) for any efficient D .”
• Guide to Elliptic Curve Cryptography (2004, methodology): “Solving the Diffie-Hellman problem given an oracle for the decision Diffie-Hellman problem is an example of a gap problem, a notion introduced by Okamoto and Pointcheval [356].”