Keywords

1 Introduction

Since the creation of the Internet, physical cash is progressively replaced through digitization by electronic payments methods like smart card or phone using NFC technology. Within this transformation, specific properties of cash were lost such as anonymity or unlinkability of the customer. In 1982, D. Chaum introduced a cryptographic response to this problem, called blind signature [13]. He described this concept as an analogue of an envelope composed of carbon paper that could be signed from the outside where the signature is engraved on a message inside.

For a concrete example, consider the following case where blind signature is helpful. Suppose that a customer wishes to buy a product at 10 in a store. It asks to its bank a (blind) signature which is worth 10Footnote 1. The customer then gives this signature to the shopkeeper against the 10 worth product. The latter sends the signature back to the bank for payment. In this setting double spending is checked by the bank since each payment corresponds to a signature. Moreover, unlinkability is ensured since the bank knows that the customer has withdrawn 10 but it cannot link it with the inquiry from the shopkeeper. Another well-known application for this primitive is the voting scheme in order to ensure that only registered voter can actually vote [42, 49].

One of the first scheme using blind signature was developed by D. Chaum, A. Fiat, M. Naor in 1988 [14]. In 1992, S. Von Solms and D. Naccache [80] described a hostage taking that could lead to a crime without possibility to trace down a ransom pay to the criminal through coins made of blind signatures. It shows the necessity to extend the definition of blind signature to give more power to the signer. The goal is to be able to apply blind signature without threat. Therefore, extensions of blind signature such as partially blind signature [3], signer-friendly blind signature, fair blind signature [71] and many others were developed. Those properties allow more control for the signer by adding information or putting constraints on the use of a signature.

Before 1994, factorization was the only hard problem that yield to blind signature. That year was a turnover for the domain, J.L. Camenisch et al. [12] introduced the first a blind signature scheme based on the discrete logarithm problem. This scheme was an adaptation of the Nyberg-Rueppel scheme [61] leading to a relatively efficient blind signature. This scheme was also the first blind signature to have an additional property: message recovery (signed message is recovered from the public key and the signature).

Following A. Shamir’s introduction of identity-based cryptography [68], signature and blind signature schemes were developed using this paradigm. The first ID-based blind signature was introduced by F. Zang and K. Kim [90] in 2002, only one year after the first use of pairing. In 2004, C. Sherman et al.[18] opened up the way to ID-based partially blind signature with a new scheme achieving partial restrictive blindness. The next year D. Galindo et al. [24] gave a general construction of \(\textsf{IDBS}\) only requiring a secure signature and a secure blind signature. This general framework achieved relatively good efficiency, but the signatures generated are about twice as large as a signature of made out schemes (the signature is the concatenation of both signature schemes).

There exist numerous properties proposed by a variety of \(\textsf{IDBS}\) schemes with the same practical applications as blind signature. Each situation has specific requirements and depending on the context one may use one schemes or another. Our main goal in this survey is to answer the question of how to choose an \(\textsf{IDBS}\) (with which property) for practical use. We list all existing schemes, classify them accordingly to their properties and security assumption; we also compare them using an empirical evaluation. We have included all \(\textsf{IDBS}\)Footnote 2 as they are for a vast majority independent works. Some does not meet the requirement to be use in practice, but we mention them for exhaustiveness as this may be of interest for authors trying to design new schemes. In such cases we have written the mentions “No reduction”, “No proof” or “Not formal” depending on the category the fall within. The authors do not recommend usage of any schemes with one of these mentions in the upcoming table. Their evaluation is not included as this would be irrelevant to compare them with scheme that have guaranteed security.

Contributions. Our contribution aims at bringing new considerations on \({\textsf{IDBS}}{}\). Our first contribution is a survey presenting the existing portfolio to someone seeking to implement these primitives. In this paper, we evaluate all existing \(\textsf{IDBS}\), this is not less than 71 schemes. We classify them within several categories that we discuss throughout this paper. Some reach additional properties that we all present in here. This allows us to give a full overview of the literature in the field and the existing properties reached by some existing \(\textsf{IDBS}\) scheme. We notice that among the existing schemes, some of them (at least 24 schemes) do not reach today’s security requirements as no formal security argument have been given by their authors or in the literature we have investigated. We point them out without going into further details on them. Scheme with existing security arguments are investigated further. We start by empirically evaluate the cost of all operations used in existing \(\textsf{IDBS}\) schemes. It allows us to establish a metric to evaluate the time efficiency of each part of the given signatures. This answers our goal i.e., obtaining a taxonomy of the reliable schemes in terms of efficiency and cryptographic assumption. This enables us to give insights on the schemes that actually reach the best efficiency in practice.

