Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

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

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 1992))

Included in the following conference series:

  • 3416Accesses

Abstract

This paper introduces a novel class of computational problems, thegap problems, which can be considered as a dual to the class of thedecision 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.

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

  1. 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.

    Article MathSciNet MATH  Google Scholar 

  2. M. Bellare and P. Rogaway. Random Oracles Are Practical: a Paradigm for Designing EfficientProt ocols. InProc. of the 1st CCS, pages 62–73. ACM Press, New York, 1993.

    Google Scholar 

  3. M. Bellare and P. Rogaway. The Exact Security of Digital Signatures-How to Sign with RSA and Rabin. InEurocrypt’ 96, LNCS 1070, pages 399–416. Springer-Verlag, Berlin, 1996.

    Google Scholar 

  4. S. A. Brands. An Efficient Off-Line Electronic Cash System Based on the Representation roblem. Technical Report CS-R9323, CWI, Amsterdam, 1993.

    Google Scholar 

  5. S. A. Brands. Off-Line Electronic Cash Based on Secret-Key Certificates. InLATIN’ 95, LNCS 911, pages 131–166. Springer-Verlag, Berlin, 1995.

    Google Scholar 

  6. S. A. Brands. Secret-Key Certificates. Technical Report CS-R9510, CWI, Amsterdam, 1995.

    MATH  Google Scholar 

  7. D. Chaum. Zero-Knowledge Undeniable Signatures. InEurocrypt’ 90, LNCS 473, pages 458–464. Springer-Verlag, Berlin, 1991.

    Google Scholar 

  8. D. Chaum. Designated Confirmer Signatures. InEurocrypt’ 94, LNCS 950, pages 86–91. Springer-Verlag, Berlin, 1995.

    Chapter  Google Scholar 

  9. D. Chaum and H. van Antwerpen. Undeniable Signatures. InCrypto’ 89, LNCS 435, pages 212–216. Springer-Verlag, Berlin, 1990.

    Google Scholar 

  10. J.-S. Coron. On the Exact Security of Full-Domain-Hash. InCrypto’ 2000, LNCS 1880, pages 229–235. Springer-Verlag, Berlin, 2000.

    Chapter  Google Scholar 

  11. R. Cramer and V. Shoup. A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack. InCrypto’ 98, LNCS 1462, pages 13–25. Springer-Verlag, Berlin, 1998.

    Google Scholar 

  12. W. Diffie and M. E. Hellman. New Directions in Cryptography.IEEE Transactions on Information Theory, IT-22(6):644–654, November 1976.

    Article MathSciNet MATH  Google Scholar 

  13. 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.

    Article MathSciNet  Google Scholar 

  14. R. Fischlin and C. P. Schnorr. Stronger Security Proofs for RSA and Rabin bits.Journal of Cryptology, 13(2):221–244, 2000.

    Article MathSciNet MATH  Google Scholar 

  15. 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.

    Article MathSciNet MATH  Google Scholar 

  16. G. Frey and H. G. Rück. A Remark Concerningm-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves.Mathematics of Computation, 62:865–874, 1994.

    MathSciNet MATH  Google Scholar 

  17. 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.

    Article MATH  Google Scholar 

  18. D. M. Gordon. Discrete Logarithms in GF(p) Using the Number Field Sieve.SIAM Journal of Discrete Mathematics, 6(1):124–138, February 1993.

    Article MathSciNet MATH  Google Scholar 

  19. M. Jakobsson, K. Sako, and R. Impagliazzo. Designated Verifier Proofs and Their Applications. InEurocrypt’ 96, LNCS 1070, pages 143–154. Springer-Verlag, Berlin, 1996.

    Google Scholar 

  20. N. Koblitz. Elliptic Curve Cryptosystems.Mathematics of Computation, 48(177):203–209, January 1987.

    Article MathSciNet MATH  Google Scholar 

  21. N. Koblitz. A Family of Jacobians Suitable for Discrete Log Cryptosystems. InCrypto’ 88, LNCS 403, pages 94–99. Springer-Verlag, Berlin, 1989.

    Chapter  Google Scholar 

  22. N. Koblitz. Hyperelliptic Cryptosystems.Journal of Cryptology, 1:139–150, 1989.

    Article MathSciNet MATH  Google Scholar 

  23. A. Lenstra and H. Lenstra.The Development of the Number Field Sieve, volume 1554 ofLecture Notes in Mathematics. Springer-Verlag, 1993.

    Google Scholar 

  24. U. M. Maurer and S. Wolf. Diffie Hellman Oracles. InCrypto’ 96, LNCS 1109, pages 268–282. Springer-Verlag, Berlin, 1996.

    Google Scholar 

  25. U. M. Maurer and S. Wolf. Diffie-Hellman, Decision Diffie-Hellman, and Discrete Logarithms. InProceedings of ISIT’ 98, page 327. IEEE Information Theory Society, 1998.

    Google Scholar 

  26. U. M. Maurer and S. Wolf. The Diffie-Hellman Protocol.Designs, Codes, and Cryptography, 19:147–171, 2000.

    Article MathSciNet MATH  Google Scholar 

  27. M. Michels and M. Stadler. Generic Constructions for Secure and Efficient Confirmer Signature Schemes. InEurocrypt’ 98, LNCS 1403, pages 406–421. Springer-Verlag, Berlin, 1998.

    Chapter  Google Scholar 

  28. V. I. Nechaev. Complexity of a Determinate Algorithm for the Discrete Logarithm.Mathematical Notes, 55(2):165–172, 1994.

    Article MathSciNet MATH  Google Scholar 

  29. T. Okamoto. Designated Confirmer Signatures and Public Key Encryption are Equivalent. InCrypto’ 94, LNCS 839, pages 61–74. Springer-Verlag, Berlin, 1994.

    Google Scholar 

  30. T. Okamoto and D. Pointcheval. REACT: Rapid Enhanced-security Asymmetric Cryptosystem Transform. InRSA’ 2001, LNCS. Springer-Verlag, Berlin, 2001.

    Google Scholar 

  31. D. Pointcheval. Self-Scrambling Anonymizers. InFinancial Cryptography’ 2000, LNCS. Springer-Verlag, Berlin, 2000.

    Google Scholar 

  32. D. Pointcheval and J. Stern. Security Arguments for Digital Signatures and Blind Signatures.Journal of Cryptology, 13(3):361–396, 2000.

    Article MATH  Google Scholar 

  33. 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.

    Article MathSciNet MATH  Google Scholar 

  34. C. P. Schnorr. Efficient Signature Generation by Smart Cards.Journal of Cryptology, 4(3):161–174, 1991.

    Article MathSciNet MATH  Google Scholar 

  35. V. Shoup. Lower Bounds for Discrete Logarithms and Related Problems. InEurocrypt’ 97, LNCS 1233, pages 256–266. Springer-Verlag, Berlin, 1997.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. NTT Labs, 1-1 Hikarinooka, Yokosuka-shi 239-0847, Japan

    Tatsuaki Okamoto

  2. Déptd'Informat ique, ENS - CNRS, 45 rue d'Ulm, 75230, Paris Cedex 05, France

    David Pointcheval

Authors
  1. Tatsuaki Okamoto

    You can also search for this author inPubMed Google Scholar

  2. David Pointcheval

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Information and Communications University,Information Security Group, 58-4 Hwaam-dong,Yusong-gu, 305-732, Taejon, Korea

    Kwangjo Kim

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

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp