Abstract
We show a new protocol for blind signatures in which security is preserved even under arbitrarily-many concurrent executions. The protocol can be based on standard cryptographic assumptions and is the first to be proven secure in a concurrent setting (under any assumptions) without random oracles or a trusted setup assumption such as a common reference string. Along the way, we also introduce new definitions of security for blind signature schemes.
This research was supported by US-Israel Binational Science Foundation grant #2004240. Work of the first author was also supported by an Eshkol fellowship from the Israel Ministry of Science and Technology. Work of the second author was also supported by NSF CAREER award #0447075.
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
Abe, M.: A Secure Three-Move Blind Signature Scheme for Polynomially-Many Signatures. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, Springer, Heidelberg (2001)
Abdalla, M., Namprempre, C., Neven, G.: On the (Im)possibility of Blind Message Authentication Codes. CT-RSA 2006 (2006)
Barak, B., Canetti, R., Nielsen, J.B., Pass, R.: Universally Composable Protocols with Relaxed Set-Up Assumptions. In: FOCS 2004 (2004)
Barak, B., Sahai, A.: How To Play Almost Any Mental Game Over The Net — Concurrent Composition via Super-Polynomial Simulation. In: FOCS 2005 (2005)
Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The One-More-RSA-Inversion Problems and the Security of Chaum’s Blind Signature Scheme. J. Cryptology 16(3), 185–215 (2003)
Bellare, M., Rogaway, P.: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In: ACM CCCS ’93, ACM, New York (1993)
Blum, M.: How to Prove a Theorem so No One Else Can Claim It. In: Proceedings of the International Congress of Mathematicians, pp. 1444–1451 (1986)
Boldyreva, A.: Efficient Threshold Signatures, Multisignatures, and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme. In: PKC 2003 (2003)
Camenisch, J., Koprowski, M., Warinschi, B.: Efficient Blind Signatures without Random Oracles. In: SCN 2004 (2004)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally Composable Two-Party and Multi-Party Secure Computation. In: STOC 2002 (2002)
Chaum, D.: Blind Signatures for Untraceable Payments. In: Crypto ’82 (1982)
Damgård, I.: Payment Systems and Credential Mechanisms with Provable Security against Abuse by Individuals. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, Springer, Heidelberg (1990)
Damgård, I., Nielsen, J.B.: Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, Springer, Heidelberg (2002)
Dwork, C., Naor, M.: Zaps and Their Applications. In: FOCS 2002 (2000)
Feige, U., Shamir, A.: Zero-Knowledge Proofs of Knowledge in Two Rounds. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, Springer, Heidelberg (1990)
Fischlin, M.: Round-Optimal Composable Blind Signatures in the Common Reference String Model. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, Springer, Heidelberg (2006)
Goldreich, O.: Foundations of Cryptography, vol. 1: Basic Tools. Cambridge University Press, Cambridge (2001)
Goldwasser, S., Micali, S., Rivest, R.: A Digital Signature Scheme Secure against Adaptive Chosen-Message Attacks. SIAM J. Computing 17(2), 281–308 (1988)
Juels, A., Luby, M., Ostrovsky, R.: Security of Blind Digital Signatures. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, Springer, Heidelberg (1997)
Kalai, Y., Lindell, Y., Prabhakaran, M.: Concurrent General Composition of Secure Protocols in the Timing Model. In: STOC 2005 (2005)
Kiayias, A., Zhou, H.-S.: Two-Round Concurrent Blind Signatures without Random Oracles. In: SCN 2006 (2006)
Lindell, Y.: Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation. J. Cryptology 16(3), 143–184 (2003)
Lindell, Y.: Bounded-Concurrent Secure Two-Party Computation without Setup Assumptions. In: STOC 2003 (2003)
Lindell, Y.: Lower Bounds for Concurrent Self-Composition. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, Springer, Heidelberg (2004)
Micali, S., Pass, R., Rosen, A.: Input-Indistinguishable Computation. In: FOCS 2006 (2006)
Okamoto, T.: Efficient Blind and Partially Blind Signatures without Random Oracles. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, Springer, Heidelberg (2006)
Pointcheval, D.: Strengthened Security for Blind Signatures. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, Springer, Heidelberg (1998)
Pointcheval, D., Stern, J.: Provably Secure Blind Signature Schemes. In: Kim, K.-c., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, Springer, Heidelberg (1996)
Pointcheval, D., Stern, J.: Security Arguments for Digital Signatures and Blind Signatures. J. Cryptology 13(3), 361–396 (2000)
Prabhakaran, M., Rosen, A., Sahai, A.: Concurrent Zero Knowledge with Logarithmic Round-Complexity. In: FOCS 2002 (2002)
Prabhakaran, M., Sahai, A.: New Notions of Security: Achieving Universal Composability without Trusted Setup. In: STOC 2004 (2004)
Rosen, A.: Concurrent Zero-Knowledge. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Hazay, C., Katz, J., Koo, CY., Lindell, Y. (2007). Concurrently-Secure Blind Signatures Without Random Oracles or Setup Assumptions. In: Vadhan, S.P. (eds) Theory of Cryptography. TCC 2007. Lecture Notes in Computer Science, vol 4392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70936-7_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-70936-7_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70935-0
Online ISBN: 978-3-540-70936-7
eBook Packages: Computer ScienceComputer Science (R0)