Seeking for more formalism and security consideration. The long version of this paper provides some formal security definitions for all type of the scheme we are investigating in this paper. These results are given in the appendix of the long version of the paper [5]. We hope it will bring up the security of the new ID-based blind signature that will be designed in the future or at least help giving some further formalization of their security as this has never been achieved for some of them.

Related Work. A few surveys related to blind signature schemes have been presented. To the best of the authors’ knowledge, we noticed three of them. The first one [6], gives an overview of 8 existing blind signature schemes and other notions that are directly related to blind signature. It also presents some properties of blind signatures. A second short paper called survey on \(\textsf{IDBS}\) was proposed in 2015 by Girish et al. [30], but it does not give insights on the existing schemes instead it presents the concept and some existing property without much formalism. In 2018, M. Khater et al. [48] compared some blind signatures based on ElGamal. Only 5 schemes derived from the well-known signature are presented and evaluated. They compare the influence of modification in the scheme parameters, such as the number of blinding factor and its influence on the complexity. We include their signatures in our Survey.

All the above cited works only offer a partial view of existing identity-based blind signature schemes and yet it is hard to get a realistic view of the state of the art of the existing literature. Moreover, they do not compare the performance of the schemes in the literature. Our objective is to present a full overview of the existing literature, while our achievement is a detailed taxonomy of all existing \(\textsf{IDBS}\) schemes and of the numerous sub-properties. Unlike the above cited papers, we ambition to be exhaustive and to give a full description of field of \({\textsf{IDBS}}\).

Outline: Section 2 introduces the security assumptions and the definitions of an ID-based blind signature schemes and its additional properties. Details about our evaluation process are given in Sect. 3. In Sect. 4.1, we are comparing the existing schemes. Finally, in Sect. 5 we give insights of some work that should be done to put forward the domain. In Sect. 6 we conclude our study.

2 Cryptographic Definitions

Blind signature schemes rely on hard mathematical problems for their security. Those assumptions should be well-studied, and assumed to be intractable in reasonable time. The Discrete Logarithm problem (DL) relies on the difficulty to compute the discrete logarithm of an element in some groups. The Decision Diffie-Hellman (DDH), Computational Diffie-Hellman (CDH), Gap Diffie-Hellman (GDH) and the Chosen Target Accompanied Computational Diffie-Hellman problems (CT-ACDH) [15] result directly from it. There are also some variants such as the q-Strong Diffie-Hellman (q-SDH), the k-Bilinear Diffie-Hellman Inversion (k-BDHI), the One-more Bilinear Diffie-Hellman Inversion (1m-BDHI) or the Collusion Attack Algorithm with k traitors (k-CAA). These problems are mostly used for schemes based on elliptic curves. Recently, a polynomial time (PT) algorithm was disclosed solving the Over-determined Solvable System of Linear Equations modulo q with Random inhomogeneity problem (ROS). This led to attacks on many schemes [8] and some \(\textsf{IDBS}\) were relying on it.

Alternatives to elliptic curves have been investigated aiming at post-quantum security. Those solutions are essentially based on lattices, notably the Short Integer Solution problem (SIS), the Shortest Vector problem (SV) and its variant on quotient ring the Ring Short Integer Solution problem (R-SIS). One last rather unusual problem that we need here is the Chebyshev Polynomial Computation problem (CPC) [73]. This problem is known to have a reduction to the discrete logarithm in a finite group GF(p), for some prime p [72]. These assumptions are formally defined in the long version of this paper [5]. All existing \({\textsf{IDBS}}\) are based on one of these problems, we formally introduce the concept of \(\textsf{IDBS}\) and informally present the multiple properties that have been put based on this definition.

