Privacy for Private Key in Signatures | SpringerLink
Skip to main content
Springer Nature Link
Log in

Privacy for Private Key in Signatures

  • Conference paper
Information Security and Cryptology (Inscrypt 2008)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 5487))

Included in the following conference series:

Abstract

One of the important applications of digital signature is anonymous credential or pseudonym system. In these scenarios, it is essential that the identity of the signer is kept secret from any third party, except the trusted authority. The identity in such a system is uniquely identified by the secret key (or the signing key) rather than the public key, since the public key may be repeatedly randomized. This paper formalizes this notion by investigating a new property of digital signatures, called key indistinguishability. In this notion, given a number of digital signatures generated from two known public keys, an adversary cannot determine whether the signing keys used to generate these public keys, and hence the signatures, are the same. This property ensures that the signatures do not leak any information of the signing keys. Observing that existing digital signatures without random oracles do not provide such a property, we fill the gap with the first key indistinguishable signature scheme which is existentially unforgeable under a chosen message attack without using random oracles. The proposed scheme is also efficient and practical for applications in pseudonym systems.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Abadi, M., Rogaway, P.: Reconciling Two Views of Cryptography (The Computational Soundness of Formal Encryption). In: Watanabe, O., Hagiya, M., Ito, T., van Leeuwen, J., Mosses, P.D. (eds.) TCS 2000. LNCS, vol. 1872, pp. 3–22. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  2. Ateniese, G., Camenisch, J., de Medeiros, B.: Untraceable RFID Tags via Insubvertible Encryption. In: Meadows, C. (ed.) ACM CCS 2005, pp. 92–101. ACM Press, New York (2005)

    Google Scholar 

  3. Ballard, L., Green, M., de Medeiros, B., Monrose, F.: Correlation-resistant Storage. Technical Report TR-SP-BGMM-050705, Johns Hopkins University (2005), http://spar.isi.jhu.edu/~mgreen/correlation.pdf

  4. Bellare, M., Boldyreva, A., Desai, A., Pointcheval, D.: Key-privacy in public-key encryption. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 566–582. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  5. Bellare, M., Rogaway, P.: Optimal Asymmetric Encryption-How to Encrypt with RSA. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995)

    Chapter  Google Scholar 

  6. Boneh, D., Boyen, X.: Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  7. Boneh, D., Boyen, X.: Short Signatures Without Random Oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56–73. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  8. Boneh, D., Lynn, B., Shacham, H.: Short Signatures from the Weil Pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  9. Brickell, E., Camenisch, J., Chen, L.: Direct Anonymous Attestation. In: Pfitzmann, B. (ed.) ACM CCS 2004, pp. 132–145. ACM Press, New York (2004)

    Google Scholar 

  10. Camenisch, J.L., Lysyanskaya, A.: Signature Schemes and Anonymous Credentials from Bilinear Maps. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 56–72. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  11. Chaum, D., van Heyst, E.: Group signatures. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 257–265. Springer, Heidelberg (1991)

    Chapter  Google Scholar 

  12. 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, pp. 13–25. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  13. Desai, A.: The Security of All-or-Nothing Encryption: Protecting against Exhaustive Key Search. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 359–375. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  14. ElGamal, T.: A Public Key Cryptosystem and Signature Scheme Based on Discrete Logarithms. IEEE Transaction on Information Theory 31, 467–472 (1985)

    MathSciNet  MATH  Google Scholar 

  15. Fischlin, M.: Pseudorandom Function Tribe Ensembles Based on One-Way Permutations: Improvements and Applications. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 432–445. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  16. Fischlin, M.: The Cramer-Shoup Strong-RSASignature Scheme Revisited. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 116–129. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  17. Galbraith, S.-D., Rotger, V.: Easy Decision Diffie-Hellman Groups. Journal of Computation and Mathematics 7, 201–218 (2004)

    MathSciNet  MATH  Google Scholar 

  18. Gennaro, R., Halevi, S., Rabin, T.: Secure Hash-and-Sign Signatures without the Random Oracle. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 123–139. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  19. Goldwasser, S., Micali, S., Rivest, R.: A Digital Signature Scheme Secure against Adaptive Chosen-message Attacks. SIAM J. Computing 17(2), 281–308 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  20. Halevi, S.: A Sufficient Condition for Key-privacy. Technique report (2005), http://eprint.iacr.org/

  21. Lysyanskaya, A., Rivest, R.L., Sahai, A., Wolf, S.: Pseudonym Systems. In: Heys, H.M., Adams, C.M. (eds.) SAC 1999. LNCS, vol. 1758, pp. 184–199. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  22. Miyaji, A., Nakabayashi, M., Takano, S.: New Explicit Conditions of Elliptic Curves for FR-reduction. IEICE Transactions on Fundamentals E84-A(5), 1234–1243 (2001)

    MATH  Google Scholar 

  23. Rivest, R.L., Shamir, A., Tauman, Y.: How to Leak a Secret. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 552–565. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  24. Schnorr, C.-P.: Efficient Identification and Signatures for Smart Cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, Heidelberg (1990)

    Google Scholar 

  25. Verheul, E.R.: Evidence that XTR Is More Secure than Supersingular Elliptic Curve Cryptosystems. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 195–210. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  26. Wu, Q., Qin, B., Mu, Y., Susilo, W.: Privacy for Private Key in Signatures. Full version (2009), http://eprint.iacr.org/

  27. Yang, G., Wong, D., Deng, X., Wang, H.: Anonymous Signature Schemes. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 347–363. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer, Wuhan University, Wuhan City, China

    Qianhong Wu

  2. Department of Mathematics, School of Science, Xi’an University of Technology, Xi’an, China

    Bo Qin

  3. Department of Computer Engineering and Mathematics, Universitat Rovira i Virgili, Tarragona, Spain

    Qianhong Wu & Bo Qin

  4. Center for Computer and Information Security Research School of Information Technology and Computer Science, University of Wollongong, Wollongong, NSW 2522, Australia

    Qianhong Wu, Bo Qin, Yi Mu & Willy Susilo

Authors
  1. Qianhong Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bo Qin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yi Mu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Willy Susilo
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Computer Science Department, Google Inc. and Columbia University, Room 464, S.W. Mudd Building, 10027, New York, NY, USA

    Moti Yung

  2. College of Information Sciences and Technology, Pennsylvania State University, PA 16802, University Park, USA

    Peng Liu

  3. SKLOIS, Institute of Software, Chinese Academy of Sciences, 100080, Beijing, China

    Dongdai Lin

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Wu, Q., Qin, B., Mu, Y., Susilo, W. (2009). Privacy for Private Key in Signatures. In: Yung, M., Liu, P., Lin, D. (eds) Information Security and Cryptology. Inscrypt 2008. Lecture Notes in Computer Science, vol 5487. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01440-6_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-01440-6_9

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-01439-0

  • Online ISBN: 978-3-642-01440-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics