Efficient Round-Optimal Blind Signatures in the Standard Model

Abstract

Blind signatures are at the core of e-cash systems and have numerous other applications. In this work we construct efficient blind and partially blind signature schemes over bilinear groups in the standard model. Our schemes yield short signatures consisting of only a couple of elements from the shorter source group and have very short communication overhead consisting of 1 group element on the user side and 3 group elements on the signer side. At 80-bit security, our schemes yield signatures consisting of only 40 bytes which is $67\%$ shorter than the most efficient existing scheme with the same security in the standard model. Verification in our schemes requires only a couple of pairings. Our schemes compare favorably in every efficiency measure to all existing counterparts offering the same security in the standard model. In fact, the efficiency of our signing protocol as well as the signature size compare favorably even to many existing schemes in the random oracle model. For instance, our signatures are shorter than those of Brands’ scheme which is at the heart of the U-Prove anonymous credential system used in practice. The unforgeability of our schemes is based on new intractability assumptions of a “one-more” type which we show are intractable in the generic group model, whereas their blindness holds w.r.t. malicious signing keys in the information-theoretic sense. We also give variants of our schemes for a vector of messages.

The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007–2013)/ERC Grant Agreement n. 307937 and EPSRC grant EP/J009520/1. The work was done while the author was at University College London.

1 Introduction

Blind signatures introduced by Chaum [23] are an interactive protocol that allows a user to obtain signatures on messages of her choice without revealing the messages to the signer. Blindness in these schemes ensures that it is infeasible for a malicious signer to link the final signatures to their corresponding signing requests. Blindness can be either proven in the honest-key model where the key pair is produced by the challenger and then revealed to the adversary or in the stronger malicious-key model [1, 49] where the key pair is chosen by the adversary herself and she is not required to reveal the signing key to the challenger. On the other hand, unforgeability ensures that it is infeasible for a malicious user to obtain more valid signatures on distinct messages than the number of completed interactions with the honest signer. Such a primitive is at the core of e-cash systems [23] where the bank acts as the signer; the privacy requirement comes from the non-traceability requirement of cash. It also finds applications in e-voting [34], anonymous credentials [8] and direct anonymous attestation [12, 20]. The primitive is very relevant to practice, besides its prominent role in realizing e-cash systems, blind signatures are the backbone of some anonymous credential systems deployed in practice, which include the U-Prove system [19].

Measures of importance when designing such schemes include their round complexity, i.e. the number of moves between the parties before the user can derive a signature. Round-optimal schemes [27] consisting of only two moves are known to imply security under concurrent executions.

Related Work. After their introduction by Chaum [23], a long line of research on blind signatures has evolved. Constructions of blind signatures relying on random oracles [26] include [2, 8, 11, 15, 18, 23, 52,53,54]. Most of the early constructions relying on random oracles are essentially Full-Domain-Hash (FDH) style signatures. The user sends a blinded message digest of the message to the signer who in turn returns a signature on such a digest. Upon receiving the signature, thanks to the homomorphic property of the underlying signature scheme, the user is able to transform such a signature to one on the message. This is the underlying idea behind the original (RSA based) scheme in [23] which was proven secure in [52]. The same applies to the (DLog based) scheme in [15].

Constructions dispensing with relying on random oracles but at the expense of assuming a trusted common reference string (CRS) include [6, 21, 40, 46]. Fischlin [27] gave a generic construction of two-move schemes in the CRS model satisfying blindness in the malicious-key model. His construction requires the user to send a commitment to her message which in turn gets signed by the signer. The final signature is then merely a zero-knowledge proof of knowledge of a signature on the (hidden) commitment to the message. Most subsequent constructions in the CRS model are either direct instantiations of Fischlin’s construction, e.g. [3, 5], or variations thereof, e.g. [3, 30]. The scheme in [3, 30] adopts a similar approach as Fischlin’s but instead of hiding the signed commitment, it exploits a feature of the underlying signature scheme to transform a signature on the commitment to a signature on the message itself. Other round-optimal constructions in the CRS model include [13, 14, 48, 56].

Round-optimal constructions not relying on either of the aforementioned assumptions, i.e. in the standard model, are preferable. However, it is well-known that such schemes are harder to design. Lindell [47] showed that it is impossible to design round-optimal schemes in the standard model conforming to simulation-based (rather than game-based) security definitions. However, Hazay et al. [44] showed that (non-round-optimal) realizations are possible under game-based definitions. Abe and Ohkubo [6] showed that universally composable blind signatures, even non-committing ones, are impossible in the standard model. Okamoto [49] gave a non-round-optimal construction in the standard model which satisfies blindness in the malicious-key model. Fischlin and Schröder [29] proved that it is impossible to reduce the security of a standard-model blind signature scheme in a blackbox manner to the intractability of a non-interactive assumption if the scheme has any of the following properties: (i) the signing protocol has less than 4 moves. (ii) Its blindness holds statistically (iii) the signing transcript allows one to check if a valid signature can be derived from it.

Existing constructions in the standard model [36, 37] circumvent the impossibility result by making use of a non-blackbox reduction to the underlying primitive. Garg et al. [37] gave the first round-optimal construction in the standard model solving a long-standing open problem. Their scheme combines fully homomorphic encryption with two-move witness-indistinguishable proofs known otherwise as ZAPs [25]. Their scheme is inefficient and is only considered as a feasibility result. Recently, Garg and Gupta [36] gave a more efficient round-optimal construction which combines structure-preserving signature schemes [3] and Groth-Sahai NIZK proofs [41]. To eliminate the need for a trusted party, they use two CRSs which are part of the signer’s public key. The signer is forced to choose those honestly as otherwise she needs to solve an exponential-time problem in order to cheat. The security of their scheme holds w.r.t. non-uniform adversaries and relies on complexity leveraging. Consequently, it suffers from a large communication overhead and a rather large computational cost.