Definition 1

(IDentity-based Blind Signature - \(\textsf{IDBS}\)). An \(\textsf{IDBS}\) with security parameter \(\mathfrak {K}\) is a 4-tuple of polynomial-time algorithms (\(\textsf{Setup}\), \(\textsf{Extract}\), \(\langle \mathcal {S},\mathcal {U}\rangle \), \(\textsf{Verif}\)) involving an authority \(\mathcal {M}\), a signer \(\mathcal {S}\) and a user \(\mathcal {U}\). Algorithms are as follows:

  • \(\textsf{Setup}(1^\mathfrak {K}) \xrightarrow {} (mpk, msk)\) calls \(\mathfrak {K}\) to generate a master key pair (mpk, msk).

  • \(\textsf{Extract}(msk, ID) \xrightarrow {} sk[ID]\) on input \(\mathcal {S}\)’s identity and a master key msk. It returns a secret key sk[ID] later sent to \(\mathcal {S}\) via a secure channel.

  • \(\langle \mathcal {S}(sk[ID]),\ \mathcal {U}(mpk, m, ID) \rangle \xrightarrow []{} \sigma \) is the signature issuing protocol between the signer \(\mathcal {S}\) and the user \(\mathcal {U}\) for a message \(m \in \{0,1\}^*\). It generates the signature \(\sigma \).

  • \(\textsf{Verif}(mpk, ID, m, \sigma )\) outputs 1 if the signature \(\sigma \) is valid for m, otherwise 0.

Secure \(\textsf{IDBS}\) must meet the three following security properties. Correctness, meaning that for any keys and any messages, the signature must always be accepted if all algorithms are honestly executed. Blindness requires that no information about the message could be revealed to the signer during the protocol. Finally, unforgeability requires that a user cannot forge new signatures from any set of existing signatures. Any of the upcoming schemes will have to meet these three basic properties. For their formal definition see the extended version of this paper [5].

We now describe in turn the other primitives based on \({\textsf{IDBS}}{}\).

ID-Based Proxy Blind Signature - \(\textsf{IDPrBS}\). An original signer \(\mathcal {S}\) delegates its right to sign to a proxy signer \(\mathcal {P}\). After being provided with a key and a public agreement, \(\mathcal {P}\) is allowed to sign any message coming from a user \(\mathcal {U}\) and falling within the agreement. \(\textsf{IDPrBS}\) should satisfy the security properties of correctness, blindness and unforgeability. But should also meet additional properties [11]: Prevention of misuse: proxy signing key cannot be used for purposes other than generating valid proxy signatures. In case of misuse, the responsibility of the proxy signer should be determined explicitly. Verifiability: From a proxy signature, a verifier can be convinced of the original signer’s agreement on the signed message. Strong Identifiability: Anyone can determine the identity of the proxy signer from a proxy signature. Strong Undeniability: A proxy signer cannot repudiate a proxy signature it created.

ID-Based (Restrictive) Partially Blind Signature - \({\textsf{IDPBS}}{}/\textsf{IDPRBS}\) [3]. Prior to the protocol, the user and the signer have to agree on a common part denoted \(\textsf{info}\). Instead of signing the usual message, \(m||\textsf{info}\) is signed. Restrictiveness is an additional constraint put by the signer on the user. \(\mathcal {U}\) is only able to get a signature on a message of a certain form, specified by the signer. Those schemes have almost the same security properties as \(\textsf{IDBS}\) schemes. The only added difference is the inability of the user to modify the common part unilaterally. We also have a modified version of blindness called partial blindness where the signer always knows the common part of the message.

ID-Based Fair Blind Signature - \(\textsf{IDFBS}\) [71]. Fairness gives the capability to a trusted entity to perform one or two types of link recoveries:

  • Type I: The trusted entity can output information that enables the signer to recognize the corresponding message-signature pair.

  • Type II: The trusted entity can output information that enables the signer to efficiently identify the sender or to find the corresponding view of the signing protocol.

