Abstract
Demonstrating in zero-knowledge the possession of digital signatures has many cryptographic applications such as anonymous authentication, identity escrow, publicly verifiable secret sharing and group signature. This paper presents a general construction of zero-knowledge proof of possession of digital signatures. An implementation is shown for discrete logarithm settings. It includes protocols of proving exponentiation and modulo operators, which are the most interesting operators in digital signatures. The proposed construction is applicable for ElGamal signature scheme and its variations. The construction also works for the RSA signature scheme. In discrete logarithm settings, our technique is O(l) times more efficient than previously known methods.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Asokan, N., Shoup, V., Waidner, M.: Optimistic fair exchange of digital signatures. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 591–606. Springer, Heidelberg (1998)
Brands, S.: Untraceable off-line cash based on the representation problem, Technical Report CS-R9323, Centrum voor Wiskunde en Informatica (April 1993)
Brands, S.: Rapid Demonstration of Linear Relations Connected by Boolean Operators. In: Pelillo, M., Hancock, E.R. (eds.) EMMCVPR 1997. LNCS, vol. 1223, pp. 318–333. Springer, Heidelberg (1997)
Camenisch, J., Michels, M.: Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 107. Springer, Heidelberg (1999); BRICS Technical Report RS-98-29
Camenisch, J., Stadler, M.: Efficient Group Signatures for Large Groups. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 465–479. Springer, Heidelberg (1997)
Chan, A., Frankel, Y., Tsiounis, T.: Easy come-easy go divisible cash. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 561–575. Springer, Heidelberg (1998)
Chaum, D., van Heijst, E., Pfitzmann, B.: Cryptographically Strong Undeniable Signature, Unconditionally Secure for the Signer. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 204–212. Springer, Heidelberg (1992)
Chaum, D., Pedersen, T.P.: Wallet databases with observers. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 89–105. Springer, Heidelberg (1993)
Cramer, R., Damgard, I.: Zero-Knowledge Proofs for Finite Field Arithmetic or: Can Zero-Knowledge be for Free? In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, p. 424. Springer, Heidelberg (1998) (to appear)
Cramer, R., Shoup, V.: A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, p. 13. Springer, Heidelberg (1998) (to appear)
Damgard, I.: Practical and Provably Secure Release of a Secret and Exchanges of Signatures. Journal of Cryptology 8(4), 201–222 (1995)
Di Crescenzo, G., Okamoto, T., Yung, M.: Keeping the SZK-Verifier Honest Un conditionally. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 31–45. Springer, Heidelberg (1997)
ElGamal, T.: A Public-Key Cryptosystem and a Signature Scheme Based on Di-screte Logarithms. IEEE Transactions on Information Theory IT-31(4), 469–472 (1985)
Feige, U., Fiat, A., Shamir, A.: Zero-knowledge proofs of Identity. Journal of Cryptology 1, 77–94 (1988)
Fujisaki, E., Okamoto, T.: Statistical Zero-Knowledge Protocols to Prove Modular Polynomial Relations. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 16–30. Springer, Heidelberg (1997)
Goldreich, O., Micali, S., Wigderson, A.: Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design. In: Proceedings of Foundation of Computer Science 1986, pp. 174–187 (1986)
Kilian, J., Petrank, E.: Identity Escrow. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, p. 169. Springer, Heidelberg (1998)
National Institute of Standards and Technology, NIST FIPS PUB 186, Digital Signature Standard, US Department of Commerce (May 1994)
Menezes, A., van Oorschot, P., Vanstone, S.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1997)
Nyberg, K., Rueppel, R.A.: Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 182–193. Springer, Heidelberg (1995)
Okamoto, T.: An efficient divisible electronic cash scheme. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 438–451. Springer, Heidelberg (1995)
Pedersen, T.: Non-Interactive and Information Theoretic Secure Verifiable Secret Sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992)
Schneider, B.: Applied Cryptography, 2nd edn. John Wiley & Sons, Inc., Chichester (1996)
Schnorr, C.: Efficient Signature Generation for Smart Cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, Heidelberg (1990)
Stadler, M.: Publicly Verifiable Secret Sharing. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 190–199. Springer, Heidelberg (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nguyen, K.Q., Bao, F., Mu, Y., Varadharajan, V. (1999). Zero-Knowledge Proofs of Possession of Digital Signatures and Its Applications. In: Varadharajan, V., Mu, Y. (eds) Information and Communication Security. ICICS 1999. Lecture Notes in Computer Science, vol 1726. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-47942-0_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-47942-0_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66682-0
Online ISBN: 978-3-540-47942-0
eBook Packages: Springer Book Archive