Recently, Fuchsbauer et al. [33] gave a semi-generic construction of round-optimal schemes in the standard model which combines the Pedersen commitment scheme [50] with structure-preserving signatures on equivalence classes [42]. Their construction satisfies blindness against malicious keys. They gave an efficient instantiation whose security relies on a couple of interactive assumptions where they used the optimal construction of signature on equivalence classes from [32]. More recently, Fuchsbauer et al. [31] weakened the assumptions on which the instantiation in [33] is based by eliminating one of the interactive assumptions on which the blindness in [33] was relying. However, the unforgeability of the new variant still relies on an interactive intractability assumption. Hanzlik and Kluczniak [43] gave a construction in the standard model in the honest-key model. The downside of their construction is that it uses an encryption scheme over composite-order groups which requires groups of a large order as well as a strong non-standard “knowledge” assumption [9]. Very recently, Döttling et al. [24] showed that blind signatures in the standard model can be constructed from maliciously circuit-private homomorphic encryption for logarithmic depth circuits.

Baldimtsi and Lysyanskaya [7] showed that existing techniques fall short for proving the security of some existing blind signatures lacking a security proof in the random oracle model. Concerned constructions include Schnorr’s [54] and Brands’ [18] schemes. The latter is at the core of the U-Prove system.

Abe and Fujisaki [4] put forward the notion of partially blind signatures which extends blind signatures to allow some part of the message to be public. This makes it possible to attach some public attributes, e.g. an expiration date, to the signatures. Recently, Fuchsbauer et al. [31, 33] gave the first efficient round-optimal partially blind schemes in the standard model.

Our Contribution. We construct two efficient blind signature schemes in the standard model satisfying blindness in the malicious-key model. Our schemes yield very short signatures consisting of only a pair of elements from the shorter source group. At 80-bit security, our signatures are only 40 bytes long which means they are $67\%$ shorter than the best existing scheme offering the same security [33]. Verifying signatures in our schemes involves evaluating a couple of pairings. The latter matches the verification overhead of the most efficient existing (non-blind) signature schemes over bilinear groups [16, 17]. Such desirable efficiency means that our schemes can even be deployed on devices with limited computational power if the evaluation of pairings required for verification is outsourced to a third party, e.g. using techniques from [22]. Our schemes have a very low communication overhead on both sides. The blindness of our schemes holds in the information-theoretic sense whereas their unforgeability relies on new intractability assumptions which we show hold in the generic group model [57]. Note that it is well-known that blind signature schemes in the standard model based solely on non-interactive assumptions, e.g. [36, 37], are much less efficient. Furthermore, all existing efficient round-optimal schemes in the standard model offering the same security as ours [31, 33] also rely on interactive intractability assumptions.

We also construct efficient partially blind signature schemes and efficient blind signature schemes for a vector of messages. The techniques underlying our constructions are akin to the blind-unblind paradigm which usually form the basis of the efficient constructions in the random oracle model. However, to obtain the desired efficiency in the standard model, we apply various techniques. Similarly to [31, 33, 40], our constructions do not require expensive zero-knowledge proofs.

Paper Organization. The rest of the paper is organized as follows. In Sect. 2, we give some preliminary definitions. In Sect. 3, we introduce and prove intractability of our new assumptions. In Sect. 4, we recall the syntax and security of blind signatures. In Sect. 5, we give our blind signature constructions. We show in Sect. 6 how to extend our schemes to sign a vector of messages. In Sect. 7, we give our partially blind signature constructions.

Notation. We write $b=\mathsf {Alg}(a;r)$ when algorithm $\mathsf {Alg}$ on input a and randomness r outputs b. We write $b\leftarrow \mathsf {Alg}(a)$ for the process of setting $b=\mathsf {Alg}(a;r)$ where r is sampled at random. For an algorithm $\mathsf {Alg}$ and an oracle $\mathcal {O}$, $\mathsf {Alg}^{\mathcal {O}^k(\cdot )}$ denotes that $\mathsf {Alg}$ can access $\mathcal {O}$ at most k times on inputs of $\mathsf {Alg}$’s choice. We write $a\leftarrow \mathcal {S}$ for sampling a uniformly at random from the set $\mathcal {S}$. A function $\nu (.): \mathbb {N}\rightarrow \mathbb {R}^+$ is negligible (in $\lambda$) if for every polynomial $\rho (\cdot )$ and all sufficiently large values of $\lambda$, it holds that $\nu (\lambda )<\frac{1}{\rho (\lambda )}$. PPT stands for running in probabilistic polynomial time in the relevant security parameter. For $\ell \in \mathbb {N}\setminus \{0\}$, by $[\ell ]$ we denote the set $\{1,\ldots ,\ell \}$.

2 Preliminaries

In this section we provide some preliminary definitions.