ID-Based Blind Signature with Message Recovery - \(\textsf{IDBSMR}\). For a given signature and public key pair, there exists a verification algorithm that outputs the signed message. This property is useful to reduce the size of exchanged information. It requires a bijection between the possible messages and the group elements that will be used during the signing process.

ID-Based Forward-Secure Blind Signature - \(\textsf{IDFSBS}\) [94]. Consider the lifetime of a system divided into N time periods. In a blind signature context, forward secrecy means that unforgeability of signatures is valid in previous time periods even if current signing secret key of the signer is compromised. Thus, if the private key is compromised, only the signature for the current time period are forgeable. No signature for any previous time period can be forged, hence they remain safe to use.

ID-Based Blind Signature with Batch Verification - \(\textsf{IDBSBV}\) [7]. Batch verification has been designed to allow fast verification of multiple signatures. In practice a specific algorithm of verification \(\textsf{VerifMult}\) allows to verify a list of message-signature pair \(\{(m_1, \sigma _1),\ldots ,(m_n,\sigma _n)\}\) with the public key pk and output 1 if all signatures are valid, otherwise 0. We can allow this verification to be probabilistic with negligible probability of failure. Yet we want this verification to run significantly faster than n computations of the \(\textsf{Verif}\) algorithm.

ID-Based Weak Blind Signature - \(\textsf{IDWBS}\) [96]. This type of scheme does not achieve unlinkability when the signature is revealed to the signer i.e., the signer is able to link the revealed signature to a user when it has a clear view of the message-signature pair.

3 Evaluation Process

We have evaluated all known \(\textsf{IDBS}\) schemes with a proven security to choose the most practical one. Here we present a metric to evaluate their complexity. An evaluation of all secure schemes is given in the full version of this paper [5].

Table 1. Conversion in \(T_{MUL_{3072}}\).
Full size table

In order to evaluate the schemes we had to choose concrete evaluation parameters. Our chosen parameters follow the recommendations of the ECRYPT’s reports on key length [22]. These are similar to the more recent NIST’s recommendations. We use 3072 bits integers and equivalent 256-bits elliptic curves i.e., over finite field \(\mathbb {F}_q\), with q of size 256 bits. In practice, it provides around 128 bits of security. Notice that recommendations for parameters of lattice differ from scheme to scheme, moreover, almost none of the authors of the listed papers gave concrete parameters for there schemes. Based on these elements, we chose to left out reduction for lattice based scheme as parameters for these schemes are still imprecise. However, we evaluate the number of operations that each existing scheme requires.

In order to compare all the existing scheme, we first compare the execution time of each operation with the execution time of a standard 3072 bits integer multiplication. Based on these result we can reduce the complexity of each signature scheme in terms of an unified unit: \(T_{MUL_{3072}}\). Table 1 expresses the execution time of relevant operation op with the proposed conversion. \(T_{op}\) corresponds to the ratio between the execution time of each operation and a 3072 bits integer multiplication.Footnote 3 Our results are based on benchmarks on an Intel Core i7-1065G7 CPU @ 1.30 GHz processor without parallelism and generated using modern cryptographic libraries like GMP library [31] (arithmetical operations on integers), MPHELL library [1] (elliptic curve’s operations), PBC library [59] (pairing functions) and OpenSSL/Crypto [2] library (hash functions) using state-of-the-art speed up.

We use the notations Minv, Mmul, Mtran, Madd for associated arithmetical operations on matrices. MVmul denotes a multiplication between a matrix and a vector. SVmul is the multiplication of a vector by a scalar. Vadd stands for the addition of two vectors. Vh and Mh are hash functions returning respectively a vector or a matrix. Sample is a sampling operation defined in [29]. We also use the following notations for usual scalar operations: EXP, MUL, ADD, INV. Moreover, ECMULFootnote 4 and ECADD hold for multiplication and addition on elliptic curve. PAIR is the evaluation of a pairing function. H is for evaluation of a hash function and PH holds for hash function mapping on elliptic curve. Less common operation as CHEBY denotes the evaluation of a Chebyshev polynomial. TR denotes the trace function \(TR(h) = h + h^2+h^4\) in \(GF(p^6)\) in the context of XTR (Efficient and Compact Subgroup Trace Representation [55]) schemes.

