Abstract
We build concurrently executable blind signatures schemes in the common reference string model, based on general complexity assumptions, and with optimal round complexity. Namely, each interactive signature generation requires the requesting user and the issuing bank to transmit only one message each. We also put forward the definition of universally composable blind signature schemes, and show how to extend our concurrently executable blind signature protocol to derive such universally composable schemes in the common reference string model under general assumptions. While this protocol then guarantees very strong security properties when executed within larger protocols, it still supports signature generation in two moves.
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, pp. 136–151. Springer, Heidelberg (2001)
Abe, M., Fujisaki, E.: How to Date Blind Signatures. In: Kim, K.-c., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 244–251. Springer, Heidelberg (1996)
Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The One-More-RSA-Inversion Problems and the Security of Chaum’s Blind Signature Scheme. Journal of Cryptology 16(3), 185–215 (2003)
Boldyreva, A.: Efficient Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 31–46. Springer, Heidelberg (2002)
Canetti, R.: Universally Composable Security: A new Paradigm for Cryptographic Protocols. In: Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS) 2001. IEEE Computer Society Press, Los Alamitos (2001), eprint.iacr.org
Canetti, R.: On Universally Composable Notions of Security for Signature, Certification and Authentication. In: Proceedings of Computer Security Foundations Workshop (CSFW) 2004. IEEE Computer Society Press, Los Alamitos (2004); an updated version see, eprint.iacr.org
Canetti, R., Fischlin, M.: Universally Composable Commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19–40. Springer, Heidelberg (2001)
Chaum, D.: Blind Signatures for Untraceable Payments. In: Advances in Cryptology 1981 - 1997, pp. 199–203. Plemum, New York (1983)
Camenisch, J.L., Koprowski, M., Warinschi, B.: Efficient Blind Signatures Without Random Oracles. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 134–148. Springer, Heidelberg (2005)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally Composable Two-Party and Multi-Party Secure Computation. In: Proceedings of the Annual Symposium on the Theory of Computing (STOC) 2002, pp. 494–503. ACM Press, New York (2002)
De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., Sahai, A.: Robust Non-interactive Zero Knowledge. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 566–598. Springer, Heidelberg (2001)
Damgard, I., Groth, J.: Non-interactive and Reusable Non-Malleable Commitment Schemes. In: Proceedings of the Annual Symposium on the Theory of Computing (STOC) 2003, pp. 426–437. ACM Press, New York (2003)
De Santis, A., Persiano, G.: Zero-Knowledge Proofs of Knowledge Without Interaction. In: Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS) 1992, pp. 427–436. IEEE Computer Society Press, Los Alamitos (1992)
Fischlin, M.: Round-Optimal Composable Blind Signatures in the Common Reference String Model (full version) (2006), Available at: www.fischlin.de
Feige, U., Lapidot, D., Shamir, A.: Multiple NonInteractive Zero Knowledge Proofs Under General Assumption. SIAM Journal on Computing 29(1), 1–28 (1999)
Håstad, J., Impagliazzo, R., Levin, L., Luby, M.: A Pseudorandom Generator from any One-way Function. SIAM Journal on Computing 28(4), 1364–1396 (1999)
Juels, A., Luby, M., Ostrovsky, R.: Security of Blind Digital Signatures. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 150–164. Springer, Heidelberg (1997)
Kiayias, A., Hong-Sheng, Z.: Two-Round Concurrent Blind Signatures without Random Oracles. Number 2005/435 in Cryptology eprint archive (2005), eprint.iacr.org
Lindell, Y.: Bounded-Concurrent Secure Two-Party Computation Without Setup Assumptions. In: Proceedings of the Annual Symposium on the Theory of Computing (STOC) 2003, pp. 683–692. ACM Press, New York (2003)
Lindell, Y.: Lower Bounds for Concurrent Self Composition. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 203–222. Springer, Heidelberg (2004)
Lepinski, M., Micali, S., Shelat, A.: Fair-zero knowledge. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 245–263. Springer, Heidelberg (2005)
Naor, M.: Bit Commitment Using Pseudo-Randomness. Journal of Cryptology 4(2), 151–158 (1991)
Naor, M., Yung, M.: Universal One-Way Hash Functions and Their Cryptographic Applications. In: Proceedings of the Annual Symposium on the Theory of Computing (STOC) 1989, pp. 33–43. ACM Press, New York (1989)
Okamoto, T.: Efficient Blind and Partially Blind Signatures Without Random Oracles. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 80–99. Springer, Heidelberg (2006)
Pointcheval, D.: Strengthened Security for Blind Signatures. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 391–405. Springer, Heidelberg (1998)
Pointcheval, D., Stern, J.: Security Arguments for Digital Signatures and Blind Signatures. Journal of Cryptology 13(3), 361–396 (2000)
Rompel, J.: One-Way Functions are Necessary and Sufficient for Secure Signatures. In: Proceedings of the Annual Symposium on the Theory of Computing (STOC) 1999, pp. 387–394. ACM Press, New York (1990)
Sahai, A.: Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security. In: Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS) 1999. IEEE Computer Society Press, Los Alamitos (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fischlin, M. (2006). Round-Optimal Composable Blind Signatures in the Common Reference String Model. In: Dwork, C. (eds) Advances in Cryptology - CRYPTO 2006. CRYPTO 2006. Lecture Notes in Computer Science, vol 4117. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11818175_4
Download citation
DOI: https://doi.org/10.1007/11818175_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37432-9
Online ISBN: 978-3-540-37433-6
eBook Packages: Computer ScienceComputer Science (R0)