Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Blind signatures allow a user (or obtainer) to obtain a signature from a signer (or issuer) without the latter learning the message that is actually signed. They are an important building block for various privacy and anonymity related applications including e-cash, e-voting, anonymous credentials and ticketing. Since their invention by Chaum [18], research has led to numerous blind signature schemes in various settings and models [2, 15, 16, 39]. The most appealing setting is that of (i) round-optimal schemes, i.e., schemes that require only two moves (and are thus automatically concurrently secure), that (ii) do not require any heuristic assumptions (such as random oracles) nor (iii) a setup assumption, such as common reference strings or honestly generated keys.

Blindness is formalized by a game between a malicious signer and a challenger who asks for two blind signatures on messages of the signer’s choice, but in random order. If both signature issuings succeed, the signer is given the resulting signatures and should not be able to tell in which order they were signed. It is natural to let the malicious signer choose its own key pair (rather than having the challenger create it), in which case we speak of the malicious-key model.

There are well known efficient round-optimal constructions in the honest-key model with security proofs in the random oracle model [11, 15, 19]; and there are various constructions without random oracles and in the malicious-key model, but relying on a trusted setup, such as a common reference string (CRS). Among those are constructions using structure-preserving signatures [4] and Groth-Sahai (GS) proofs [31] instantiating the framework of Fischlin [21], as well as other approaches in the bilinear group setting [12–14, 43]. There is also a very recent construction [33] without a CRS but relying on non-falsifiable “knowledge” assumptions with security in the honest-key model. Some constructions [16, 30] require both a CRS and honestly generated keys.

Round-Optimal Schemes in the Plain Model. Until now, only very few schemes [26–28] were proposed that are round-optimal and require neither random oracles nor setup assumptions, that is, satisfying (i)–(iii). Due to known impossibility results, such constructions are indeed hard to find. Lindell [38] showed that concurrently secure blind signatures are impossible in the standard model when relying on simulation-based security notions. Later, Fischlin and Schröder [23] proved that black-box reductions from unforgeability to non-interactive assumptions in the standard model are impossible for blind signature schemes satisfying certain conditions.

Known constructions bypass these impossibility results in several ways: All rely on game-based security definitions [42] instead of simulation-based ones. The constructions due to Garg et al. [28] as well as Garg and Gupta [27] make use of complexity leveraging in their proofs and thus do not use black-box reductions. The first scheme [28] can only be considered a feasibility result and the second [27] is still too inefficient for practical applications. In contrast, the most recent construction by Fuchsbauer et al. [26], whose signatures consist of 5 elements from a bilinear group, can be considered practical. It is based on the recent concept of structure-preserving signature schemes on equivalence classes (SPS-EQ) [25, 32], whose unforgeability is proven in the generic group model, and commitments. A drawback of the scheme is that blindness (in the malicious-key model) is proven under an interactive assumption.

The FHS Construction. Before looking at the ideas underlying the FHS construction, let us recall SPS-EQ. Defined over groups equipped with a bilinear map \(e:\mathbb {G}_1\times \mathbb {G}_2\rightarrow \mathbb {G}_T\), structure-preserving signatures [4] are schemes whose verification keys, signatures and messages all consist of elements from the base groups \(\mathbb {G}_1\) and \(\mathbb {G}_2\) and signatures are verified by evaluating the bilinear map on these elements. In SPS-EQ the message space, typically \(\mathbb {G}_1^\ell \) for some \(\ell >1\), is partitioned into equivalence classes, where all multiples of a vector belong to one class. These classes should be indistinguishable, that is, it should be hard to tell whether two messages belong to the same class or not (which follows from DDH in \(\mathbb {G}_1\)).

Given an SPS-EQ signature on a message, anyone can publicly adapt the signature to a different representative of the same class. Unforgeability is therefore defined w.r.t. equivalence classes, that is, after being given signatures on messages of its choice, no adversary should be able to compute a signature on a message from a different class. SPS-EQ moreover guarantees that after signing a message, not even the signer is able to distinguish an adaptation of the signature to another representative of the same class from a fresh signature on a completely random message.

The FHS blind-signature scheme [26] works as follows: the obtainer assembles a representative of an equivalence class as a vector containing a commitment to the message and a normalization element (the group generator). She then blinds this message by changing it to another representative and sends it to the signer. The signer signs the representative and sends the signature to the obtainer. Given this signature, the obtainer adapts it to a signature on the original representative. (Due to the normalization element, the obtainer can only switch back to the original representative.) The blind signature is then the rerandomized (unlinkable) signature for the original representative, which contains a commitment to the message, plus an opening of the commitment.

The FHS scheme uses a variant of Pedersen commitments that are perfectly hiding and computationally binding under the co-DHI\(_1^*\) assumption (cf. Sect. 3.1 for a more detailed discussion). The commitment key is part of the signer’s public key, which guarantees that the obtainer cannot open commitments to different messages (and thereby break unforgeability). Consequently, unforgeability relies on the co-DHI\(_1^*\) assumption in addition to EUF-CMA security of the SPS-EQ scheme. To prove blindness in the malicious-key model (where the reduction has no access to the adversarially generated signing key), FHS argue that during the blindness game the adversary must always produce valid SPS-EQ signatures, as otherwise the challenger does not send any blind signatures in the end, in which case the adversary cannot win the game as all it sees are perfectly hiding commitments.

Intuitively, blindness follows, since under the DDH assumption the randomization of the representative containing the commitment during signature issuing can be replaced by a random representative of a random class. In the latter case, the order in which the messages are signed is perfectly hidden and thus the adversary cannot win. However, since the commitment key is chosen by the adversary, to actually make this replacement, FHS need an interactive assumption. Moreover, this replacement is only indistinguishable to a simulator that does not know the randomization of the representative used. This however means that the simulator cannot later adapt back the signer’s SPS-EQ signatures in order to produce the blind signatures. FHS overcome this by relying on SPS-EQ security, which guarantees that adapted signatures look like fresh ones. Thus, if the reduction knew the signing key (which is the case in the honest-key model) then it could simply produce the final blind signatures by itself. In the malicious-key model, the reduction computes the fresh signatures by using the adversary as a signing oracle: it runs the adversary to obtain these signatures and then rewinds it. In the second (and actual) run, it embeds an (interactive) DDH instance and uses the signatures from the first run.

Open Questions. As the FHS scheme is the most efficient scheme having all the discussed properties, it would be desirable to base its security (or that of a related scheme) on weaker assumptions. The first question we ask is whether one can relate the unforgeability of a blind signature scheme based on SPS-EQ directly to the EUF-CMA security of the latter without necessitating any further assumptions. Even more interesting would be whether it is possible to remove the requirement for an interactive assumption for blindness. To address the first question, instead of the perfectly hiding commitment, one could use a perfectly binding one, as then each SPS-EQ signature from the signer can only be opened in one way, meaning that SPS-EQ unforgeability would directly imply blind-signature unforgeability. This however means that the commitment key cannot be chosen by the signer anymore, as knowing the underlying randomness could allow the signer to break hiding of the commitment and thus blindness of the scheme. But even if we let the user choose the commitment key, the information-theoretic argument by FHS that a signer must send valid SPS-EQ signatures does not apply anymore: even when not seeing the final blind signatures, the signer still obtains information on which message corresponds to which issuing, as the commitments are only computationally hiding.

Our Contribution. We answer the two above questions in the affirmative and reduce the strength of the required assumptions for both security notions. We construct a variant of the FHS blind signature scheme and prove unforgeability solely under the EUF-CMA security of the underlying SPS-EQ scheme. More importantly, we show that our scheme is blind in the malicious-key model under a non-interactive (and non-“q-type”) assumption, namely an extension of the bilinear DDH assumption in asymmetric bilinear groups.

Our scheme replaces the perfectly hiding commitments in FHS by perfectly binding ones, which means unforgeability follows directly from SPS-EQ unforgeability. As there are no trusted parameters, we let the user choose the commitment key during signature issuing and include it in the final signature. Straight-forward implementation of this approach however turns out not to result in a blind scheme. We therefore “distribute” the commitment key over several group elements, which enables us to show blindness.

Our blindness proof follows FHS’s idea of rewinding the signer in order to use it as a signing oracle for signatures which the simulator cannot adapt on its own. The proof is however much more involved, since we need to consider adversaries that might return invalid SPS-EQ signatures but still break blindness. Our proof works by rewinding the blindness adversary numerous times to increase the success probability of the reduction noticeably beyond one half. We moreover show in the full version that these multiple rewinds are necessary by giving a counterexample for the case of only rewinding once.

Organization. Sect. 2 discusses preliminaries including signature schemes on equivalence classes (SPS-EQ). Section 3 discusses blind signatures, the FHS construction and presents our construction of round-optimal blind signatures and the extension to partially blind signatures.

2 Preliminaries

A function \(\epsilon :\mathbb {N}\rightarrow \mathbb {R}^+\) is called negligible if for all \(c > 0\) there is a \(k_0\) such that \(\epsilon (k) < 1/k^c\) for all \(k > k_0\). By , we denote that a is chosen uniformly at random from a set S. Furthermore, we write \(\mathsf{A}(a_1,\dots ,a_n; r)\) if we want to make the randomness r used by a probabilistic algorithm \(\mathsf{A}(a_1,\dots ,a_n)\) explicit and denote by \([\mathsf{A}(a_1,\dots ,a_n)]\) the set of points with positive probability of being output by \(\mathsf A\). For an (additive) group \(\mathbb {G}\) we use \(\mathbb {G}^*\) to denote \(\mathbb {G}\setminus \{0_\mathbb {G}\}\).

Definition 1

(Bilinear Map). Let \(\mathbb {G}_1\), \(\mathbb {G}_2\) and \(\mathbb {G}_T\) be cyclic groups of prime order p, where \(\mathbb {G}_1\) and \(\mathbb {G}_2\) are additive and \(\mathbb {G}_T\) is multiplicative. Let P and \(\hat{P}\) be generators of \(\mathbb {G}_1\) and \(\mathbb {G}_2\), resp. We call \(e:\mathbb {G}_1\times \mathbb {G}_2 \rightarrow \mathbb {G}_T\) a bilinear map or pairing if it is efficiently computable and it is:

 

Bilinear::

\(e(aP, b\hat{P}) = e(P,\hat{P})^{ab} = e(bP,a\hat{P}) ~~~ \forall \, a,b\in \mathbb {Z}_p\),

Non-degenerate::

\(e(P,\hat{P}) \ne 1_{\mathbb {G}_T}\), i.e., \(e(P,\hat{P})\) generates \(\mathbb {G}_T\).

 

If \(\mathbb {G}_1 = \mathbb {G}_2\) then e is symmetric (Type-1) and asymmetric (Type-2 or 3) otherwise. For Type-2 pairings there is an efficiently computable isomorphism \(\varPsi :\mathbb {G}_2 \rightarrow \mathbb {G}_1\); for Type-3 pairings no such isomorphism is known. Type-3 pairings are currently the optimal choice in terms of efficiency for a given security level [17].

Definition 2

(Bilinear-Group Generator). A bilinear-group generator \(\mathsf BGGen\) is a (possibly probabilisticFootnote 1) polynomial-time algorithm that takes a security parameter \(1^\kappa \) and outputs a bilinear group description \(\mathsf{BG}=(p,\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T,e,P,\hat{P})\) consisting of groups \(\mathbb {G}_1 = \langle P \rangle \), \(\mathbb {G}_2 = \langle \hat{P} \rangle \) and \(\mathbb {G}_T\) of prime order p with \(\log _2 p = \lceil \kappa \rceil \) and an asymmetric pairing \(e:\mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T\).

Definition 3

(DDH). Let \(\mathsf BGGen\) be a bilinear-group generator that outputs \(\mathsf{BG}=(p,\mathbb {G}_1,\mathbb {G}_2, \mathbb {G}_T, e,P_1 = P,P_2 = \hat{P})\). For \(i\in \{1,2\}\) the decisional Diffie-Hellman assumption holds in \(\mathbb {G}_i\) for \(\mathsf BGGen\) if for all PPT adversaries \(\mathcal {A}\) there is a negligible function \(\epsilon (\cdot )\) such that

The next assumption is in the spirit of the bilinear Diffie-Hellman assumption (BDDH) [35], which in symmetric bilinear groups states that given rP, uP, vP, the element ruvP looks random. In asymmetric groups, we can additionally give uvP, \(u\hat{P}\) and \(v\hat{P}\). We therefore call the assumption ABDDH\(^+\).

Definition 4

(ABDDH \(^+\) ). Let \(\mathsf BGGen\) be a bilinear-group generator that outputs \(\mathsf{BG}=(p,\mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, e,P_1 = P,P_2 = \hat{P})\). The ABDDH\(^+\) assumption holds for \(\mathsf{BGGen}\) if for all PPT algorithms \(\mathcal {A}\) there is a negligible function \(\epsilon (\cdot )\) such that

In the generic group model, in order to distinguish ruvP from random, one basically needs to construct this element in the target group. It is easily seen that this cannot be done from the remaining elements, which we now make formal:

Proposition 1

The assumption in Definition 4 holds in generic groups and reaches the optimal, quadratic simulation error bound.

We prove the above proposition in the full version. Moreover, note that given an ABDDH\(^+\) instance \((\mathsf{BG},R,U,W,\hat{U},\hat{V},T)\), we could use a DDH oracle to decide it: simply query \((\mathsf{BG},R,W,T)\) to the oracle and return the result. We thus have:

Lemma 1

If ABDDH\(^+\) holds for a bilinear-group generator \(\mathsf{BGGen}\) then DDH in \(\mathbb {G}_1\) also holds for it.

2.1 SPS on Equivalence Classes

Structure-preserving signatures (SPS) [3–8, 10, 24, 29, 37] can handle messages that are elements of a bilinear group, without requiring any prior encoding. In such a scheme public keys, messages and signatures consist only of group elements and the verification algorithm evaluates a signature by deciding group membership of signature elements and by evaluating pairing-product equations (PPEs).

The notion of SPS on equivalence classes (SPS-EQ) was introduced by Hanser and Slamanig [32]. Their initial instantiation was only secure against random-message attacks, but together with Fuchsbauer [25] they subsequently presented a scheme that they proved EUF-CMA-secure in the generic group model.

The idea is as follows. For a prime p, \(\mathbb {Z}_p^\ell \) is a vector space. Thus, if \(\ell > 1\) we can define a projective equivalence relation on it, which propagates to \(\mathbb {G}_i^\ell \) and partitions \(\mathbb {G}_i^\ell \) into equivalence classes. Let \(\sim _\mathcal {R}\) be this relation, i.e., for \(M, N \in \mathbb {G}_i^\ell \) we have \(M \sim _\mathcal {R}N \Leftrightarrow \exists \, s\in \mathbb {Z}_{p}^* : M = s N\). An SPS-EQ scheme signs an equivalence class \([M]_\mathcal{R}\) for \(M \in (\mathbb {G}_i^*)^\ell \) by actually signing a representative M of \([M]_\mathcal {R}\). It then allows to switch to other representatives of \([M]_\mathcal {R}\) and to update the corresponding signature without having access to the secret key. If the DDH assumption holds on the message space, then a random representative of a given class \([M]_\mathcal {R}\) is indistinguishable from a message vector outside of \([M]_\mathcal {R}\). Moreover, the malicious-key perfect adaptation property (defined in Definition 9) guarantees that updated signatures are random elements in the corresponding space of signatures. The combination of both properties implies the unlinkability of message-signature pairs (under the same \(\mathsf{pk}\)) corresponding to the same class.

The Abstract Signature Scheme. Here, we discuss the abstract model, the security model of such a signature scheme [25, 26, 32] and a concrete construction, as presented in [25].

Definition 5

(SPS-EQ). A structure-preserving signature scheme for equivalence relation \(\mathcal {R}\) over \(\mathbb {G}_i\) with \(i \in \{1,2\}\) is a tuple SPS-EQ of the following PPT algorithms:

 

\(\mathsf{BGGen}_\mathcal {R}(1^\kappa )\) :

is a (probabilistic) bilinear-group generation algorithm which on input a security parameter \(1^\kappa \) outputs a prime-order bilinear group \(\mathsf BG\).

\(\mathsf{KeyGen_\mathcal {R}}(\mathsf{BG},1^\ell )\) :

is a probabilistic algorithm which on input a bilinear group \(\mathsf{BG}\) and a vector length \(\ell >1\) (in unary) outputs a key pair \((\mathsf{sk},\mathsf{pk})\).

\(\mathsf{Sign_\mathcal {R}}(M,\mathsf{sk})\) :

is a probabilistic algorithm which on input a representative \(M \in (\mathbb {G}_i^*)^\ell \) of an equivalence class \([M]_\mathcal {R}\) and a secret key \(\mathsf{sk}\) outputs a signature \(\sigma \) for the equivalence class \([M]_\mathcal {R}\).

\(\mathsf{ChgRep_\mathcal {R}}(M, \sigma , \mu , \mathsf{pk})\) :

is a probabilistic algorithm, which on input a representative \(M \in (\mathbb {G}_i^*)^\ell \) of an equivalence class \([M]_\mathcal {R}\), a signature \(\sigma \) for M, a scalar \(\mu \) and a public key \(\mathsf{pk}\) returns an updated message-signature pair \((M', \sigma ')\), where \(M'=\mu \cdot M\) is the new representative and \(\sigma '\) its updated signature.

\(\mathsf{Verify_\mathcal {R}}(M,\sigma ,\mathsf{pk})\) :

is a deterministic algorithm which given a representative \(M \in (\mathbb {G}_i^*)^\ell \), a signature  \(\sigma \) and a public key \(\mathsf{pk}\) outputs \(1\) if \(\sigma \) is valid for M

\(\mathsf{VKey_\mathcal {R}}(\mathsf{sk},\mathsf{pk})\) :

is a deterministic algorithm which given a secret key \(\mathsf{sk}\) and a public key \(\mathsf{pk}\) checks their consistency and returns \(1\) on success and \(0\) otherwise.

 

An SPS-EQ scheme SPS-EQ defined on message-space \(\mathbb {G}_i\) is secure if the DDH assumption holds in \(\mathbb {G}_i\), if SPS-EQ is correct, EUF-CMA secure and if it perfectly adapts signatures.

Definition 6

(Correctness). An SPS-EQ scheme \(\textsf {SPS-EQ}\) over \(\mathbb {G}_i\) with \(i \in \{1,2\}\) is correct if for all security parameters \(\kappa \in \mathbb {N}\), for all \(\ell >1\), all bilinear groups \(\mathsf{BG} = (p,\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T,e,P,\hat{P}) \in [\mathsf{BGGen}_\mathcal {R}(1^\kappa )]\), all key pairs \((\mathsf{sk},\mathsf{pk})\in [\mathsf{KeyGen_\mathcal {R}}(\mathsf{BG},1^\ell )]\), all messages \(M \in (\mathbb {G}_i^*)^\ell \) and all scalars \(\mu \in {\mathbb {Z}_p}^{*}\) we have:

$$\begin{aligned}&\mathsf{VKey}_\mathcal {R}(\mathsf{sk},\mathsf{pk}) = 1\quad \text {and}\\&\Pr \big [\mathsf{Verify_\mathcal {R}}(M, \mathsf{Sign_\mathcal {R}}(M,\mathsf{sk}),\mathsf{pk})=1\big ] = 1 \quad \text {and}\\&\Pr \big [\mathsf{Verify_\mathcal {R}}(\mathsf{ChgRep_\mathcal {R}}(M, \mathsf{Sign_\mathcal {R}}(M,\mathsf{sk}), \mu , \mathsf{pk}),\mathsf{pk})=1\big ] = 1. \end{aligned}$$

In contrast to the standard unforgeability definition for signatures, EUF-CMA security for SPS-EQ is defined with respect to equivalence classes, i.e., a forgery is a signature on a message from an equivalence class from which the adversary has not asked any messages to be signed.

Definition 7

(EUF-CMA). An SPS-EQ scheme SPS-EQ over \(\mathbb {G}_i\) with \(i \in \{1,2\}\) is existentially unforgeable under adaptive chosen-message attacks if for all \(\ell > 1\) and all PPT algorithms \(\mathcal {A}\) having access to a signing oracle \(\mathsf{Sign}_\mathcal {R}(\cdot , \mathsf{sk})\), there is a negligible function \(\epsilon (\cdot )\) such that:

where Q is the set of queries that \(\mathcal {A}\) has issued to the signing oracle.

The next two definitions were introduced in [26]. They formalize the notion that signatures output by \(\mathsf ChgRep_\mathcal {R}\) are distributed like fresh signatures on the new representative.