We summarize our results in two types of tables. The first type of table (e.g., Table 2) gives a quick overview of a scheme with the following characteristics: mathematical setting (EC, pairing, etc.), security assumptions (CDH, ECDL, etc.), number of needed interactions and the number of random elements generated by a user to blind a message, also called blinding factor.

The second type of table evaluates and compare the complexity of the schemes. It is postponed to the full version [5] due to length limitation.

4 Schemes Presentation

4.1 ID-Based Blind Signature - \(\textsf{IDBS}\)

We have identified 32 \(\textsf{IDBS}\) schemes in the literature, they are listed in Table 2. The table gives the mathematical setting, the hard problem when a reduction is provided for the signature, the number of communications and the blinding factor. We chose these characteristics because communication between two distant machines can sometime be longer than running time of any algorithm of the signature edition. On another hand, we specify the number of random parameters to be generated each time. Generating cryptographically-secure randomness is costly, hence a low number of blinding factors can speed up the signature issuing and requires less resources.

Most schemes rely on pairing function and the CDH problem. Some such as [33, 52] are pairing free and consequently faster to execute. Due to the increasing development of post-quantum cryptography, new \(\textsf{IDBS}\) schemes have been designed based on the SIS problem. Another base concept is XTR. Introduced by Lenstra et al. [55], this cryptographic basis leads to smaller signatures for the same security level. For instance, one would need 512-bits prime integers to achieve equivalent security to discrete logarithm problem with prime of 3072 bits. We have used the conversions from [55] to evaluate the operation of scheme from [75] as parameters of the scheme in [92] are not clear. Thus, we cannot propose a rigorous evaluation for this scheme. However, we can infer its relatively slow speed since a zero-knowledge proof procedure is used to sign a message.

Table 2. Identity-Based Blind Signature. (\(^*\) Weak Linkability)
Full size table

Complexity evaluations and further details on the schemes are provided in the full version [5]. From this evaluation we note that the execution of an elliptic curves based signature gives better complexity than evaluation of a pairing function. Thus, pairing based signatures are less efficient. We have observed that Chebyshev polynomials are fast to evaluate, hence it produces an efficient scheme. Chaotic maps can be efficient, but their security needs to be more studied, yet a reduction to the discrete logarithm problem is given [73].

Table 3. ID-based Proxy Blind Signature Scheme.
Full size table
Table 4. ID-based Partially Blind Signature Scheme. (*Scheme with Restrictiveness)
Full size table

We conclude that the fastest pairing based scheme is 4 times faster than the slowest one. And again, the best pairing free scheme is 5 times faster than the best pairing based scheme. The complexity of [52] and [33] is close, and the difference might be negligible regarding time needed for cache affectation during the execution of properly implemented scheme. The only advantage is for [33], it uses less random values, but it might be compensated by the lowest complexity of the former scheme. Elliptic curve schemes still remain the most efficient schemes relying on a well-studied problem.

4.2 ID-Based Proxy Blind Signature - \(\textsf{IDPrBS}\)

Sorting the scheme by type of underlying problem, we give an overview of the existing \(\textsf{IDPrBS}\) in Table 3. Part of the existing schemes lack of formal security arguments. Three schemes are still recorded in our survey, but this is specified in the table. There exist \(\textsf{IDPrBS}\) based on the tree prominent type of problems: elliptic curves, pairing and lattice. Proxyness is the most studied property for \({\textsf{IDBS}}{}\), a generic construction exist for this primitive as highlighted in Sect. 4.5. The first scheme was introduced in 2003, only two years after the first appearing of pairing in cryptography in [54]. Ten years later was published the first paring-free scheme [74]. It led to one of the most efficient schemes of this survey and was proven as hard as the well-studied ECDL problem. With the development of quantum computer and the growing threat on classical assumptions, two lattice based schemes were developed [65, 70]. Sadly, attacks were found on both primitives. Thus, finding a lattice based \(\textsf{IDPrBS}\) is still an open problem.

Complexity evaluation of pairing based schemes are reported in the extended version [5]. With our comparison, we claim that the most efficient, proven secure, ID-based proxy blind signature is the one from S. James et al. [46].

