Abstract
This paper introduces a novel class of computational problems, the gap problems, which can be considered as a dual to the class of the decision problems. We show the relationship among inverting problems, decision problems and gap problems. These problems find a nice and rich practical instantiation with the Diffie-Hellman problems. Then, we see how the gap problems find natural applications in cryptography, namely for proving the security of very efficientsc hemes, but also for solving a more than 10-year old open security problem: the Chaum's undeniable signature.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
W. Alexi, B. Chor, O. Goldreich, and C. P. Schnorr. RSA and Rabin Functions: Certain Parts are as Hard as the Whole. SIAM Journal on Computing, 17:194–209, 1988.
M. Bellare and P. Rogaway. Random Oracles Are Practical: a Paradigm for Designing EfficientProt ocols. In Proc. of the 1st CCS, pages 62–73. ACM Press, New York, 1993.
M. Bellare and P. Rogaway. The Exact Security of Digital Signatures-How to Sign with RSA and Rabin. In Eurocrypt’ 96, LNCS 1070, pages 399–416. Springer-Verlag, Berlin, 1996.
S. A. Brands. An Efficient Off-Line Electronic Cash System Based on the Representation roblem. Technical Report CS-R9323, CWI, Amsterdam, 1993.
S. A. Brands. Off-Line Electronic Cash Based on Secret-Key Certificates. In LATIN’ 95, LNCS 911, pages 131–166. Springer-Verlag, Berlin, 1995.
S. A. Brands. Secret-Key Certificates. Technical Report CS-R9510, CWI, Amsterdam, 1995.
D. Chaum. Zero-Knowledge Undeniable Signatures. In Eurocrypt’ 90, LNCS 473, pages 458–464. Springer-Verlag, Berlin, 1991.
D. Chaum. Designated Confirmer Signatures. In Eurocrypt’ 94, LNCS 950, pages 86–91. Springer-Verlag, Berlin, 1995.
D. Chaum and H. van Antwerpen. Undeniable Signatures. In Crypto’ 89, LNCS 435, pages 212–216. Springer-Verlag, Berlin, 1990.
J.-S. Coron. On the Exact Security of Full-Domain-Hash. In Crypto’ 2000, LNCS 1880, pages 229–235. Springer-Verlag, Berlin, 2000.
R. Cramer and V. Shoup. A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack. In Crypto’ 98, LNCS 1462, pages 13–25. Springer-Verlag, Berlin, 1998.
W. Diffie and M. E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, IT-22(6):644–654, November 1976.
T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, IT-31(4):469–472, July 1985.
R. Fischlin and C. P. Schnorr. Stronger Security Proofs for RSA and Rabin bits. Journal of Cryptology, 13(2):221–244, 2000.
G. Frey, M. Müller, and H. G. Rück. The Tate-Pairing and the Discrete Logarithm Applied to Elliptic Curve Cryptosystems. IEEE Transactions on Information Theory, 45:1717–1719, 1999.
G. Frey and H. G. Rück. A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves. Mathematics of Computation, 62:865–874, 1994.
S. Goldwasser, S. Micali, and R. Rivest. A Digital Signature Scheme Secure Against Adaptative Chosen-Message Attacks. SIAM Journal of Computing, 17(2):281–308, April 1988.
D. M. Gordon. Discrete Logarithms in GF(p) Using the Number Field Sieve. SIAM Journal of Discrete Mathematics, 6(1):124–138, February 1993.
M. Jakobsson, K. Sako, and R. Impagliazzo. Designated Verifier Proofs and Their Applications. In Eurocrypt’ 96, LNCS 1070, pages 143–154. Springer-Verlag, Berlin, 1996.
N. Koblitz. Elliptic Curve Cryptosystems. Mathematics of Computation, 48(177):203–209, January 1987.
N. Koblitz. A Family of Jacobians Suitable for Discrete Log Cryptosystems. In Crypto’ 88, LNCS 403, pages 94–99. Springer-Verlag, Berlin, 1989.
N. Koblitz. Hyperelliptic Cryptosystems. Journal of Cryptology, 1:139–150, 1989.
A. Lenstra and H. Lenstra. The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics. Springer-Verlag, 1993.
U. M. Maurer and S. Wolf. Diffie Hellman Oracles. In Crypto’ 96, LNCS 1109, pages 268–282. Springer-Verlag, Berlin, 1996.
U. M. Maurer and S. Wolf. Diffie-Hellman, Decision Diffie-Hellman, and Discrete Logarithms. In Proceedings of ISIT’ 98, page 327. IEEE Information Theory Society, 1998.
U. M. Maurer and S. Wolf. The Diffie-Hellman Protocol. Designs, Codes, and Cryptography, 19:147–171, 2000.
M. Michels and M. Stadler. Generic Constructions for Secure and Efficient Confirmer Signature Schemes. In Eurocrypt’ 98, LNCS 1403, pages 406–421. Springer-Verlag, Berlin, 1998.
V. I. Nechaev. Complexity of a Determinate Algorithm for the Discrete Logarithm. Mathematical Notes, 55(2):165–172, 1994.
T. Okamoto. Designated Confirmer Signatures and Public Key Encryption are Equivalent. In Crypto’ 94, LNCS 839, pages 61–74. Springer-Verlag, Berlin, 1994.
T. Okamoto and D. Pointcheval. REACT: Rapid Enhanced-security Asymmetric Cryptosystem Transform. In RSA’ 2001, LNCS. Springer-Verlag, Berlin, 2001.
D. Pointcheval. Self-Scrambling Anonymizers. In Financial Cryptography’ 2000, LNCS. Springer-Verlag, Berlin, 2000.
D. Pointcheval and J. Stern. Security Arguments for Digital Signatures and Blind Signatures. Journal of Cryptology, 13(3):361–396, 2000.
R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Communications of the ACM, 21(2):120–126, February 1978.
C. P. Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptology, 4(3):161–174, 1991.
V. Shoup. Lower Bounds for Discrete Logarithms and Related Problems. In Eurocrypt’ 97, LNCS 1233, pages 256–266. Springer-Verlag, Berlin, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Okamoto, T., Pointcheval, D. (2001). The Gap-Problems: A New Class of Problems for the Security of Cryptographic Schemes. In: Kim, K. (eds) Public Key Cryptography. PKC 2001. Lecture Notes in Computer Science, vol 1992. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44586-2_8
Download citation
DOI: https://doi.org/10.1007/3-540-44586-2_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41658-6
Online ISBN: 978-3-540-44586-9
eBook Packages: Springer Book Archive