Designated Confirmer Signatures and Public-Key Encryption are Equivalent

  • Tatsuaki Okamoto
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)


The concept of designated confirmer signatures was introduced by Chaum [Cha94] to improve a shortcoming of undeniable signatures. The present paper formalizes the definition of designated confirmer signatures and proves that a designated confirmer signature scheme is equivalent to a public-key encryption scheme with respect to existence. In addition, the paper proposes practical designated confirmer signature schemes which are more efficient in signing than the previous scheme [Cha94].


  1. [BCC88]
    Brassard, G., Chaum, D., and Crépeau, C.: Minimum Disclosure Proofs of Knowledge. J. Computer and System Sciences, 37 (1988) 156–189zbMATHCrossRefGoogle Scholar
  2. [BCDP90]
    Boyar, J., Chaum, D., Damgård, I., Pedersen, T.: Convertible Undeniable Signatures. Proc. of Crypto’90, LNCS 537, Springer-Verlag, (1991) 189–205Google Scholar
  3. [Cha90]
    Chaum, D.: Zero-Knowledge Undeniable Signatures. Proc. of Eurocrypto’90, LNCS 473, Springer-Verlag, (1991) 458–464Google Scholar
  4. [Cha94]
    Chaum, D.: Designated Confirmer Signatures. Proc. of Eurocrypt’ 94, LNCS, Springer-Verlag (to appear)Google Scholar
  5. [CA89]
    Chaum, D., van Antwerpen, H.: Undeniable Signatures. Proc. of Crypto’89, LNCS 435, Springer-Verlag, (1990) 212–216Google Scholar
  6. [DH76]
    Diffie, W., Hellman, M. E.: New Directions in Cryptography. IEEE Trans. Information Theory, 22,6, (1976) 644–654zbMATHCrossRefMathSciNetGoogle Scholar
  7. [ElG85]
    ElGamal, T.: A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. Information Theory, 31,4, (1985) 460–472Google Scholar
  8. [FFS88]
    Feige, U., Fiat, A., Shamir, A.: Zero-Knowledge Proofs of Identity. J. of Cryptology, 1,2 (1988) 77–94zbMATHCrossRefMathSciNetGoogle Scholar
  9. [GGM84]
    Goldreich, O., Goldwasser, S., Micali, S.: How to Construct Random Functions. J. of ACM, 33,4 (1984) 792–807CrossRefMathSciNetGoogle Scholar
  10. [GL89]
    Goldreich, O., Levin, L.: A Hard-Core Predicate for any One-way Function. Proc. of STOC’89 (1989) 25–32Google Scholar
  11. [GM84]
    Goldwasser, S., Micali, S.: Probabilistic Encryption. J. Computer and System Sciences, 28,2 (1984) 270–299zbMATHCrossRefMathSciNetGoogle Scholar
  12. [GMRa89]
    Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive Proof Systems. SIAM J. Comput., 18,1 (1989) 186–208zbMATHCrossRefMathSciNetGoogle Scholar
  13. [GMRi88]
    Goldwasser, S., Micali, S., Rivest, R.: A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM J. Comput., 17,2 (1988) 281–308zbMATHCrossRefMathSciNetGoogle Scholar
  14. [GMW86]
    Goldreich, O., Micali, S., Wigderson, A.: Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design. Proc. FOCS (1986) 174–187Google Scholar
  15. [GQ88]
    Guillou, L. C., Quisquater, J.J.: A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory. Proc. of Eurocrypt’88, LNCS 330, Springer-Verlag (1988) 123–128Google Scholar
  16. [Has90]
    Håstad, J.: Pseudo-Random Generators under Uniform Assumptions. Proc. of STOC (1990) 395–404Google Scholar
  17. [ILL89]
    Impagliazzo, R., Levin, L., Luby, L.: Pseudo-Random Number Generation from One-Way Functions. Proc. of STOC (1989) 12–24Google Scholar
  18. [IR89]
    Impagliazzo, R., Rudich, S.: Limits on the Provable Consequence of One-Way Permutations. Proc. of STOC (1989) 44–61Google Scholar
  19. [IY87]
    Impagliazzo, R., Yung, M.: Direct Minimum-Knowledge Computations. Proc. of Crypto’87, LNCS 293, Springer-Verlag (1988) 40–51Google Scholar
  20. [MRS88]
    Micali, S., Rackoff, C., Sloan, B.: The Notion of Security of Probabilistic Cryptosystems. SIAM J. Comput., 17,2 (1988) 412–426zbMATHCrossRefMathSciNetGoogle Scholar
  21. [Nao90]
    Naor, M.: Bit Commitment Using Pseudo-Randomness. Proc. of Crypto’89, LNCS 435, Springer-Verlag, (1990) 128–136Google Scholar
  22. [NY89]
    Naor, M., Yung, M.: Universal One-Way Hash Functions and Their Cryptographic Applications. Proc. of STOC (1989) 33–43Google Scholar
  23. [OhOk88]
    Ohta, K., Okamoto, T.: A Modification of the Fiat-Shamir Scheme. Proc. of Crypto’88, LNCS 403, Springer-Verlag (1990) 232–243Google Scholar
  24. [Oka92]
    Okamoto, T.: Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes. Proc. of Crypto’92, LNCS 740, Springer-Verlag, (1993) 31–53Google Scholar
  25. [Oka93]
    Okamoto, T.: On the Relationship among Cryptographic Physical Assumptions. Proc. of ISAAC’93, LNCS 762, Springer-Verlag, (1993) 369–378Google Scholar
  26. [Rom90]
    Rompel, J.: One-Way Functions are Necessary and Sufficient for Secure Signature. Proc. of STOC (1990) 387–394Google Scholar
  27. [Sch91]
    Schnorr, C. P.: Efficient Signature Generation by Smart Cards. J. of Cryptology, 4,3 (1991) 161–174zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Tatsuaki Okamoto
    • 1
  1. 1.NTT LaboratoriesNippon Telegraph and Telephone CorporationYokosuka-shi, Kanagawa-kenJapan

Personalised recommendations