4.3 ID-Based Partially Blind Signature - \(\textsf{IDPBS}\)

\(\textsf{IDPBS}\) sometime with restrictiveness as described in Sect. 2 are exposed in Table 4. These signatures allow adding auxiliary information to the message making them relevant for practical usages. This common information put in context improves management of signature and security. For example, it allows the signer to add an expiration date to its signatures. Up to today, 14 \(\textsf{IDPBS}\) have been published. As explained before, restrictiveness requires the user to fit its message to a specific structure. The user has fewer capabilities while the signer has more control. Due similarities between restrictive \(\textsf{IDPBS}\) and classical \(\textsf{IDPBS}\), we are evaluating them all together.

As usual we let the reader refer to the full version [5] for in depth evaluation of the schemes. \(\textsf{IDPBS}\) were published from 2004. The first published scheme had restrictiveness and was based on pairing. Only later, in 2016, a first scheme was proposed avoiding the use of pairing based cryptography, published by H. Islam et al. [43] it introduced the first elliptic curve based scheme leading to better efficiency when issuing signatures. Pairing free schemes are faster than pairing based by a factor of 1.5 to more than 10. Up to now, no lattice based or quantum resistant blind signature has been proposed with the aforementioned properties. The scheme’s signature sizes varies from 2 elements (i.e., 514 bits), being relatively short, up to 6 elements (i.e., 1542 bits) clearly leading to more computation during the verification process.

Scheme from [43] seems to be the best fitted algorithms as it is one of the most efficient schemes that we have recorded in our survey. Although its security is proven in the random oracle model, it is an efficient signature algorithm with a short signature, thus could be use in practice.

4.4 ID-Based Blind Signature with Other Properties

We describe and evaluate \(\textsf{IDBS}\) schemes with additional properties: message recovery, fairness, forward security and batch verification. These notions are quickly introduced in Sect. 2. Fewer signatures have been presented in the literature with these properties. A brief overview of their usefulness is given, followed by the usual evaluation routine (see Sect. 3). For a short overview of the characteristics of the schemes see Table 5. For their evaluation refer to the full version [5].

ID-Based Blind Signature with Message Recovery - \(\textsf{IDBSMR}\)

\(\textsf{IDBS}\) schemes with message recovery allow to recover the message from the signature and the public key. The six existing schemes are presented in Table 5. They rely for the most recent one on elliptic curves and on pairing function for the rest of them. Efficiency of these schemes are comparable to the most efficient of this survey. The best known pairing based \({\textsf{IDBSMR}}\) here only requires half of the computation expected toward the best pairing based \(\textsf{IDBS}\). For their evaluation refer to the full version [5].

A scheme with message recovery has to handle carefully the verification phase. All schemes with message recovery have a small signature only composed of two group elements. The size of the signature can be reduced to 514 bits via a simple compression algorithm. It is still an open problem to present a round-optimal \(\textsf{IDBS}\) with message recovery. The existing \(\textsf{IDBS}\) with message recovery all need 3 communications. This is an essential point for a blind signature scheme as communication comes at a cost in terms of time efficiency of the protocol.

ID-Based Fair Blind Signature - \(\textbf{IDFBS}\)

With a moderate cost, Wand et al. [83] where able to introduce an ID-based Fair Blind Signature. Moreover, it has two additional properties: enabling proxy signature and weak linkability. The drawbacks consist in a relatively long signature (1028 bits) and 4 communications to obtain the signature. Note that the weak linkability property could also be considered as a weakness of the scheme. Latter, an alternative was proposed by Verma et al. [78]. The scheme relies on a Fiat-Shamir signature and is based on oblivious transfer, which is known to be a relatively expensive primitives. Hence, the scheme has a low efficiency and needs many communications. We are not providing a complexity analysis of the latest as one willing to put such a signature in practice may not consider it due to its deficiency of proven security. The authors want to highlight that none of the schemes have been proven secure. In [83], discussion of the security of the scheme is provided, but no attention is given to unforgeability. Security proofs are almost mandatory in today’s development of cryptography and here no model has ever been proposed for these schemes. Despite the real practicality provided by fairness, none of the scheme would be considered as reliable enough. We conclude that some work remains to do to propose to the community an efficient and secure \(\textsf{IDFBS}\). We propose a security model for \({\textsf{IDFBS}}{}\) in the full version of the paper [5].