Definition 8

(Signature Adaptation). Let \(\ell > 1\). An SPS-EQ scheme \(\mathsf{SPS-EQ} \) on \((\mathbb {G}_i^*)^\ell \) with \(i \in \{1,2\}\) perfectly adapts signatures if for all tuples \((\mathsf{sk},\mathsf{pk}, M,\sigma ,\mu )\) with

$$\begin{aligned} \mathsf{VKey}_\mathcal {R}(\mathsf{sk},\mathsf{pk})&=1&\mathsf{Verify}_\mathcal {R}(M,\sigma ,\mathsf{pk})&= 1&M&\in (\mathbb {G}_i^*)^\ell&\mu&\in {\mathbb {Z}_p}^{*}\end{aligned}$$

\(\mathsf{ChgRep_\mathcal {R}}(M,\sigma ,\mu ,\mathsf{pk})\) and \((\mu M, \mathsf{Sign_\mathcal {R}}(\mu M,\mathsf{sk}))\) are identically distributed.

The following definition demands that this even holds for maliciously generated verification keys. As for such keys there might not even exist a corresponding secret key, we require that adapted signatures are random elements in the space of valid signatures.

Definition 9

(Signature Adaptation Under Malicious Keys). Let \(\ell > 1\). An SPS-EQ scheme \(\mathsf{SPS-EQ} \) on \((\mathbb {G}_i^*)^\ell \) with \(i \in \{1,2\}\) perfectly adapts signatures under malicious keys if for all tuples \((\mathsf{pk},M, \sigma , \mu )\) with

$$\begin{aligned} \mathsf{Verify}_\mathcal {R}(M,\sigma ,\mathsf{pk})&= 1&M&\in (\mathbb {G}_i^*)^\ell&\mu&\in {\mathbb {Z}_p}^{*}\end{aligned}$$
(1)