Bilinear Groups. A bilinear group is a tuple $\mathcal {P}:=({\mathbb {G}}, \hat{\mathbb {G}}, \mathbb {T}, p, {\MakeUppercase {G}}, \hat{\MakeUppercase {G}}, {e})$ where ${\mathbb {G}}$, $\hat{\mathbb {G}}$ and $\mathbb {T}$ are groups of a prime order $p$, and ${\MakeUppercase {G}}$ and $\hat{\MakeUppercase {G}}$ generate ${\mathbb {G}}$ and $\hat{\mathbb {G}}$, respectively. The function ${e}$ is a non-degenerate bilinear map ${e}: {\mathbb {G}}\times \hat{\mathbb {G}}\longrightarrow \mathbb {T}$. To distinguish between elements of ${\mathbb {G}}$ and $\hat{\mathbb {G}}$, the latter will be accented with $\hat{~}$. We use multiplicative notation for all the groups. We let ${\mathbb {G}}^\times := {\mathbb {G}}\setminus \{1_{{{\mathbb {G}}}}\}$ and $\hat{\mathbb {G}}^\times := \hat{\mathbb {G}}\setminus \{1_{\hat{\mathbb {G}}}\}$. In this paper, we work in the efficient Type-III setting [35], where ${\mathbb {G}}\ne \hat{\mathbb {G}}$ and there is no efficiently computable isomorphism between the groups in either direction. We assume there is an algorithm $\mathcal {BG}$ that on input a security parameter $\lambda$, outputs a description of bilinear groups. Without loss in generality and similarly to e.g. [31, 33] in this work we will assume $\mathcal {BG}$ is deterministic, which as argued by [31, 33] is the case for instance in the most widely used groups based on BN curves [10].

Pedersen Commitment Scheme. We use a generalized variant of the Pedersen commitment scheme [50] which allows committing to a vector of messages at once. The scheme is information-theoretically hiding and computationally binding under the discrete logarithm assumption. The generalized variant is defined by the following algorithms:

• $\mathsf {Setup}(1^\lambda ,n)$ On input the security parameter $\lambda$ and the size of the vector $n$, this algorithm chooses a cyclic group $\mathbb {G}$ of prime order $p$ where $\log {p} \in \varTheta (\lambda )$. It also samples the elements $G_1,\ldots ,G_n, H \leftarrow \mathbb {G}$. It returns the commitment key $\mathsf {ck}:=(G_1,\ldots ,G_n, H )$ which we assume is an implicit input to the rest of the algorithms.

• $\mathsf {Commit}(\varvec{m},r)$ On input a message vector $\varvec{m}=(m_1, \ldots , m_n) \in \mathbb {Z}^n_p$ and a randomness $r \in \mathbb {Z}_p$, this algorithm returns the commitment $\mathsf {Co}:=H^r \prod _{i=1}^{n} G_i^{m_i}$ and the opening information $d :=(\varvec{m},r)$.

• $\mathsf {Open}(\mathsf {Co},d=(\varvec{m},r))$ On input a commitment $\mathsf {Co}$ and its associated opening information d, this algorithm verifies whether such opening information is a valid one by checking that $\mathsf {Co}= H^r \prod _{i=1}^{n} G_i^{m_i}$ returning 1 or 0 accordingly.

Since the hiding property of the scheme holds in the information-theoretic sense, such a property still holds even if we let the recipient runs the $\mathsf {Setup}$ algorithm which is otherwise usually run by a trusted third party. The above argument holds as long as $H \ne 1_{\mathbb {G}}$ which is easy to check.

3 New Intractability Assumptions

In this section we introduce some new assumptions of a “one-more” type where the adversary interacts with an oracle k times and is tasked with outputting $k+1$ valid tuples. They are similar in nature to the E-LRSW assumption introduced by Ghadafi and Smart [40].

3.1 The BSOM Assumption

Our first new assumption which we refer to as the BSOM (short for Blind Signature One More) assumption will form the basis for the unforgeability of our first blind signature construction. It is inspired in part by the assumption underlying the recent signature scheme by Ghadafi [38].

Definition 1

(BSOM Assumption). Let $\mathcal {P}=({\mathbb {G}},\hat{\mathbb {G}},\mathbb {T},{\MakeUppercase {G}},\hat{\MakeUppercase {G}}, {e},p)$ be the description of Type-III bilinear groups output by $\mathcal {BG}(1^\lambda )$, and let ${\MakeUppercase {H}}:={\MakeUppercase {G}}^{h}$, $\hat{\MakeUppercase {H}}:=\hat{\MakeUppercase {G}}^{h}$, $\hat{\MakeUppercase {X}}:=\hat{\MakeUppercase {G}}^{x}$, $\hat{\MakeUppercase {Y}}:=\hat{\MakeUppercase {G}}^{y}$ for some $h,x,y \leftarrow \mathbb {Z}_p$. Let $\mathcal {O}{} \textit{BSOM}_{{\MakeUppercase {H}},\hat{\MakeUppercase {H}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}}}(\cdot )$ be an oracle that on input a message ${\MakeUppercase {M}} = {\MakeUppercase {G}}^m$ (for some possibly unknown $m \in \mathbb {Z}_p$) returns a triple $\big ({\MakeUppercase {A}} :={\MakeUppercase {G}}^a, {\MakeUppercase {B}} :=({\MakeUppercase {G}}^x {\MakeUppercase {M}})^{\frac{a}{ y}}, {\MakeUppercase {C}} :={\MakeUppercase {H}}^{\frac{a}{ y}} \big ) \in {\mathbb {G}}^3$ for some $a \leftarrow \mathbb {Z}_p$. We say the BSOM assumption holds (relative to $\mathcal {BG}$) if for all PPT adversaries $\mathcal {A}$, the following advantage is negligible (in $\lambda$):