ID-Based Forward-Secure Blind Signature - \(\textbf{IDFSBS}\)

Forwards security is gradually becoming a central property in cryptography. In the context of signature scheme is allows to divide the lifetime of a key pair into N periods. The secret key is modified for each period while keeping the same public key, thus providing additional security as on leakage of a secret key, previous signature are no longer affected by this security breach. Thus, signatures made during the \(N-1\) others are still reliable. This increase the global security of signatures.

\(\textsf{IDFSBS}\) are not possible to compare since the authors of [94] were the only one to propose such a signature. It relies on the well-studied SIS problem over lattices and requires 3 communications and 2 blinding factor. The signature is composed of one vector of size m (the message) with elements in \(\mathbb {Z}_q\). Lattice based signatures known to produce relatively long outputs which is a drawback compensated by the absence of known algorithm to be efficient against them even on quantum computers. We further evaluate this signature in the full version of the paper [5].

ID-Based Blind Signature with Batch Verification - \(\textbf{IDBSBV}\)

Batch verification allows faster signature verification. For signatures with batch verification it is possible to specify an algorithm verifying multiples instance in the same time and significantly faster than the normal verification.

Table 5. \(\textsf{IDBS}\) with properties.
Full size table

We have observed only one such scheme by Li et al. [58]. The scheme is efficient, still relying on pairing function known to be costly. They proposed an efficient signature process leading a relatively short signature with fast verification. Note also that the scheme has a costly verification process, based on pairing. The batch verification allows to drastically reduce the need of pairing function for the verification and thus gives scheme that is comparable to the best pairing free algorithm of the literature.

4.5 Comparison to the Generic Construction

Generic construction of \(\textsf{IDBS}\) have been introduced by D. Galindo et al. [24]. It gives a generic framework based on a signature scheme \(\mathcal {S}=( KG _\mathcal {S}, SGN _\mathcal {S}, VFY _\mathcal {S})\) and a blind signature scheme \(\mathcal{B}\mathcal{S}=(\textsf{KG}_\mathcal{B}\mathcal{S}, \textsf{SGN}_\mathcal{B}\mathcal{S}^{com}, \textsf{SGN}_\mathcal{B}\mathcal{S}^{blind}, \textsf{SGN}_\mathcal{B}\mathcal{S}^{sgn}, \textsf{SGN}_\mathcal{B}\mathcal{S}^{unb}, \textsf{VFY}_\mathcal{B}\mathcal{S})\). Combining these two structures we can construct a \(\textsf{IDBS}\) scheme. In order to accomplish their roles the three entities (user, signer, verifier) have to execute the following algorithm to output and verify a signature: User: \( VFY _\mathcal {S}, \textsf{SGN}_\mathcal{B}\mathcal{S}^{blind}, \textsf{SGN}_\mathcal{B}\mathcal{S}^{unb}\); Signer: \(\textsf{SGN}_\mathcal{B}\mathcal{S}^{com}, \textsf{SGN}_\mathcal{B}\mathcal{S}^{sgn}\); Verifier: \( VFY _\mathcal {S}, \textsf{VFY}_\mathcal{B}\mathcal{S}\).

The authors of [24] proposed an instantiation for their ID-based blind signature construction based on two schemes: the Boneh-Lynn-Shacham (BLS) signature [10] and Boldyreva’s blind signature [9]. At the time D. Galindo et al. idea was published, they claimed to be among the most efficient schemes. We detail the cost of their proposed instantiation in the full version [5].

Based on our reduction, we can deduce that the total complexity of the generated scheme is barely the addition of the cost of both schemes and is around the average of the observed complexity for the existing \({\textsf{IDBS}}\) schemes. Relying on secure pairing free schemes would lead to a secure \(\textsf{IDBS}\) with improved complexity.

