Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Cryptology
Published in: Journal of Cryptology 2/2017

14-01-2016

Security of Blind Signatures Revisited

Authors: Dominique Schröder, Dominique Unruh

Published in: Journal of Cryptology | Issue 2/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We revisit the security definitions of blind signatures as proposed by Pointcheval and Stern (J Cryptol 13(3):361–396, 2000). Security comprises the notions of one-more unforgeability, preventing a malicious user to generate more signatures than requested, and of blindness, averting a malicious signer to learn useful information about the user’s messages. Although this definition is well established nowadays, we show that there are still desirable security properties that fall outside of the model. More precisely, in the original unforgeability definition is not excluded that an adversary verifiably uses the same message m for signing twice and is then still able to produce another signature for a new message \(m'\ne m\). Intuitively, this should not be possible; yet, it is not captured in the original definition, because the number of signatures equals the number of requests. We thus propose a stronger notion, called honest-user unforgeability, that covers these attacks. We give a simple and efficient transformation that turns any unforgeable blind signature scheme (with deterministic verification) into an honest-user unforgeable one.
previous article Secret-Sharing for NP
next article The Security of Tandem-DM in the Ideal Cipher Model

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
More precisely, \(\mathsf {KG}\) and \(\mathsf {Vf}\) run in polynomial-time in the total length of their inputs. The total running time of \(\mathcal {S}\) is polynomial in the total length of its input \((\textit{sk})\) plus the total length of its incoming messages. The total running time of \(\mathcal {U}\) is polynomial in the total length of its input \((\textit{pk},m)\). (But the running time of \(\mathcal {U}\) may not depend on its incoming messages.) The asymmetry between the running time of \(\mathcal {S}\) and \(\mathcal {U}\) is necessary to ensure that (a) an interaction between \(\mathcal {U}\) and \(\mathcal {S}\) always runs in polynomial-time, and that (b) the running time of \(\mathcal {S}\) may depend on the length of the message m that only \(\mathcal {U}\) has in its input.
 
2
Completeness is actually necessary to show this lemma: For example, let \(\mathsf {BS}'\) be a scheme derived from a complete and strongly unforgeable scheme \(\mathsf {BS}\) in the following way: All machines except for the user are the same in \(\mathsf {BS}\) and \(\mathsf {BS}'\). When the user \(\mathcal {U}'\) should sign a message m, he signs \(m+1\) instead. Since the user does not occur in the definition of strong unforgeability, the strong unforgeability of \(\mathsf {BS}\) implies the strong unforgeability of \(\mathsf {BS}'\). Yet \(\mathsf {BS}'\) is not strongly honest-user unforgeable: By performing a signature query for m from the user \(\mathcal {U}'\), the adversary can get a valid signature for \(m+1\).
 
3
Without loss of generality, we assume that the public key \(\textit{pk}\) can efficiently be computed from the secret key \(\textit{sk}\).
 
4
Notice that one could weaken the requirement and only require that two invocations of the verification algorithm output the same value with overwhelming probability.
 
Literature
1.
M. Abe, A secure three-move blind signature scheme for polynomially many signatures, in Birgit Pfitzmann, editor, Advances in Cryptology—EUROCRYPT 2001, vol. 2045 of Lecture Notes in Computer Science, Innsbruck, Austria, May 6–10 (Springer, Berlin, 2001), pp. 136–151
2.
M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, M. Ohkubo, Structure-preserving signatures and commitments to group elements, in Tal Rabin, editor, Advances in Cryptology—CRYPTO 2010, vol. 6223 of Lecture Notes in Computer Science, Santa Barbara, CA, USA, August 15–19, (Springer, Berlin, 2010), pp. 209–236
3.
M. Abdalla, C. Namprempre, G. Neven, On the (im)possibility of blind message authentication codes, in David Pointcheval, editor, Topics in Cryptology—CT-RSA 2006, vol. 3860 of Lecture Notes in Computer Science, San Jose, CA, USA, February 13–17, (Springer, Berlin, 2006), pp. 262–279
4.
M. Abe, M. Ohkubo, A framework for universally composable non-committing blind signatures, in Mitsuru Matsui, editor, Advances in Cryptology—ASIACRYPT 2009, vol. 5912 of Lecture Notes in Computer Science, Tokyo, Japan, December 6–10, (Springer, Berlin, 2009), pp. 435–450
5.
N. Asokan, V. Shoup, M. Waidner, Optimistic fair exchange of digital signatures (extended abstract), in Kaisa Nyberg, editor, Advances in Cryptology—EUROCRYPT’98, vol. 1403 of Lecture Notes in Computer Science, Espoo, Finland, May 31 – June 4, (Springer, Berlin, 1998), pp. 591–606
6.
7.
M. Bellare, C. Namprempre, D. Pointcheval, M. Semanko, The one-more-RSA-inversion problems and the security of Chaum’s blind signature scheme. J. Cryptol., 16(3):185–215 (2003)
8.
A. Boldyreva, Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme, in Yvo Desmedt, editor, PKC 2003: 6th International Workshop on Theory and Practice in Public Key Cryptography, volume 2567 of Lecture Notes in Computer Science, Miami, USA, January 6–8, (Springer, Berlin, 2003), pp. 31–46
9.
10.
S.A. Brands, Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy, (MIT Press, Cambridge, 2000)
11.
J. Camenisch, T. Groß, Efficient attributes for anonymous credentials, in Peng Ning, Paul F. Syverson, Somesh Jha, editors, ACM CCS 08: 15th Conference on Computer and Communications Security, Alexandria, Virginia, USA, October 27–31, (ACM Press, New York, 2008), pp. 345–356
12.
D. Chaum, Blind signatures for untraceable payments, in David Chaum, Ronald L. Rivest, Alan T. Sherman, editors, Advances in Cryptology—CRYPTO’82, Santa Barbara, CA, USA, (Plenum Press, New York, 1982), pp. 199–203
13.
D. Chaum, Blind signature system, in David Chaum, editor, Advances in Cryptology—CRYPTO’83, Santa Barbara, CA, USA, (Plenum Press, New York, 1983), p. 153
14.
J. Camenisch, M. Koprowski, B. Warinschi, Efficient blind signatures without random oracles, in Carlo Blundo and Stelvio Cimato, editors, SCN 04: 4th International Conference on Security in Communication Networks, vol. 3352 of Lecture Notes in Computer Science, Amalfi, Italy, September 8–10, (Springer, Berlin, 2004), pp. 134–148
15.
J. Camenisch, G, Neven, A. Shelat, Simulatable adaptive oblivious transfer, in Moni Naor, editor, Advances in Cryptology—EUROCRYPT 2007, vol. 4515 of Lecture Notes in Computer Science, Barcelona, Spain, May 20–24, (Springer, Berlin, 2007), pp. 573–590
16.
M. Fischlin, Round-optimal composable blind signatures in the common reference string model, in Cynthia Dwork, editor, Advances in Cryptology—CRYPTO 2006, vol. 4117 of Lecture Notes in Computer Science, Santa Barbara, CA, USA, August 20–24, (Springer, Berlin, 2006), pp. 60–77
17.
M. Fischlin, D. Schröder, Security of blind signatures under aborts, in Stanislaw Jarecki and Gene Tsudik, editors, PKC 2009: 12th International Conference on Theory and Practice of Public Key Cryptography, vol. 5443 of Lecture Notes in Computer Science, Irvine, CA, USA, March 18–20, (Springer, Berlin, 2009), pp. 297–316
18.
M. Fischlin, D. Schröder, On the impossibility of three-move blind signature schemes, in Henri Gilbert, editor, Advances in Cryptology—EUROCRYPT 2010, vol. 6110 of Lecture Notes in Computer Science, French Riviera, May 30 – June 3, (Springer, Berlin, 2010), pp. 197–215
19.
G. Fuchsbauer, Automorphic signatures in bilinear groups and an application to round-optimal blind signatures. Cryptology ePrint Archive, Report 2009/320, 2009. http://​eprint.​iacr.​org/​.
20.
S. Garg, D. Gupta, Efficient round optimal blind signatures, in Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology—EUROCRYPT 2014, vol. 8441 of Lecture Notes in Computer Science, Copenhagen, Denmark, May 11–15, (Springer, Berlin, 2014), pp. 477–495
21.
J.A. Garay, P.D. MacKenzie, M. Prabhakaran, K. Yang, Resource fairness and composability of cryptographic protocols, in Shai Halevi and Tal Rabin, editors, TCC 2006: 3rd Theory of Cryptography Conference, vol. 3876 of Lecture Notes in Computer Science, New York, NY, USA, March 4–7, (Springer, Berlin, 2006) pp. 404–428
22.
S. Garg, V. Rao, A. Sahai, D. Schröder, D. Unruh, Round optimal blind signatures, in Advances in Cryptology—CRYPTO 2011—31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14–18, 2011. Proceedings, vol. 6841 of Lecture Notes in Computer Science, (Springer, Berlin, 2011), pp. 630–648
23.
24.
O. Goldreich, The Foundations of Cryptography, vol. 2 (Cambridge University Press, New York, NY, 2004).
25.
O. Horvitz, J. Katz, Universally-composable two-party computation in two rounds, in Alfred Menezes, editor, Advances in Cryptology—CRYPTO 2007, vol. 4622 of Lecture Notes in Computer Science, Santa Barbara, CA, USA, August 19–23, (Springer, Berlin, 2007), pp. 111–129
26.
C. Hazay, J. Katz, C.-Y. Koo, Y. Lindell, Concurrently-secure blind signatures without random oracles or setup assumptions, in Salil P. Vadhan, editor, TCC 2007: 4th Theory of Cryptography Conference, vol. 4392 of Lecture Notes in Computer Science, Amsterdam, The Netherlands, February 21–24, (Springer, Berlin, 2007), pp. 323–341
27.
A. Juels, M. Luby, R. Ostrovsky, Security of blind digital signatures (extended abstract), in Burton S. Kaliski Jr., editor, Advances in Cryptology—CRYPTO’97, vol. 1294 of Lecture Notes in Computer Science, Santa Barbara, CA, USA, August 17–21, (Springer, Berlin, 1997), pp. 150–164
28.
A. Kiayias, H.-S. Zhou, Equivocal blind signatures and adaptive UC-security, in Ran Canetti, editor, TCC 2008: 5th Theory of Cryptography Conference, vol. 4948 of Lecture Notes in Computer Science, San Francisco, CA, USA, March 19–21, (Springer, Berlin, 2008), pp. 340–355
29.
30.
T. Okamoto, Efficient blind and partially blind signatures without random oracle, in Shai Halevi and Tal Rabin, editors, TCC 2006: 3rd Theory of Cryptography Conference, vol. 3876 of Lecture Notes in Computer Science, New York, NY, USA, March 4–7, (Springer, Berlin, 2006), pp. 80–99
31.
D. Pointcheval, J. Stern, Security arguments for digital signatures and blind signatures. J. Cryptol., 13(3):361–396 (2000)
32.
M. Rückert, Lattice-based blind signatures, in Masayuki Abe, editor, Advances in Cryptology—ASIACRYPT 2010, vol. 6477 of Lecture Notes in Computer Science, Singapore, December 5–9, (Springer, Berlin, 2010), pp. 413–430
33.
Metadata
Title
Security of Blind Signatures Revisited
Authors
Dominique Schröder
Dominique Unruh
Publication date
14-01-2016
Publisher
Springer US
Published in
Journal of Cryptology / Issue 2/2017
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-015-9225-1

Other articles of this Issue 2/2017

Journal of Cryptology 2/2017 Go to the issue

OriginalPaper

Jacobian Coordinates on Genus 2 Curves

OriginalPaper

The Security of Tandem-DM in the Ideal Cipher Model

OriginalPaper

Design Methodology and Validity Verification for a Reactive Countermeasure Against EM Attacks

OriginalPaper

Efficient Cryptosystems From -th Power Residue Symbols

OriginalPaper

Acoustic Cryptanalysis

OriginalPaper

Secret-Sharing for NP

Premium Partner

    Image Credits