we have that \(\mathsf{ChgRep_\mathcal {R}}(M,\sigma ,\mu ,\mathsf{pk})\) outputs \((\mu M,\sigma ')\) such that \(\sigma '\) is uniformly random in the space of signatures, conditioned on \(\mathsf{Verify_\mathcal {R}}(\mu M,\sigma ',\mathsf{pk}) =1\).

In Fig. 1, we restate the SPS-EQ construction from [25]. It is EUF-CMA secure in the generic group model and satisfies Definitions 8 and 9.

Fig. 1.
figure 1

Scheme 1, an EUF-CMA secure SPS-EQ scheme

Full size image

3 Blind Signatures

Before we discuss the construction from [26] and then present our new blind signature construction, we give the abstract model and the security properties of blind signature schemes. These are correctness, unforgeability and blindness and were initially studied in [36, 41] and later on rigorously treated in [22, 42].

Definition 10

(Blind Signature Scheme). A blind signature scheme \(\mathsf{{BS}}\) consists of the following PPT algorithms:

 

\(\mathsf{KeyGen}_\mathsf{{BS}}(1^\kappa )\),:

on input \(\kappa \), returns a key pair \((\mathsf{sk}, \mathsf{pk})\). The security parameter \(\kappa \) is also an (implicit) input to the following algorithms.

\((\mathcal {U}_\mathsf{{BS}}(m, \mathsf{pk}), \mathcal {S}_\mathsf{{BS}}(\mathsf{sk}))\) :

are run by a user and a signer, who interact during execution. \(\mathcal {U}_\mathsf{{BS}}\) gets input a message m and a public key \(\mathsf{pk}\) and \(\mathcal {S}_\mathsf{{BS}}\) has input a secret key \(\mathsf{sk}\). At the end \(\mathcal {U}_\mathsf{{BS}}\) outputs \(\sigma \), a signature on m, or \(\bot \) if the interaction was not successful.

\(\mathsf{Verify_\mathsf{{BS}}}(m, \sigma , \mathsf{pk})\) :

is deterministic and given a message-signature pair \((m, \sigma )\) and a public key \(\mathsf{pk}\) outputs \(1\) if \(\sigma \) is valid on m under \(\mathsf{pk}\) and \(0\) otherwise.

 

A blind signature scheme \(\mathsf{{BS}}\) is secure if it is correct, unforgeable and blind.

Definition 11

(Correctness). A blind signature scheme \(\mathsf{{BS}}\) is correct if for all security parameters \(\kappa \in \mathbb {N}\), all key pairs \((\mathsf{sk},\mathsf{pk})\in [\mathsf{KeyGen_\mathsf{{\tiny BS}}}(1^\kappa )]\), all messages m and all signatures \(\sigma \in [({\mathcal {U}_\mathsf{{\tiny BS}}}(m, \mathsf{pk}), {\mathcal {S}_\mathsf{{\tiny BS}}}(\mathsf{sk}))]\) it holds that \(\mathsf{Verify_\mathsf{{\tiny BS}}}(m,\sigma ,\mathsf{pk})=1\).

Definition 12

(Unforgeability). \(\mathsf{{BS}}\) is unforgeable if for all PPT algorithms \(\mathcal {A}\) having access to a signer oracle, there is a negligible function \(\epsilon (\cdot )\) such that:

$$\Pr \!\left[ \! \begin{array}{l} (\mathsf{sk},\mathsf{pk})\leftarrow \mathsf{KeyGen_\mathsf{{BS}}}(1^\kappa ), \\ (m_i^*, \sigma _i^*)_{i=1}^{k+1} \!\leftarrow \! \mathcal {A}^\mathsf{(\cdot , \mathcal {S}_\mathsf{{BS}}(\mathsf{sk}))}(\mathsf{pk}) \end{array} : \begin{array}{c} m_i^* \ne m_j^* ~ \forall i,j \in [k\!+\!1], i \ne j ~~ \wedge \\ \mathsf{Verify_\mathsf{{BS}}}(m_i^*,\sigma _i^*, \mathsf{pk}) \!=\! 1~ \forall i \in [k\!+\!1] \end{array} \right] \le \epsilon (\kappa ), $$

where k is the number of completed interactions with the oracle.

There are several different kinds of blindness, where the strongest (and arguably most natural) definition is blindness in the malicious-key model [1, 40]. In this case, the public key is generated by the adversary, whereas in the weaker honest-key model the key pair is initially set up by the environment, i.e., it requires a trusted setup. We use the stronger notion to prove the blindness of our construction—as also done by other existing round-optimal standard-model constructions [26–28]:

Definition 13

(Blindness). A blind signature scheme \(\mathsf{{BS}}\) is called blind in the malicious-key model if for all PPT algorithms \(\mathcal {A}\) having one-time access to two user oracles, there is a negligible function \(\epsilon (\cdot )\) such that:

3.1 The FHS Construction

The construction in [26] uses unconditionally hiding commitments to the messages and SPS-EQ to sign these commitments. The latter allows for blinding and unblinding, as it implies the ability to derive a signature for arbitrary representatives of this class (without knowing the private signing key). The construction is unforgeable under the EUF-CMA security of the SPS-EQ and an asymmetric-group variant of the Diffie-Hellman inversion assumption. It is blind under an interactive DDH variant in the malicious-key model without requiring any trusted setup. Its design principle is as follows.

A signer public key consists of an SPS-EQ verification key \(\mathsf{pk}\) and two elements \((Q=qP, \hat{Q}=q\hat{P})\) for some random \(q\in {\mathbb {Z}_p}^{*}\). When asking for a signature on a message m, the user picks and creates a Pedersen commitment \(C=mP+rQ\) and forms a vector (C, P), which is a representative of equivalence class \([(C,P)]_\mathcal {R}\). Then she chooses a randomizer and uses it to randomize (C, P) to another representative (sC, sP), thereby blinding the vector, and sends (sC, sP) to the signer. When the signer returns an SPS-EQ signature on (sC, sP), the user is able to derive a signature for the unblinded (original) message (C, P), using SPS-EQ’s changing of representatives. Verification of the blind signature will only accept messages whose second component is P. Together with SPS-EQ unforgeability, this means that the only such message for which the user can derive a signature is (C, P).

The Pedersen commitment \(C=mP+rQ\) has a tweaked opening, which is (m, rP) instead of (m, r), and which lets one check the well-formedness of C via the pairing equation \(e(C - mP, \hat{P}) =e(rP, \hat{Q})\). This can be thought of as showing knowledge of the discrete logarithm r without revealing it (revealing r would lead to attacks against blindness). Under the co-DHI\(_1^*\) assumption commitments with opening of this form are binding, meaning the user can open a commitment only to one message, which is required for blind-signature unforgeability. The user includes the values \(T \leftarrow C - mP\) and \(R \leftarrow rP\) in the blind signature to allow the verification of the opening.

Blindness intuitively follows from the fact that the message \((sC,sP) = (smP+srQ,sP)\) that the signer sees during issuing looks unrelated to the message m and the resulting blind signature (which contains rP): under DDH, given sP and rP, the element srP looks random. However, the blinding factor in the randomized commitment is not srP but srQ, with Q chosen by the signer. This is what forced FHS to introduce an interactive variant of DDH, where the adversary chooses Q and \(\hat{Q}\) and then gets an instance rP, rQ, sP, tQ and needs to decide whether \(t=rs\).

3.2 Construction

In previous round-optimal blind-signature schemes (using a related approach involving commitments) the commitment is done w.r.t. a commitment key contained in the CRS. Since we aim at constructing a scheme in the standard model where there is no CRS, we could add the commitment key to the signer’s public key—as done in [26]. In this case the commitment must be perfectly hiding and can thus only be computationally binding. (Binding protects the signer from a user generating signatures on more messages than signatures issued by the signer.) We choose a different approach, namely to let the user choose the commitment key. To prevent forgeries, the commitment now needs to be perfectly binding, which we achieve by using an encryption scheme. We then show that, together with the properties of the used SPS-EQ scheme, computational hiding of the commitment implies blindness of our construction.

In our signing protocol the user chooses a public key Q for ElGamal encryption and then commits to the message m by encrypting mP as \((C,R)=(mP+rQ,rP)\). The user then forms a vector (C, R, Q, P), consisting of the ciphertext, the public key and the group generator P. (Note that this vector uniquely defines m.) Next, to blind the message, the user transforms this tuple to a random element of the equivalence class \([(C,R,Q,P)]_\mathcal {R}\): she picks , computes \(M\leftarrow (sC,sR,sQ,sP)\), and sends M to the signer. When the signer returns an SPS-EQ signature on (sC, sR, sQ, sP), the user derives a signature for the unblinded (original) message (C, R, Q, P). For unforgeability, this unblinding must be unambiguous, which is why verification only accepts tuples whose last component is P.

Finally, the user needs to “open” \((C,R,Q\!=\!qP)\) to the actual message m. This could be done by publishing \(Z=rQ\) and \(\hat{Q}=q\hat{P}\): then for a message m we could check whether the signature is valid on \((mP+Z,R,Q,P)\) and whether Z is of the correct form, by checking \(e(Q,\hat{P})=e(P,\hat{Q})\) and

$$\begin{aligned} e(Z,\hat{P})=e(R,\hat{Q}). \end{aligned}$$
(2)

This is basically the opening that FHS use (where \(\hat{Q}\) is part of the commitment key). In their scheme R is only given in the final signature; here however, the signer also sees sR, which leads to the following attack: The signer can check whether \(M=(sC,sR,sQ,sP)\) received during the signing protocol corresponds to a particular m, by testing \(e(M_1-mM_4,\hat{P})=e(M_2,\hat{Q})\), since this corresponds to the pairing equation \(e(srQ,\hat{P}) = e(srP,\hat{Q})\).

To prevent this attack, we “split” the logarithm of Q and define \(Q=uvP\). Instead of publishing \(\hat{Q}\), we publish \(X=ruP\) and \(\hat{V}=v\hat{P}\) and replace the RHS of (2) with \(e(X,\hat{V})=e(r\cdot uvP,\hat{P})\). Now we additionally need to enable a check that X and \(\hat{V}\) are correctly formed, which we do by publishing \(U=uP\) and \(\hat{U}=u\hat{P}\). As in [25, 26], we assume the bilinear group generation algorithm of the SPS-EQ scheme to be deterministic and to produce one bilinear group per security parameter. We then show that assuming ABDDH\(^+\) for such a group generation algorithm, our scheme satisfies malicious-key blindness. Our blind-signature scheme is detailed in Fig. 2.

Fig. 2.
figure 2

A blind signature scheme from SPS-EQ.

Full size image

3.3 Security

The correctness of the scheme in Fig. 2 follows by inspection.

Theorem 1

If the underlying SPS-EQ scheme is EUF-CMA secure, then the scheme in Fig. 2 is unforgeable.

Unforgeability of the SPS-EQ scheme guarantees that after k signing queries the adversary possesses only signatures on k tuples of the form \((C_i,R_i,Q_i,P)\). (Since the last component fixes each equivalence class to one representative.) It remains to show that each such tuple can only be opened to one message m: let (C, R, Q, P) and \(\sigma \) be such a valid message-signature pair. Then we show that any choice of \((Y,U,X,\hat{U},\hat{V})\) that satisfies verification together with \((\sigma ,Q,R)\) leads to the same m. Let u, v be such that \(\hat{U}=u\hat{P}\) and \(\hat{V}=v\hat{P}\). Then by (3.2), the 2nd equation in (3): \(Q=uvP\); and (4.1) implies \(U=uP\). With r s.t. \(R=rP\), we have \(X=ruP\) by (4.2) and \(Y=ruv=rQ\) by (4.3). This means that R and Q uniquely determine Y, which together with \(C = mP + Y\) uniquely determines m.

The formal proof is given in the full version. The reduction has a natural security loss determined by the number of signing queries by the adversary, since the reduction has to guess which of the \(k+1\) valid signatures is the forgery.

Blindness. In the full version, we first show that ABDDH\(^+\) (Definition 4) implies that when given \(rQ,Q,R,U,X,\hat{U},\hat{V}\) (the elements which the signer sees in the final signature), the elements srQ (the blinding factor of the message in the issuing protocol), and sQ, srP and sP (the remaining components seen during issuing) are indistinguishable from random. This intuitively means that what the adversary sees during issuing looks unrelated to the derived blind signature.

We start with the basic idea to prove blindness. Given an instance of the decision problem just described \((\mathsf{BG},R,S=sP,U=uP,X=uR, Q=uvP, Y=rQ,\hat{U}=u\hat{P},\hat{V}=v\hat{P},T,W,Z)\), where either (a) \(T=sR,\) \(W=sQ\) and \(Z=sY\) or (b) T, W and Z are random, in the blindness game the challenger could compute the message sent to the signer during issuing as

$$\begin{aligned} M \leftarrow (m\cdot S + Z,T,W,S), \end{aligned}$$
(3)

which is correctly distributed in case (a) but independent of m (and the resulting blind signature) in case (b). In the blindness game, the challenger next receives an SPS-EQ signature on M, which it needs to adapt to the unblinded message in order to construct a blind signature.

Overall, we distinguish two behaviors of blindness adversaries. Type I does not return correct SPS-EQ signatures during issuing. As in this case the adversary does not obtain blind signatures at the end, the above simulation already works and we are done.

However, if the adversary returns valid signatures (Type II) then the simulator, after embedding the instance when creating M as in (3), does not know the blinding factor s, meaning the simulator cannot adapt the SPS-EQ signature to the unblinded message. By perfect adaptation however, the distribution of an adapted signature is the same as that of a fresh signature on the unblinded message. In the honest-key model, where the simulator knows the signing key, it could therefore compute a signature \(\sigma \) on \((m\cdot P + Z,R,Q,P)\) and return the blind signature \((\sigma ,Y,Q,R,U,X,\hat{U},\hat{V})\). Blindness follows, since during issuing the signer obtained a random quadruple; thus the game is independent of bit b.

For blindness in the malicious-key model, we do not have access to the adversarially generated signing key, meaning we cannot recompute the signature on the unblinded message. Instead, we use the adversary \(\mathcal {A}\) as a signing oracle by rewinding it. (This is similar to Coron’s [20] meta-reduction strategy, which was extended to randomizable signatures by Hofheinz et al. [34].) The idea is to first run the adversary to obtain a signature on \((s'(mP+Y),s'R,s'Q,s'P)\) for a known \(s'\), which we can therefore transform into a signature on \((mP+Y,R,Q,P)\). We then rewind the adversary to the point after it output the public key and the messages, and then run it again (using a new random bit b), this time setting M as in (3), thus not knowing s. In the second run we are not able to transform the signature, but we can use the signature from the first run, which is distributed identically, thanks to the property of the SPS-EQ scheme.

Making this approach actually work turns out quite tricky. In the proof in [26] it is argued that an adversary must always output two valid signatures, as otherwise the bit b is perfectly hidden due to the perfectly hiding commitments. For such adversaries if the original blindness game is won with some probability then the game that rewinds the adversary will yield valid signatures in the first run and in the second run the adversary wins with the same probability as in the original (non-rewinding) game.

This is not true anymore for our scheme, as an aborting adversary (one that returns invalid SPS-EQ signatures) can still win the game. In particular, we show in the full version that rewinding once is not enough by giving an example of an adversary’s coin distribution (before and after the point of rewinding) that leads to the original blindness game being won with non-negligible probability, while the game with rewinding (which outputs a random bit if it receives invalid signatures in the first run) is won with probability less than one half.

However, if we rewind more than once then it suffices to obtain valid signatures in at least one of the rewinds. We therefore consider a game where we rewind the adversary \(\lambda \) times and abort if all runs yield invalid signatures (outputting a random bit); otherwise, we run the adversary a final time and check if it wins or not.

In the full version we show the following: suppose the adversary wins the blindness game with non-negligible advantage, that is, for some polynomial p and infinitely many security-parameter values \(\kappa \), the probability of winning the blindness game is greater than \(\frac{1}{2}+\frac{1}{p(\kappa )}\). Then if we rewind the adversary \(\lambda =\kappa \cdot p(\kappa )\) times, the probability that at least one of the \(\lambda \) runs yields valid SPS-EQ signatures and the adversary wins the final run is greater than \(\frac{1}{2}+\frac{1}{2\cdot p(\kappa )}\) for infinitely many \(\kappa \)’s. We make this formal in the following theorem.

Theorem 2

If the underlying SPS-EQ scheme has perfect adaptation of signatures under malicious keys and ABDDH\(^+\) holds for \(\mathsf BGGen\) then the scheme in Fig. 2 satisfies blindness in the malicious-key model.

Efficiency of the Construction. When instantiating our blind signature construction with the SPS-EQ scheme from [25], we obtain a public key size of \(4\,\mathbb {G}_2\), a communication complexity of \(6\,\mathbb {G}_1+1\,\mathbb {G}_2\) and a signature size of \(7\,\mathbb {G}_1+3\,\mathbb {G}_2\) elements. We will now contrast this to the FHS construction [26] and to the DLIN construction from [27].

Instantiating the FHS construction with the SPS-EQ scheme from [25] yields a blind signature scheme having a public key size of \(1\,\mathbb {G}_1+3\,\mathbb {G}_2\), a communication complexity of \(4\,\mathbb {G}_1+1\,\mathbb {G}_2\) and a signature size of \(4\,\mathbb {G}_1+1\,\mathbb {G}_2\) elements. While being more efficient, we recall that blindness of the FHS construction is based on an interactive and, thus, much stronger assumption.

Ignoring the increase of the security parameter due to complexity leveraging for the construction from [27], it has a public key size of \(43\,\mathbb {G}_1\) elements, a communication complexity of \(18\log _2 q\, +\,41\,\mathbb {G}_1\) elements (where, for instance, we have \(\log _2 q=155\) when assuming that the adversary runs in at most \(2^{80}\) steps) and a signature size of \(183\,\mathbb {G}_1\) elements.

Extension to Partially Blind Signatures. We note that analogously to the extension of the round-optimal blind signature construction in [26], it is possible to derive a partially blind signature scheme from the scheme in Fig. 2. To include a common information \(\gamma \in {\mathbb {Z}_p}^{*}\), the underlying SPS-EQ scheme is set up for \(\ell = 5\) (instead of \(\ell = 4 \)) and the additional vector component is being used to include \(\gamma \). In contrast to the blind signature scheme in Fig. 2, the signer on receiving \(M\leftarrow (s(mP+ruvP),srP,suvP,sP)\) computes an SPS-EQ signature for vector \((s(mP+ruvP),srP,suvP,\gamma (sP),sP)\). In the verification of the partially blind signature, the SPS-EQ signature is verified on \((mP+Y,R,Q,\gamma P,P)\).