A more recently study [11] introduced a new generic construction for \(\textsf{IDPBS}\). As in the previous construction, they rely on a signature and a blind signature. They are organized in a manner reaching an acceptable complexity as explained in the article, with approximately the same complexity as the previous construction.

5 Synthesis of the Current Literature

There exists an extensive literature on \(\textsf{IDBS}\), numerous schemes have been presented by multiple authors. In total 71 schemes are presented in this survey. We noticed that the literature is mostly independent and that no global courses of action was followed by the authors of these schemes. Only few works mostly based on lattices were following previous work due to some attacks found on them: the latest schemes were made to fix some security breach in the existing work. This survey aims at putting some coherence in future work in the field, it brings up formalism for security assumption based on the existing security expectation for each of the properties. In the long version of this paper [5], we have tried to formalize these securities properties for the various security that such a scheme was expected to withdraw when an attack comes in place through security games. Even if these experiments needs further discussion before being fully adopted by the community, we believe it as a step forward in the study of the security of these primitives.

This is motivated by the fact that no security proofs or formal arguments have been disclosed for 22 of the investigated schemes. It implies that it may remain unknown vulnerabilities for existing schemes and possible attacks might be found in the future. We do not recommend using any unproven schemes for practical purposes. Also, some authors provided a reduction for their scheme. Yet, the security may not be ensured as their assumption are weak e.g., \({\textsf{IDBS}}\) rely on quite unusual hypothesis and some other schemes rely on the broken ROS problem. The later should no longer be used as they do not bring any security to their users.

While exploring the literature, we noticed that it lacks pairing free \(\textsf{IDFBS}\), \(\textsf{IDFSBS}\) or \(\textsf{IDBSBV}\) schemes. Further studies could potentially improve efficiency and quantum resistance of such primitives. No pairing free \(\textsf{IDFBS}\) or \(\textsf{IDBSBV}\) yet exists and no post quantum assumption was ever used to design an \(\textsf{IDPBS}\), \(\textsf{IDPrBS}\), \(\textsf{IDBSMR}\), \(\textsf{IDFBS}\) or \(\textsf{IDBSBV}\) that withdraw proven security until today. A big step forward on the development of new schemes on post quantum assumptions is necessary to guarantee the future of these primitives.

On another hand, minimizing the number of transmission to obtain round optimal \({\textsf{IDBS}}\) is also of interest for the field as it brings a non-negligible speedup as most construction achieves a computational cost comparable of to the order of magnitude of a Round Trip Time. For example, no round optimal \({\textsf{IDBSMR}}\) have ever been introduced, combined with this type of primitive that seems to achieve efficient computational time would be of interest.

As highlighted in [90], numerous schemes had issues while being performed in parallel execution. This is mostly due to a polynomial time algorithm capable of solving the ROS problem [8]. Other studies could focus on bringing an \({\textsf{IDBS}}\) with proven security under parallel execution.

We see that some works are still to be done in this domain to guarantee the future security and the practicality of the \({\textsf{IDBS}}\) and other signature schemes evoked in this paper.

6 Conclusion

In this survey we review the literature on ID-based blind signature with several existed properties presented throughout this paper. We show that depending on the case of use, there exist several \({\textsf{IDBS}}\) schemes to consider. The studied schemes have specific properties and their efficiency relies on manifold requirements. In this survey we answer the question: how to choose an \(\textsf{IDBS}\) scheme? For that we have listed all existing \(\textsf{IDBS}\) schemes, we present them all with their most notable properties and a reproducible, bias free evaluation of their complexity. Providing a time reduction of all arithmetical operations used for \({\textsf{IDBS}}\) schemes in order to evaluate them all at the same security level is our first contribution. We directly exploit it to give a metric on the complexity of any these scheme. With this metric we can compute the total computational cost of a signature issuing and verification process. Hence, it is easy to compare their efficiencies.

We can conclude thanks to our study that the most computationally efficient \(\textsf{IDBS}\) scheme using EC is [52]. But schemes can be chosen from other kind of feature such as number of communications, number of blinding factors or the size of the signature. We enable anybody to quickly choose from the existing literature the best feted properties and signature for its use based on their characteristics. In the extended version [5], we also give new insights by proposing formal security experiment and open axes of research for these primitives.