$$ \Pr \left[ \begin{array}{l} \mathcal {P}\leftarrow \mathcal {BG}(1^\lambda );~h,x,y \leftarrow \mathbb {Z}_p;~({\MakeUppercase {H}},\hat{\MakeUppercase {H}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}}):=({\MakeUppercase {G}}^{h},\hat{\MakeUppercase {G}}^{h},\hat{\MakeUppercase {G}}^{x},\hat{\MakeUppercase {G}}^{y});~\\ \left\{ ({\MakeUppercase {A}}_i, {\MakeUppercase {B}}_i, m_i )\right\} _{i=1}^{k+1} \leftarrow \mathcal {A}^{\mathcal {O}{} \textit{BSOM}_{{\MakeUppercase {H}},\hat{\MakeUppercase {H}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}}}^{k}(\cdot )}\left( \mathcal {P}, {\MakeUppercase {H}},\hat{\MakeUppercase {H}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}}\right) :~\\ \left| \{m_i\}_{i=1}^{k+1}\right| =k+1 ~\wedge ~ \forall i \in [k+1]:~{\MakeUppercase {A}}_i \ne 1_{{\mathbb {G}}} \wedge {e}({\MakeUppercase {B}}_i,\hat{\MakeUppercase {Y}})= {e}({\MakeUppercase {A}}_i, \hat{\MakeUppercase {X}} \hat{\MakeUppercase {G}}^{m_i}) \end{array} \right] $$

The proof for the following theorem can be found in the full version [39].

Theorem 1

For any generic adversary $\mathcal {A}$ against the BSOM assumption, if p is the (prime) order of the bilinear group and $\mathcal {A}$ makes $q_G$ group operation queries, $q_P$ pairing queries and $q_O$ queries to the BSOM oracle $\mathcal {O}{} \textit{BSOM}_{{\MakeUppercase {H}},\hat{\MakeUppercase {H}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}}}$, then the probability of $\mathcal {A}$ against the BSOM assumption is $\mathcal {O}(\frac{q_G^2 q_O + q_P^2 q_O + q_O^3}{p})$.

3.2 The BSOMI Assumption

Our second new assumption which we refer to as the BSOMI assumption will form the basis for the unforgeability of our second blind signature construction. It is inspired in part by the assumption underlying the recent signature scheme by Pointcheval and Sanders [51].

Definition 2

(BSOMI Assumption). Let $\mathcal {P}=({\mathbb {G}},\hat{\mathbb {G}},\mathbb {T},{\MakeUppercase {G}},\hat{\MakeUppercase {G}}, {e},p)$ be the description of Type-III bilinear groups output by $\mathcal {BG}(1^\lambda )$, and let ${\MakeUppercase {H}}:={\MakeUppercase {G}}^{h}$, $\hat{\MakeUppercase {H}}':=\hat{\MakeUppercase {G}}^{\frac{1}{h}}$, $\hat{\MakeUppercase {X}}:=\hat{\MakeUppercase {G}}^{x}$, $\hat{\MakeUppercase {Y}}:=\hat{\MakeUppercase {G}}^{y}$ for some $h,x,y \leftarrow \mathbb {Z}_p$. Let $\mathcal {O}{} \textit{BSOMI}_{{\MakeUppercase {H}},\hat{\MakeUppercase {H'}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}}}(\cdot )$ be an oracle that on input a message ${\MakeUppercase {M}} :={\MakeUppercase {G}}^m$ (for some possibly unknown $m \in \mathbb {Z}_p$) returns a triple $\big ({\MakeUppercase {A}} :={\MakeUppercase {G}}^a, {\MakeUppercase {B}} :={\MakeUppercase {A}}^{x} {\MakeUppercase {M}}^{a y}, {\MakeUppercase {C}} :={\MakeUppercase {H}}^{a y} \big ) \in {\mathbb {G}}^3$ for some $a \leftarrow \mathbb {Z}_p$. We say the BSOMI assumption holds (relative to $\mathcal {BG}$) if for all PPT adversaries $\mathcal {A}$, the following advantage is negligible (in $\lambda$):

