Efficient Round Optimal Blind Signatures
Known constructions of blind signature schemes suffer from at least one of the following limitations: (1) rely on parties having access to a common reference string or a random oracle, (2) are not round-optimal, or (3) are prohibitively expensive.
- PDF / 349,519 Bytes
- 19 Pages / 439.363 x 666.131 pts Page_size
- 33 Downloads / 192 Views
Abstract. Known constructions of blind signature schemes suffer from at least one of the following limitations: (1) rely on parties having access to a common reference string or a random oracle, (2) are not roundoptimal, or (3) are prohibitively expensive. In this work, we construct the first blind-signature scheme that does not suffer from any of these limitations. In other words, besides being round optimal and having a standard model proof of security, our scheme is very efficient. Specifically, in our scheme, one signature is of size 6.5 KB and the communication complexity of the signing protocol is roughly 100 KB. An amortized variant of our scheme has communication complexity less that 1 KB.
1
Introduction
Blind signatures, introduced by Chaum [10], allow users to obtain signatures on messages of their choice without revealing the messages itself to the signer. Additionally, the blind signature scheme should satisfy unforgeability, i.e. no user can produce additional signatures on messages without interacting with the signer. Blind signatures have widespread applications such as e-cash, e-voting, and anonymous credentials. Even after 30 years of research, and with 50+ candidate schemes in the literature, the state of the art is not completely satisfactory. Essentially, all schemes in the literature can be partitioned into two categories – (1) the schemes that rely on a random oracle or a setup, or (2) the schemes which are round inefficient. Examples of constructions argued to be secure using the random oracle methodology [7] include [26,27,25,1,5,8] and using a setup such as a shared random string include [4,3,11,13,21,23,22]. On the other hand, essentially all schemes that avoid the use of the random oracle methodology or a setup [20,9,23,19] are not round optimal. The only scheme that does not fall in the above two categories is the recent construction of Garg et al. [16]. Unfortunately, this scheme is prohibitively expensive. For example, the communication complexity of this protocol is a
Research conducted while at the IBM Research, T.J.Watson funded by NSF Grant No.1017660.
P.Q. Nguyen and E. Oswald (Eds.): EUROCRYPT 2014, LNCS 8441, pp. 477–495, 2014. c International Association for Cryptologic Research 2014
478
S. Garg and D. Gupta
Table 1. Comparing the Efficiency of Different Round Optimal Blind Signature Schemes. κ is the security parameter of the scheme. > 1 is an appropriate constant. The concrete parameters above correspond to the setting for 80 bits of security. Scheme
Communication Asymptotic Garg et al. [16] poly(κ) DLIN (This work) O(κ1+ ) Amortized (This work) O(κ ) q-SFP (This work) O(κ1+ ) Amortized (This work) O(κ )
Complexity Signature Size Concrete Asymptotic small2 100.6KB O(κ ) 836 Bytes O(κ ) 100.2KB O(κ ) 472 bytes O(κ )
Concrete 6.5KB 6.5KB 3.2KB 3.2KB
large polynomial in the security parameter1. In this work, we ask the following question: Can we construct a very efficient round optimal blind signature scheme without relying on a random oracle or a setup? 1.1
Our Re
Data Loading...