$$ \Pr \left[ \begin{array}{l} \mathcal {P}\leftarrow \mathcal {BG}(1^\lambda );~h,x,y \leftarrow \mathbb {Z}_p;~({\MakeUppercase {H}},\hat{\MakeUppercase {H'}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}}):=({\MakeUppercase {G}}^{h},\hat{\MakeUppercase {G}}^{\frac{1}{h}},\hat{\MakeUppercase {G}}^{x},\hat{\MakeUppercase {G}}^{y});~\\ \left\{ ({\MakeUppercase {A}}_i, {\MakeUppercase {B}}_i, m_i )\right\} _{i=1}^{k+1} \leftarrow \mathcal {A}^{\mathcal {O}{} \textit{BSOMI}_{{\MakeUppercase {H}},\hat{\MakeUppercase {H'}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}}}^{k}(\cdot )}\left( \mathcal {P}, {\MakeUppercase {H}},\hat{\MakeUppercase {H'}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}}\right) :~\\ \left| \{m_i\}_{i=1}^{k+1}\right| =k+1 ~\wedge ~ \forall i \in [k+1]:~{\MakeUppercase {A}}_i \ne 1_{{\mathbb {G}}} \wedge {e}({\MakeUppercase {B}}_i,\hat{\MakeUppercase {G}})= {e}({\MakeUppercase {A}}_i, \hat{\MakeUppercase {X}} \hat{\MakeUppercase {Y}}^{m_i}) \end{array} \right] $$

The proof for the following theorem can be found in the full version [39].

Theorem 2

For any generic adversary $\mathcal {A}$ against the BSOMI assumption, if p is the (prime) order of the bilinear group and $\mathcal {A}$ makes $q_G$ group operation queries, $q_P$ pairing queries and $q_O$ queries to the BSOMI oracle $\mathcal {O}{} \textit{BSOMI}_{{\MakeUppercase {H}},\hat{\MakeUppercase {H'}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}}}$, then the probability of $\mathcal {A}$ against the BSOMI assumption is $\mathcal {O}(\frac{q_G^2 q_O + q_P^2 q_O + q_O^3}{p})$.

4 Syntax and Security of Blind Signatures

In this section, we define the syntax and security of blind signatures. Since we are interested in round-optimal schemes, we will specialize our definitions to this case. A blind signature scheme $\mathsf {BS}$ (with a two-move signature request) consists of the following polynomial-time algorithms:

• $\mathsf {KeyGen}_\mathsf {BS}(1^\lambda )$ On input a security parameter $1^\lambda$, this probabilistic algorithm outputs a pair $(\mathsf {vk}_\mathsf {BS},\mathsf {sk}_\mathsf {BS})$ of public/secret keys for the signer. Without loss of generality we assume the security parameter is an implicit input to the rest of the algorithms.

• $\mathsf {Request}^0_\mathsf {BS}(\mathsf {vk}_\mathsf {BS},m)$: This algorithm run by the user takes as input a message m in the message space $\mathcal {M}$ and the public key $\mathsf {vk}_\mathsf {BS}$, and produces a signature request $\rho$, plus some state $\mathsf {st}$ (which is assumed to contain m).

• $\mathsf {Issue}_\mathsf {BS}(\mathsf {sk}_\mathsf {BS},\rho )$: This probabilistic algorithm run by the signer takes as input the secret key $\mathsf {sk}_\mathsf {BS}$ and the signature request $\rho$, and produces a pre-signature $\beta$.

• $\mathsf {Request}^1_\mathsf {BS}(\mathsf {vk}_\mathsf {BS},\beta ,\mathsf {st})$: On input the public key $\mathsf {vk}_\mathsf {BS}$, the pre-signature $\beta$, and the state $\mathsf {st}$, this algorithm produces a blind signature $\sigma$ on m, or it outputs $\perp$ if it does not accept the transcript.

• $\mathsf {Verify}_\mathsf {BS}(\mathsf {vk}_\mathsf {BS},m,\sigma )$: This deterministic algorithm outputs 1 if $\sigma$ is a valid signature on the message m, or 0 otherwise.

(Perfect) correctness of blind signatures requires that for all $\lambda \in \mathbb {N}$ and all $m \in \mathcal {M}$, we have

$$ \Pr \left[ \begin{array}{l} (\mathsf {vk}_\mathsf {BS},\mathsf {sk}_\mathsf {BS}) \leftarrow \mathsf {KeyGen}_\mathsf {BS}(1^\lambda );~(\rho ,\mathsf {st})\leftarrow \mathsf {Request}^0_\mathsf {BS}(\mathsf {vk}_\mathsf {BS},m);\\ \beta \leftarrow \mathsf {Issue}_\mathsf {BS}(\mathsf {sk}_\mathsf {BS},\rho );\sigma \leftarrow \mathsf {Request}^1_\mathsf {BS}(\mathsf {vk}_\mathsf {BS},\beta ,\mathsf {st}) : \mathsf {Verify}_\mathsf {BS}(\mathsf {vk}_\mathsf {BS},m,\sigma ) = 1 \end{array} \right] = 1.$$

Security of blind signatures [45, 52] which was strengthened by [28, 55] requires blindness and unforgeability.

Unforgeability. Unforgeability requires that it is infeasible for an adversarial user who interacts with an honest signer on k occasions to output $k+1$ valid signatures on $k+1$ distinct messages.

Definition 3

(Unforgeability). A blind scheme $\mathsf {BS}$ satisfies unforgeability if for all $\lambda \in \mathbb {N}$, for all PPT adversaries $\mathcal {A}$, the advantage $\mathsf {Adv}_{\mathsf {BS},\mathcal {A}}^{\textit{Unforge}}(\lambda )$ against the game $\mathsf {Exp}_{\mathsf {BS},\mathcal {A}}^{\textit{Unforge}}$ defined in Fig. 1. is negligible (in $\lambda$) where

$$ \mathsf {Adv}_{\mathsf {BS},\mathcal {A}}^{\textit{Unforge}}(\lambda ) = \Pr [\mathsf {Exp}_{\mathsf {BS},\mathcal {A}}^{\textit{Unforge}}(\lambda )=1]. $$

Fig. 1.

The security experiments for unforgeability (left) and blindness w.r.t. malicious keys (right)

Blindness. Blindness (w.r.t. malicious keys [1, 49]) requires that an adversarial signer who freely chooses two messages $m_0$ and $m_1$ as well as the keys and then takes part in interactions with an honest user to generate signatures on those messages cannot tell the order in which the messages were signed.

Definition 4

(Blindness w.r.t. malicious keys). A blind scheme $\mathsf {BS}$ satisfies blindness w.r.t. malicious keys if for all $\lambda \in \mathbb {N}$, for all PPT adversaries $\mathcal {A}$, the advantage $\mathsf {Adv}_{\mathsf {BS},\mathcal {A}}^{\textit{Blind}}(\lambda )$ defined as

$$ \mathsf {Adv}_{\mathsf {BS},\mathcal {A}}^{\textit{Blind}}(\lambda ) = \left| \Pr [\mathsf {Exp}_{\mathsf {BS},\mathcal {A}}^{\textit{Blind}}(\lambda )=1] - \frac{1}{2} \right| $$

is negligible (in $\lambda$) where $\mathsf {Exp}_{\mathsf {BS},\mathcal {A}}^{\textit{Blind}}$ is defined in Fig. 1.

5 Blind Signature Constructions

Here we present our two constructions of blind signatures satisfying blindness in the malicious-key model.

5.1 Construction I

Here we present our first construction whose unforgeability is based on the BSOM assumption. The high-level idea is that when requesting a blind signature on the message $m\in \mathbb {Z}_p$, the user uses the Pedersen commitment scheme to commit to m as $\mathsf {Co}:=G^m H^r$ and sends the commitment $\mathsf {Co}$ to the signer. Unlike many existing constructions, neither the user nor the signer in our construction are required to produce expensive zero-knowledge proofs to prove correctness of their computation. Note that since the Pedersen commitment is perfectly hiding, the commitment $\mathsf {Co}$ reveals no information about the committed message. We can think of such a commitment as the message M on which the oracle in the $\text {BSOM}$ assumption is queried. Now the signer, playing the role of the oracle in the definition of the $\text {BSOM}$ assumption, returns the tuple $(A',B',C')$. The user can check whether such a tuple corresponds to a valid pre-signature by first verifying that the last element (which is independent of the message) is constructed correctly. This is achieved by verifying that ${e}(C',\hat{\MakeUppercase {Y}})={e}(A',\hat{\MakeUppercase {H}})$. If such a check does not pass, the user returns $\perp$. Otherwise, since the user already knows the randomness r she used in constructing the commitment $\mathsf {Co}$, she can now adapt the pre-signature $(A',B')$ on the commitment $\mathsf {Co}$ to one on the message m by letting $B' :=B' {C'}^{-r}$ and then randomizing the signature $(A',B')$ into a new one (A, B) so that the two pairs are unlinkable. Similarly to e.g. [31, 33], by assuming that the bilinear group generator $\mathcal {BG}$ is deterministic combined with the fact that the Pedersen commitment remains hiding even if the commitment key is generated maliciously, we achieve blindness w.r.t. malicious keys. The construction is detailed in Fig. 2.

Fig. 2.

Our 1st blind signature construction

Note that the checks performed in the ${\mathsf {Request}_{\mathsf {BS}}^0}$ algorithm to verify well-formedness of the signer’s verification key need only be performed once when requesting the first signature and not each time a signature is requested.

Theorem 3

The construction is a secure blind signature scheme in the malicious-key model.

Proof

We first show that the scheme is correct. We have that $\mathsf {Co}= {\MakeUppercase {G}}^m {\MakeUppercase {H}}^r$, ${\MakeUppercase {B'}}=({\MakeUppercase {G}}^x \mathsf {Co})^{\frac{a'}{y}}= {\MakeUppercase {G}}^{\frac{a' x}{y}} \mathsf {Co}^{\frac{a'}{y}} ={\MakeUppercase {G}}^{\frac{a' x}{y}} ({\MakeUppercase {G}}^m {\MakeUppercase {H}}^r) ^{\frac{a'}{y}}$ and ${\MakeUppercase {C'}} = {\MakeUppercase {H}}^{\frac{a'}{y}}$. We have that ${\MakeUppercase {B'}}={\MakeUppercase {B'}} {\MakeUppercase {C'}}^{-r}= {\MakeUppercase {G}}^{\frac{a' x}{y}} ({\MakeUppercase {G}}^m {\MakeUppercase {H}}^r) ^{\frac{a'}{y}} {\MakeUppercase {H}}^{\frac{-a' r}{y}} = {\MakeUppercase {G}}^{\frac{a' x}{y}} {\MakeUppercase {G}}^\frac{m a'}{y}$. Thus, $({\MakeUppercase {A'}},{\MakeUppercase {B'}})$ satisfy ${e}({\MakeUppercase {B'}},\hat{\MakeUppercase {Y}})= {e}({\MakeUppercase {A'}},\hat{\MakeUppercase {X}} \hat{\MakeUppercase {G}}^m)$.

The following 2 lemmata complete the proof.

Lemma 1

(Unforgeability). The construction is unforgeable if the BSOM assumption is intractable.

Proof

Let $\mathcal {A}$ be an adversary against the unforgeability of the scheme. We show how to use $\mathcal {A}$ to construct an adversary $\mathcal {B}$ against the BSOM assumption. Adversary $\mathcal {B}$ gets the tuple $(\mathcal {P},{\MakeUppercase {H}},\hat{\MakeUppercase {H}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}})$ from her game and she has access to the oracle $\mathcal {O}\text {BSOM}_{{\MakeUppercase {H}},\hat{\MakeUppercase {H}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}}}^{}{(\cdot )}$ which she can query polynomially many times. $\mathcal {B}$ starts $\mathcal {A}$ on $\mathsf {vk}_\mathsf {BS}:=({\MakeUppercase {H}},\hat{\MakeUppercase {H}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}})$. When queried on $\mathsf {Co}_i$, $\mathcal {B}$ forwards such query to her oracle and returns the answer to $\mathcal {A}$. Eventually, when $\mathcal {A}$ outputs her $k+1$ message-signatures tuples $\{(m_i,A_i,B_i)\}_{i=1}^{k+1}$, $\mathcal {B}$ returns that as the answer in her game. It is clear that $\mathcal {B}$ wins her game with the same advantage as that of $\mathcal {A}$ in her game. Thus, we have $\mathsf {Adv}_{\mathsf {BS},\mathcal {A}}^{\text {Unforge}} = \mathsf {Adv}_{\text {BSOM},\mathcal {B}}$.

Lemma 2

The construction is perfectly blind in the malicious-key model.

Proof

Since the Pedersen commitment is perfectly hiding, it is clear that $\mathsf {Co}$ sent by the user reveals no information about the committed message. Now the check we perform on the pre-signatures ensures that each pre-signature is valid on its respective commitment. If any of those pre-signatures is invalid, we return $(\perp ,\perp )$. It is obvious in the latter case the adversary gains no information about the order in which the messages were signed. If the checks on the pre-signatures pass, it means the first pre-signature is a valid signature on the message $m_{b}$ committed in $\mathsf {Co}_b$ whereas the second signature is valid on the message $m_{1-b}$ committed in $\mathsf {Co}_{1-b}$. From the adversary’s point of view each signature could be on either message since the commitment could have been on either message. What remains now is to show that $(A',B',C')$ are unlinkable to (A, B). By definition we have that ${\MakeUppercase {A'}}_0 \ne 1_{\mathbb {G}}$ and ${\MakeUppercase {A'}}_1 \ne 1_{\mathbb {G}}$. Now each final signature is computed by raising the corresponding pre-signature to a random exponent from $\mathbb {Z}^\times _p$. Thus, each final signature is uniformly distributed over the space of possible signatures and it follows that the final signature is independent of the pre-signature.    $\square$

5.2 Construction II

Here we present our second construction whose unforgeability is based on the BSOMI assumption. The high-level idea is similar to that of the first construction. When requesting a blind signature on the message $m \in \mathbb {Z}_p$, the user uses the Pedersen commitment scheme to commit to m as $\mathsf {Co}:=G^m H^r$ and sends the commitment $\mathsf {Co}$ to the signer. Here we view the commitment as the message M on which the oracle in the BSOMI assumption is queried. Now the signer, playing the role of the oracle in the definition of the BSOMI assumption, returns the tuple $(A',B',C')$. The user can check whether such a tuple corresponds to a valid pre-signature by first verifying that the last element (which is independent of the message) is constructed correctly. This is achieved by verifying that ${e}(C',\hat{\MakeUppercase {H'}})={e}(A',\hat{\MakeUppercase {Y}})$. If such a check does not pass, the user returns $\perp$. Otherwise, since the user already knows the randomness r she used in constructing the commitment $\mathsf {Co}$, she can now adapt the pre-signature $(A',B')$ on the commitment $\mathsf {Co}$ to one on the message m by letting $B' :=B' {C'}^{-r}$ and then randomizing the signature $(A',B')$ into a new one (A, B) so that the two pairs are unlinkable. Again as in our first construction, by assuming that the bilinear group generator $\mathcal {BG}$ is deterministic combined with the fact that the Pedersen commitment remains hiding even if the commitment key is generated maliciously, we achieve blindness w.r.t. malicious keys. The construction is detailed in Fig. 3.

Note that the checks performed in the ${\mathsf {Request}_{\mathsf {BS}}^0}$ algorithm to verify well-formedness of the signer’s verification key need only be performed once when requesting the first signature and not each time a signature is requested.

Fig. 3.

Our 2nd blind signature construction

The proof for the following theorem can be found in the full version [39].

Theorem 4

The construction is a secure blind signature scheme in the malicious-key model in the standard model.

Efficiency Comparison. We compare in Table 1 the efficiency of our blind signature constructions with the most efficient existing schemes offering the same security in the standard model [31, 33]. As can be seen from the table, our schemes outperform existing schemes in every efficiency metric. At 80-bit security, the size of our signatures is 40 bytes, i.e. $67\%$ shorter than those of [33]. Also, blindness in our schemes holds in the information-theoretic sense which is another advantage. The security of all schemes in the table including ours rely on interactive intractability assumptions. Note that the most efficient scheme based on non-interactive assumptions in the standard model [36] is much less efficient than the schemes in the table, e.g. the signature size in [36] is 183 group elements in symmetric bilinear groups. In the table, P stands for pairing, A for point addition, and MK Model for the malicious-key model.

Table 1. Efficiency comparison

6 Blind Schemes for a Vector of Messages

In this section we give constructions of blind signatures for a vector of messages. These constructions are extensions of their single-message counterparts in which we replace the single-message Pedersen commitment scheme by its generalized variant which allows committing to a vector of messages at once, and make the necessary changes.

Fig. 4.

A blind signature scheme I for a vector of messages $\in \mathbb {Z}_p^n$

6.1 Construction I

We show in Fig. 4 that we can without affecting the signature size or the number of pairings involved in the verification extend our scheme from Sect. 5.1 to blindly sign a vector of messages. This variant is unforgeable under the same assumption as the single-message scheme.

All the checks performed in the ${\mathsf {Request}_{\mathsf {BS}}^0}$ algorithm to verify well-formedness of the signer’s verification key need only be performed once when requesting the first signature and not each time a signature is requested.

Theorem 5

The scheme in Fig. 4 is a secure blind signature.

Proof

Correctness is straightforward to verify. Perfect blindness in the malicious-key model holds similarly to the perfect blindness of the single-message scheme. The following lemma proves unforgeability of the scheme.

Lemma 3

(Unforgeability). The scheme is unforgeable if the BSOM assumption is intractable.

Proof

Let $\mathcal {A}$ be an adversary against the unforgeability of the scheme. We show how to use $\mathcal {A}$ to construct an adversary $\mathcal {B}$ against the BSOM assumption. Adversary $\mathcal {B}$ gets the tuple $(\mathcal {P},{\MakeUppercase {H}},\hat{\MakeUppercase {H}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}})$ from her game and she has access to the oracle $\mathcal {O}\text {BSOM}_{{\MakeUppercase {H}},\hat{\MakeUppercase {H}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}}}^{}{(\cdot )}$ which she can query polynomially many times. $\mathcal {B}$ chooses $z_1, \ldots , z_{n-1} \leftarrow \mathbb {Z}^{\times }_p$ and computes $({\MakeUppercase {Z}}_i, \hat{\MakeUppercase {Z}}_i ):=({\MakeUppercase {G}}^{z_i}, \hat{\MakeUppercase {G}}^{z_i} )$ for all $i \in [n-1]$. She then starts $\mathcal {A}$ on $\mathsf {vk}_\mathsf {BS}:=({\MakeUppercase {H}},\hat{\MakeUppercase {H}},\hat{\MakeUppercase {X}},\hat{\MakeUppercase {Y}} , \{{\MakeUppercase {Z}}_i,\hat{\MakeUppercase {Z}}_i\}_{i=1}^{n-1})$. When queried on $\mathsf {Co}_i$, $\mathcal {B}$ forwards such query to her oracle and returns the answer to $\mathcal {A}$. Eventually, when $\mathcal {A}$ outputs her $k+1$ message-signature tuples $\{(\varvec{m}_i=(m_{i,1},\ldots ,m_{i,n}),A_i,B_i)\}_{i=1}^{k+1}$ where the vectors $\varvec{m}_i$ are distinct, $\mathcal {B}$ computes $m'_i =m_{i,1} + \sum _{j=2}^{n} z_{j-1} m_{i,j}$ for all $i \in [k+1]$ and returns the $k+1$ tuples $\{(m'_i,A_i,B_i)\}_{i=1}^{k+1}$ as the answer in her game. It is clear that $\mathcal {B}$ wins her game with the same advantage as that of $\mathcal {A}$ in her game. Thus, we have $\mathsf {Adv}_{\mathsf {BS},\mathcal {A}}^{\text {Unforge}} = \mathsf {Adv}_{\text {BSOM},\mathcal {B}}$.    $\square$

6.2 Construction II

We extend our scheme from Sect. 5.2 to blindly sign a vector of messages as shown in Fig. 5. This scheme is unforgeable under the same assumption as the single-message scheme.

Fig. 5.

A blind signature scheme II for a vector of messages $\in \mathbb {Z}_p^n$

All the checks performed in the ${\mathsf {Request}_{\mathsf {BS}}^0}$ algorithm to verify well-formedness of the signer’s verification key need only be performed once when requesting the first signature and not each time a signature is requested.

The proof for the following theorem can be found in the full version [39].

Theorem 6

The scheme in Fig. 5 is a secure blind signature.

7 Partially Blind Signature Schemes

Here we show how to modify our schemes in Sects. 6.1 and 6.2 to obtain partially blind signature schemes. For more generality, we give schemes where the public information is also a vector $\varvec{\tau }=(\tau _1, \ldots , \tau _{n'}) \in \mathbb {Z}^{n'}_p$. This allows to attach multiple attributes to the signature.

7.1 Construction I

To realize our first construction, we modify the blind scheme on vector messages from Sect. 6.1 to attach a vector $\varvec{\tau }=(\tau _1, \ldots , \tau _{n'}) \in \mathbb {Z}^{n'}_p$ of public information to the signature. To do so, we add to the public key of the scheme in Fig. 4 the elements $\hat{\MakeUppercase {W}}_i:=\hat{\MakeUppercase {G}}^{w_i}$ for some randomly chosen elements $w_i \leftarrow \mathbb {Z}_p$ for $i=1,\ldots , n'$. When asked to sign a commitment $\mathsf {Co}$ along with the public information $\varvec{\tau }$, the signer signs the modified commitment $\mathsf {Co}':=\mathsf {Co}G^{\sum _{i=1}^{n'} \tau _i w_i}$. Upon receiving the pre-signature, the user checks that it is valid on the tuple $(\varvec{m},\varvec{\tau })$. The details of the construction are in Fig. 6. The unforgeability of the scheme relies on a slight extension of the BSOM assumption which we refer to as the E-BSOM assumption. See full version [39] for details.

All the checks performed in the ${\mathsf {Request}_{\mathsf {BS}}^0}$ algorithm to verify well-formedness of the signer’s verification key need only be performed once when requesting the first signature and not each time a signature is requested.

The proof for the following theorem can be found in the full version [39].

Theorem 7

The scheme in Fig. 6 is a secure partially blind signature.

Fig. 6.

A partially blind signature scheme I for a vector of messages $\in \mathbb {Z}_p^n$

7.2 Construction II

Our second partially blind signature construction shown in Fig. 7 is an extension of our blind construction from Fig. 5 in a similar manner to the first construction. The unforgeability of the scheme relies on a slight extension of the BSOMI assumption which we refer to as the E-BSOMI assumption. See full version [39] for details.

The proof for the following theorem can be found in the full version [39].

Theorem 8

The scheme in Fig. 7 is a secure partially blind signature.

Fig. 7.

A partially blind signature scheme II for a vector of messages $\in \mathbb {Z}_p^n$