Traditional single-user security models do not necessarily capture the power of real-world attackers. A scheme that is secure in the single-user setting may not be as secure in the multi-user setting. Inspired by the recent analysis of Schnorr signatures in the multi-user setting, we analyse Boneh-Lynn-Shacham (BLS) signatures and Boneh-Gentry-Lynn-Shacham (BGLS) aggregate signatures in the multi-user setting. We obtain a tight reduction from the security of key-prefixed BLS in the multi-user model to normal BLS in the single-user model. We introduce a multi-user security model for general aggregate signature schemes, in contrast to the original “chosen-key” security model of BGLS that is analogous to the single-user setting of a signature scheme. We obtain a tight reduction from the security of multi-user key-prefixed BGLS to the security of multi-user key-prefixed BLS. Finally, we apply a technique of Katz and Wang to present a tight security reduction from a variant of multi-user key-prefixed BGLS to the computational co-Diffie-Hellman (co-CDH) problem. All of our results for BLS and BGLS use type III pairings.
Hinweise
This article is part of the Topical Collection on Recent Trends in Cryptography
1 Introduction
It is important to have security models that reflect real-world conditions. Proving that a scheme is secure against a particular type of adversary is less valuable when it does not correspond to the adversary of such a system deployed in the real world. While single-user settings are much easier to analyse, they do not capture many real-world attacks. For example, computing the greatest common divisors of RSA moduli from different public keys makes it possible to recover their corresponding private keys if these moduli share a prime factor [12]. A generic MAC scheme’s security in the multi-user setting is not equivalent to its security in the single-user setting—a MAC forger in the multi-user setting has an advantage over a MAC forger in the single-user setting by a factor of the number of users, n [9].
Although digital signatures have existed for over 30 years, there is still debate about the most appropriate security models and how to interpret security reductions when choosing security parameters. As recently as late 2015, the security of Schnorr signatures in the multi-user setting relative to their security in the single-user setting was not well understood [4, 5, 15]. This discussion about the security of Schnorr signatures inspired our analysis of two more signature schemes.
Anzeige
1.1 Overview and our contributions
In this paper, we analyse the multi-user security of two related signature schemes: the Boneh-Lynn-Shacham (BLS) signature scheme [7] and the Boneh-Gentry-Lynn-Shacham (BGLS) aggregate signature scheme [6]. In Sections 1.2–1.4, we review Schnorr and BLS signatures, unforgeability, and single-user vs. multi-user settings. In Section 1.5, we summarize the history of multi-user Schnorr signature security and related work.
Next, in Section 2, we present a reduction from multi-user BLS security to single-user BLS security. It is not tight; the gap is about min{n, qs + 1}. We go on to show in Theorem 1 that with key-prefixing, the security of multi-user BLS does tightly reduce to the security of single-user BLS. Although we were unable to obtain a tight reduction from the security of multi-user BLS to single-user BLS without key-prefixing—which does not eliminate the possibility that multi-user forgery is easier—it is in fact known that, in the random oracle model, multi-user BLS has the same tightness loss as single-user BLS when it is reduced directly to the co-CDH problem [14]. We explain this in more detail at the end of Section 2.
In Section 3, we consider BGLS, a natural extension of BLS and the first proposed aggregate signature scheme. We introduce a truly multi-user security model for general aggregate signature schemes, as opposed to the chosen-key model of BGLS, in Section 3.1. In Theorem 2, we present a tight reduction from key-prefixed multi-user BGLS security to key-prefixed multi-user BLS security in the random-oracle model. Finally, in Theorem 3, we present a tight security reduction for the key-prefixed BGLS scheme in the multi-user setting, also in the random oracle model, by further modifying BGLS to use a technique of Katz and Wang [13].
Figure 1 summarizes our results and shows where they fit in relation to known results. The tightness of reductions is indicated with “tight” or with the tightness gap. “KP” indicates the variant where keys are prefixed to messages before signing, and “KW” indicates the Katz-Wang variants, where a random bit is prefixed to a message before signing. Reductions are in the standard model unless otherwise indicated with “RO” for “random oracle.”
Fig. 1
Overview of our results for BLS and BGLS and how they compare to reductions in the single-user setting
×
Anzeige
1.2 Review of Schnorr and BLS signatures, notation
See Table 1 for an overview of the Schnorr [19] and BLS [7] signature schemes. For simplicity, we omit the role of the security parameter in Setup. Schnorr signatures are mentioned in this paper for illustrative purposes; although we contribute no results about Schnorr signatures, the history of their security models inspired this work.
Although the BLS scheme was introduced for symmetric pairings, where G1 = G2, we use the modified scheme due to Chatterjee et al. [8] that also works for asymmetric pairings where no efficiently computable isomorphism from G2 to G1 is known (“type III” pairings).
The security of the BLS signature scheme with type III pairings depends on the hardness of the computational co-Diffie-Hellman (co-CDH) problem in G1 × G2: given (g1x, g2x) ∈ G1 × G2 and h ∈ G1, compute hx ∈ G1. We say that a problem is (t,𝜖)-hard if there exists no adversary that can solve it in time at most t with probability at least 𝜖, where the probability is taken over all possible instances of the problem and any coin flips the adversary makes.
Note that BLS public keys contain both g1x and g2x, but only the latter is used for verification. Without g1x, it is unknown [8] whether there is a reduction from BLS forgery to solving the co-CDH problem (the opposite direction of that which we examine in this paper). If a forger receives a public key (g1x, g2x), it is straightforward to see that, given a co-CDH solver, it can forge a signature on any message without even making a single signing query.
We let tm and te represent the times required to compute a multiplication or exponentiation in G1 or G2. We write [n] for the set of integers {1,…,n}. We write x←$S to denote picking a value of x uniformly at random from the set S. We let x||y denote the concatenation of (the binary representations of) x and y. A multi-set is a set that may contain repetitions.
1.3 Standard and strong unforgeability
The widely-accepted notion of security for a digital signature scheme is resistance to existential forgery under adaptive chosen-message attacks, formalized by Goldwasser, Micali, and Rivest in 1988 [11]. A digital signature scheme is (single-user) (t, 𝜖, qs)-existentially unforgeable under adaptive chosen-message attacks (EUF-CMA) if there exists no forger \({\mathcal {F}}\) that, given one challenge public key generated by KeyGen and adaptively making at most qs queries to a signing oracle, runs in time at most t and can produce with probability at least 𝜖 a signature on a message it did not submit to the signing oracle. See Fig. 2a for a diagram representing the EUF-CMA experiment.
Fig. 2
Four types of existential forgery experiments in the standard model. The public keys are generated with KeyGen. Similar experiments exist in the random oracle model, where the forgers can also make at most qh queries to a hashing oracle
×
For probabilistic signature schemes, there exists a variant of existential unforgeability: “strong unforgeability,” introduced by An, Dodis, and Rabin in 2002 [1]. A digital signature scheme is (single-user) strongly(t, 𝜖, qs)-existentially unforgeable under adaptive chosen-message attacks (SEUF-CMA) if there is no forger \({\mathcal {F}}\), with the same properties as above, that can produce a new signature on any message, including the messages it submitted to the signing oracle. (See Fig. 2b.)
Although the notions of standard and strong unforgeability are identical for BLS, the difference is important in understanding the history of the security models of Schnorr signatures.
1.4 Single-user and multi-user settings
In the standard and strong unforgeability models, the adversary receives one target public key for which it must forge a signature. However, since public keys are public, a real-world adversary has the choice of which public key to target. Perhaps it is easier to forge a signature for any public key from a set rather than one specific public key. That is, perhaps forgery in the multi-user setting, where the adversary chooses which public key to target, is easier than forgery in the single-user setting. We will compare these two settings.
The study of signature schemes in the multi-user setting was initiated by Menezes and Smart in 2001 [18]. A digital signature scheme is (multi-user) (t ,𝜖, n, qs)-existentially unforgeable under adaptive chosen-message attacks (MU-EUF-CMA) if there exists no forger \({\mathcal {F}}\) that, given n challenge public keys generated by KeyGen and adaptively making at most qs queries to a signing oracle, runs in time at most t and with probability at least 𝜖, can produce a signature for one of the n users on a message that it did not submit to the signing oracle for this user. (See Fig. 2c.) For probabilistic signature schemes, there is again a strong unforgeability variant of multi-user security. A digital signature scheme is (multi-user) strongly(t, 𝜖, n, qs)-existentially unforgeable under adaptive chosen-message attacks (MU-SEUF-CMA) if there is no forger \({\mathcal {F}}\), with the same properties as above, that can produce a new signature on any message by any of the users, including messages submitted to the signing oracle for this user. (See Fig. 2d.)
1.5 A brief history of multi-user schnorr signature security and related work
In this section, we review the security of Schnorr signatures in the multi-user model. We will employ similar techniques to develop a reduction for BLS signatures in the multi-user setting.
In 2002, Galbraith, Malone-Lee, and Smart claimed that single-user unforgeability (EUF-CMA) tightly implies multi-user unforgeability (MU-EUF-CMA) for any Schnorr-like signature scheme [10]. However, the GMLS reduction, which explains how to construct a single-user forger given a multi-user forger, contains an error, pointed out by Bernstein in October 2015 [5]. The error arises from the single-user forger \({\mathcal {F}}_{1}\) using its challenge public key y to create each of the public keys it gives the multi-user forger \({\mathcal {F}}_{n}\). To answer each of \({\mathcal {F}}_{n}\)’s signature queries, \({\mathcal {F}}_{1}\) must always query its own signing oracle for y with the same message. The analysis of \({\mathcal {F}}_{1}\)’s success probability overlooks the possibility that \({\mathcal {F}}_{n}\)’s forgery is for a message with which it previously queried the signing oracle (for any of the users). In addition to pointing out the error, Bernstein proved that single-user security for Schnorr signatures (EUF-CMA) tightly implies multi-user security for key-prefixed Schnorr signatures (MU-EUF-CMA) in the standard model. He also argued that such a reduction for Schnorr signatures without key-prefixing is unlikely to exist.
In November 2015, Kiltz, Masny, and Pan gave a reduction showing that strong single-user security (SEUF-CMA) tightly implies strong multi-user security (MU- SEUF-CMA) for Schnorr signatures in the random oracle model [15]. In response, Bernstein pointed out that the assumption of strong unforgeability is less well-understood: “Having to assume ‘strong’ unforgeability isn’t as good as assuming standard unforgeability—there could be huge differences in security between these two attack targets” [4]. This work by Bernstein, Kiltz, Masny, and Pan was in the context of IETF standardization of elliptic-curve based signature schemes. Their results played a role in the Crypto Forum Research Group (CFRG)’s selection of a proposal [4], illustrating the importance of appropriate security models and highlighting the difficulty of interpreting security reductions when implementing schemes.
Kiltz, Masny, and Pan later generalized their work to reduce the security of signature schemes obtained from identification schemes via the Fiat-Shamir transform in the multi-user setting to the security of their underlying identification schemes [16]. The tightness of this security reduction is independent of the number of users and does not require key-prefixing. Other recent work proved that a tightness loss in the number of users is unavoidable for some signature schemes when reducing security in the multi-user setting to the single-user setting [2]. This result applies to adversaries who can corrupt (i.e., learn the private key of) all but one of the users.
2 BLS signatures
The security reduction for BLS signatures in the single-user setting loses tightness by a factor of qs, the number of signature queries a forger can make. We restate the result here, and note that the tightness loss of qs is optimal in the sense that there exists no tighter reduction [17].
If solving the co-CDH problem inG1 × G2 is (t′, 𝜖′)-hard, then the BLS signature scheme is (t, 𝜖, qh, qs)-secure against (single-user) existential forgery under adaptive chosen-message attacks, for
For the multi-user security of any signature scheme, it is known that there exists a non-tight reduction to single-user security, where the tightness loss is the number of users [10]. A natural question is whether a tighter reduction exists for BLS. Although we were not able to find a tight reduction in the standard model without key-prefixing, our reduction—illustrated in Fig. 3—loses tightness by a factor of about min{n, qs + 1}. We omit the details of this non-tight reduction and instead supplement Fig. 3 with some intuition and an overview of the proof.
Fig. 3
Reduction from multi-user security to single-user security for BLS
×
The single-user forger \({\mathcal {F}}_{1}\) embeds its challenge public key into a fraction α of the n public keys it provides to the multi-user forger \({\mathcal {F}}_{n}\). When \({\mathcal {F}}_{n}\) queries the signing oracle for a signature by a user whose public key does not depend on \({\mathcal {F}}_{1}\)’s challenge public key, \({\mathcal {F}}_{1}\) can simply compute the signature. Otherwise, it answers \({\mathcal {F}}_{n}\)’s signature query by forwarding it to its own signing oracle and multiplying the result by the appropriate power of the message’s hash.
Although \({\mathcal {F}}_{1}\) can always answer \({\mathcal {F}}_{n}\)’s signature queries, the reduction can fail even if \({\mathcal {F}}_{n}\) successfully forges a signature. For \({\mathcal {F}}_{1}\) to succeed as well, two more conditions must be met: user i∗ must have a pk-dependent key, and \({\mathcal {F}}_{n}\) must not have requested a signature on m∗ by any user with a pk-dependent key. Given that \({\mathcal {F}}_{n}\) succeeded, the first condition is met with probability at least α. Given \({\mathcal {F}}_{n}\)’s success and the first condition being met, the second condition is met with probability at least \((1 - \alpha )^{\min \{n-1, q_{s}\}}\), since the number of signatures \({\mathcal {F}}_{n}\) can request on m∗ is limited by the number of users and the total number of signatures it can request. Therefore, given \({\mathcal {F}}_{n}\)’s success, \({\mathcal {F}}_{1}\) succeeds with probability at least \(\alpha \cdot (1 - \alpha )^{\min \{n-1, q_{s}\}}\), which is maximized for α = 1/min{n, qs + 1} and corresponds to a tightness gap of about e ⋅ min{n, qs + 1}.
This non-tight reduction leaves open the question of whether there is an attack on multi-user BLS that is much faster than on single-user BLS. Recall that for Schnorr signatures, there were two approaches to making a multi-user to single-user security reduction tight: strong unforgeability and prefixing keys to messages. Since BLS signatures are not probabilistic, we try the second approach: we establish a reduction from multi-user key-prefixed BLS security to single-user BLS security. Let BLS-KP refer to the key-prefixed variant of BLS, whose details are in Table 2. We obtain a result for BLS analogous to Bernstein’s for Schnorr signatures. See Fig. 4 for an illustration of this tight reduction and Theorem 1 for its details.
Reduction from multi-user BLS-KP security to single-user BLS security
×
Theorem 1 (Reduction from multi-user BLS-KP security to single-user BLS security)
If the BLS signature scheme is resistant to (t′, 𝜖, qs)-existentialforgery under adaptive chosen-message attacks in thesingle-user setting (EUF-CMA), then BLS-KP is resistant to (t, 𝜖, n, qs)-existentialforgery under adaptive chosen-message attacks inthe multi-user setting (MU-EUF-CMA), for anyt, n, andqssatisfying
We proceed in the usual manner, by proving the contrapositive: given a multi-user (t, 𝜖, n, qs)-forger \({\mathcal {F}}_{n}\) for BLS-KP, we build a single-user (t′, 𝜖, qs)-forger \({\mathcal {F}}_{1}\) for BLS. \({\mathcal {F}}_{1}\) receives a challenge public key pk = (y1, y2) and has access to a signing oracle Σ1 for pk. \(\mathcal {F}_{1}\) gives \({\mathcal {F}}_{n}\) the following n public keys:
where \(r_{i} \leftarrow _{\$} \mathbb {Z}_{p}\). \({\mathcal {F}}_{1}\) records (i, ri) for each of the n public keys. \({\mathcal {F}}_{1}\) must simulate responses from a signing oracle for \({\mathcal {F}}_{n}\), which can make qs signature queries. To answer the query (m, i) for a signature on m by the user with key pki, \({\mathcal {F}}_{1}\) requests a signature on the message pki||m from Σ1 and then computes \(\mathsf {Sign}^{\prime }_{i}(m) = \mathsf {Sign}(\mathsf {pk}_{i}\vert \vert m)\cdot \mathsf {H}(\mathsf {pk}_{i}\vert \vert m)^{r_{i}}\). This signature is valid:
$$\begin{array}{@{}rcl@{}} e(\mathsf{Sign}(\mathsf{pk}_{i}\vert\vert m)\cdot \mathsf{H}(\mathsf{pk}_{i}\vert\vert m)^{r_{i}}, g_{2}) &=& e(\mathsf{Sign}(\mathsf{pk}_{i}\vert\vert m), g_{2}) \cdot e(\mathsf{H}(\mathsf{pk}_{i}\vert\vert m), {g_{2}}^{r_{i}}) \\ &=& e(\mathsf{H}(\mathsf{pk}_{i}\vert\vert m),{y_{2}}) \cdot e(\mathsf{H}(\mathsf{pk}_{i}\vert\vert m), {g_{2}}^{r_{i}}) \\ &=& e(\mathsf{H}(\mathsf{pk}_{i}\vert\vert m), {{y_{2,i}}}). \end{array} $$
After time at most t and with probability at least 𝜖, \({\mathcal {F}}_{n}\) outputs a forgery (σ, m∗, i∗) that is new and valid: (m∗, i∗) was not queried to Σn and \(\mathsf {Ver}(\mathsf {pk}_{i^{*}},\sigma ,\allowbreak m^{*})=1\), specifically, \(e(\sigma ,g_{2}) = e(\mathsf {H}(\mathsf {pk}_{i^{*}}\vert \vert m^{*}), {{y_{2,i^{*}}}})\). Then, \(\mathcal {F}_{1}\) computes \(\sigma ^{\prime } = \sigma \cdot {\mathsf {H}({\mathsf {pk}_{i^{*}}\vert \vert m}^{*})}^{-r_{i^{*}}}\) and outputs the forgery \((\sigma ^{\prime },\mathsf {pk}_{i^{*}}\vert \vert m^{*})\). This signature is a valid forgery on \(\mathsf {pk}_{i^{*}}\vert \vert m^{*}\) by the user with public key pk since
There is a one-to-one correspondence between the signing queries of \({\mathcal {F}}_{1}\) and \({\mathcal {F}}_{n}\), so \({\mathcal {F}}_{1}\) made exactly qs signing queries and never queried Σ1 with \(\mathsf {pk}_{i^{*}}\vert \vert {m}^{*}\) since \({\mathcal {F}}_{n}\) never queried \({\Sigma }^{\prime }_{n}\) with (m∗, i∗). \({\mathcal {F}}_{1}\)’s success probability is exactly \({\mathcal {F}}_{n}\)’s success probability 𝜖. Finally, \({\mathcal {F}}_{1}\)’s only additional work was computing 2n + qs + 1 multiplications and 2n + qs + 1 exponentiations in G1 or G2, so t′ = t + (2n + qs + 1)(tm + te), giving the required bounds. □
By composing the BLS security reduction and Theorem 1, we can obtain a security reduction for BLS in the multi-user setting with key-prefixing. One might be tempted to conclude that key-prefixing is necessary to preserve BLS security in a multi-user setting, but it is not. In fact, the security of BLS in the multi-user setting can be directly reduced to the hardness of the co-CDH problem, with the same tightness loss as BLS in the single-user setting [14]. To see this, first consider the single-user BLS security reduction. The co-CDH solver embeds one part of the co-CDH instance in the public key it gives to the forger, and the other part in a particular fraction of the message hashes. It succeeds if it was able to answer all of the forger’s signature queries, if the forger succeeded, and if the message on which the forger forged a signature was one of the special fraction of messages. In the multi-user BLS security reduction, the co-CDH solver can simply embed the first part of the co-CDH instance in all of the public keys it provides the BLS forger. The rest of the reduction (and thus, the analysis) is the same.
Now that we have a tight reduction relating the security of multi-user BLS (with key-prefixing) and single-user BLS, we turn our attention to the BGLS aggregate signature scheme.
3 Aggregate signatures
Aggregate signature schemes combine multiple users’ signatures on multiple (possibly different) messages. Their current chosen-key security model does not reflect the possibility that an adversary may consider it sufficient to forge a signature involving any one user, rather than a given user.
Boneh, Gentry, Lynn, and Shacham introduced aggregate signatures in 2003 [6]. These schemes allow compressing many signatures into one signature of shorter length, sometimes even independent of the number of included signatures. A general aggregate signature scheme comprises five algorithms (Setup, KeyGen, Sign, Agg, AggVer) on four sets (public keys, secret keys, messages, and signatures). Setup, KeyGen, and Sign work exactly as they do in a normal signature scheme, except that KeyGen is run once for each user. Agg takes two or more signatures and outputs one (aggregate) signature. AggVer takes a signature, a multi-set of k ≤ nmax public key-message pairs, and outputs 1 if the signature is a valid aggregate. While sequential aggregate signature schemes exist, we consider only general aggregate signature schemes where aggregation can be performed by anyone in any order. In the following experiments, we always assume without loss of generality that the messages in each aggregate signature are numbered so that the first one corresponds to the non-trivial component of that signature, as we describe below.
3.1 General aggregate signature security model
The original security model is the “aggregate chosen-key security model” [6], in which the adversary receives one public key generated with KeyGen and can adaptively query a signing oracle with messages of its choice. Its goal is to output a valid, non-trivial aggregate signature on k ∈ [nmax] messages for which it chose k − 1 of the public keys. “Non-trivial” means that the first message (corresponding to the challenge public key) was not queried to the signing oracle. See Fig. 5a for a diagram of this experiment, the aggregate existential unforgeability under adaptive chosen-message attacks (A-EUF-CMA) experiment. We write pk or pki for public keys generated using KeyGen, and \(\mathsf {pk}^{\prime }_{j}\) for public keys chosen by the adversary. The keys it chooses may or may not be equal to some of the keys it received as input.
Fig. 5
Two types of aggregate existential forgery experiments in the random oracle model. The public keys pk and pk1,…,pkn are generated with KeyGen
×
We believe the chosen-key security model is analogous to the single-user setting for (non-aggregate) digital signatures: the adversary is given one public key to target. We propose a new security model that is truly a multi-user model—the forger receives n challenge public keys generated by KeyGen and it can choose which one or ones to target, eventually forging an aggregate signature on at most nmax messages. A valid, non-trivial aggregate signature in this model must include at least one message signed by a user with one of the challenge public keys, and the forger must not have requested a signature on this message by this user from the signing oracle. The other public keys, if any, may be challenge keys or they may have been generated by the forger. We call this model “multi-user aggregate existential forgery under adaptive chosen-message attacks” (MU-A-EUF-CMA). (See Fig. 5b.)
Chosen-key aggregate forgery is at least as hard as multi-user aggregate forgery: an aggregate forger in the chosen-key model can easily be translated to an aggregate forger in the multi-user model. For the converse, however, we do not know of a tight reduction, only one that loses tightness by a factor of the number of users, n. This straightforward, general result does not require the random oracle model.
Proposition 1 (Reduction from multi-user to chosen-key aggregate signature security)
If an aggregate signature scheme is resistant to aggregate (t, 𝜖, nmax, qs)-existentialforgery under adaptive chosen-message attacks(A-EUF-CMA), then it is resistant to multi-user aggregate (t, 𝜖, n, nmax, qs)-existentialforgery under adaptive chosen-message attacks (MU-A-EUF-CMA) for anyt, 𝜖, n, nmax, andqssatisfying
$$\begin{array}{@{}rcl@{}} t &=& t^{\prime} - q_{s} t_{\mathsf{Sign}} - (n-1) t_{\mathsf{KeyGen}}, \text{ and} \\ \epsilon &=& \epsilon^{\prime} n \end{array} $$
wheretSignandtKeyGenare the timesrequired to runSignandKeyGen.
This result applies to any general aggregate signature scheme, and could be composed with a security reduction in the A-EUF-CMA model to obtain a security reduction in the MU-A-EUF-CMA model. For BGLS, however, it is possible to obtain a tighter security reduction by first reducing security to the underlying signature scheme, BLS, in the multi-user model.
Our reductions involving BGLS aggregate forgers are in the random oracle model. We make the following simplifying assumptions:
When a forger requests a signature on a message from a signing oracle, it has already obtained the hash of this message from the hashing oracle.
A forger never makes the same query twice.
When a forger outputs a signature on a message (or messages), every message was previously hashed.
3.2 BGLS and key-prefixing
Recall that we used key-prefixing to obtain a tight reduction from multi-user BLS-KP security to single-user BLS security, as did Bernstein for Schnorr signatures [5]. Key-prefixing is also relevant to BGLS signatures, but for a different reason: to prevent a rogue-key attack. In such an attack, a malicious user claims its public key is some function of an honest user’s public key, but without actually knowing the associated secret key. Table 3 summarizes the basic BGLS scheme, which must be modified or restricted to prevent a rogue-key attack.
The rogue key attack, identified in the original BGLS paper [6], works as follows. Suppose honest user 1 has public key pk1 = (y1,1, y2,1). Malicious user 2 can pick any integer \(x \in \mathbb {Z}_{p}\) and publish pk2 = (g1x ⋅y1,1−1, g2x ⋅y2,1−1) as its public key. Then, user 2 can compute σA = H(m)x for any message m and claim that it is an aggregate signature on m comprising signatures by both itself and honest user 1. This signature is valid since
This attack applies to the basic BGLS scheme as defined in Table 3 in both the original A-EUF-CMA model and our new MU-A-EUF-CMA model. Boneh, Gentry, Lynn, and Shacham suggested applying one of the following three countermeasures:
Require users to prove knowledge of their private keys (e.g., by disclosing their private keys to a trusted party).
Require users to prove possession of their private keys (e.g., by signing random messages that will never be used in practice).
Require all of the messages in one aggregate signature to be distinct.
The authors suggested that the last option might be the simplest, and further suggested that to achieve distinctness of messages, a user could simply prefix its public key to a message, creating an “enhanced” or “key-prefixed” message, before hashing it. Then, the distinctness requirement would apply only to each user’s messages in the aggregate, rather than all messages in the aggregate.
In their 2007 paper, Bellare, Namprempre, and Neven pointed out that while hashing enhanced messages eliminates the rogue-key attack, the requirement for distinct enhanced messages is restrictive and unnecessary [3]. There may be applications where multiple signatures by the same user on the same message need to be aggregated. They suggested that an “unrestricted” scheme—with no requirement for enhanced messages to be distinct—is more practical and is sufficient for preventing the rogue-key attack. See Table 4 for this unrestricted, key-prefixed variant “BGLS-KP.”
Bellare, Namprempre, and Neven presented a tight reduction from the unforgeability of BGLS-KP to the unforgeability of BLS in the random oracle model [3]. Composing this reduction with the standard BLS security reduction yields a security reduction for BGLS-KP that loses tightness by a factor of qs. Then, using a technique of Katz and Wang [13], they presented a tight security reduction for a variant of BGLS with key-prefixing, “BGLS-KP-KW,” where each signer further enhances a message before hashing and signing it by also prefixing a random bit of its choice (Table 5).
In the next section, we determine whether similar results hold for BGLS in our multi-user security model. First, we examine whether there is also a tight reduction from BGLS-KP security in the multi-user model to BLS-KP security in the multi-user model. Next, we determine whether the Katz-Wang trick is enough to yield a tight security reduction for BGLS-KP-KW in the multi-user model.
3.3 BGLS security in a truly multi-user setting
In the standard model, it is not obvious how to reduce the security of multi-user BGLS-KP to the security of multi-user BLS-KP: a BLS forger would need to isolate one component of the BGLS forger’s aggregate signature, which requires being able to compute signatures on messages by users whose keys are chosen by the BGLS-KP forger. In the random oracle model, however, it is possible to obtain a tight reduction from BGLS-KP to BLS-KP security in the multi-user setting, as the next theorem proves. See Fig. 6 for an illustration of the reduction.
Fig. 6
Reduction from multi-user BGLS-KP security to multi-user BLS-KP security
×
Theorem 2 (Reduction from multi-user BGLS-KP security to multi-user BLS-KP security)
If the BLS-KP signature scheme is resistant to multi-user\((t^{\prime },\epsilon ,n,q_{h},q_{s}^{\prime })\)-existentialforgery under adaptive chosen-message attacks (MU-EUF-CMA), thenthe BGLS-KP aggregate signature scheme is resistant to multi-user (t, 𝜖, n, nmax, qh, qs)-existentialaggregate forgery under adaptive chosen-message attacks (MU-A-EUF-CMA),for anyt, 𝜖, n, nmax, qh, andqssatisfying
We proceed by proving the contrapositive: given a multi-user BGLS-KP (t, 𝜖, n, nmax, qh, qs)-aggregate forger \({\mathcal {F}}_{A}\), we build a multi-user \((t^{\prime },\epsilon ,n,q_{h},q_{s}^{\prime })\)-forger \({\mathcal {F}}\) for BLS-KP. \({\mathcal {F}}\) receives n challenge public keys (pk1,…,pkn) and can query a hashing oracle H and a signing oracle Σn. \({\mathcal {F}}\) gives \({\mathcal {F}}_{A}\) the same n public keys and must simulate a hashing oracle H′ and signing oracle \({\Sigma }_{n}^{\prime }\). When \({\mathcal {F}}_{A}\) makes a hash query, the reply depends on the message’s format:
$$\mathsf{H}^{\prime}(m) = \left\{\begin{array}{ll} \mathsf{H}(m^{\prime}) & \text{ if } m=\mathsf{pk} \vert\vert m^{\prime} \text{ for some } \mathsf{pk}\in \{\mathsf{pk}_{1},\ldots,\mathsf{pk}_{n}\} \\ {g_{1}}^{r}, r \leftarrow_{\$} \mathbb{Z}_{p} & \text{else.} \end{array}\right. $$
In the first case, \({\mathcal {F}}\) must query H. In the second case, \({\mathcal {F}}\) records (m, r). When \({\mathcal {F}}_{A}\) queries \({\Sigma }_{n}^{\prime }\) with (m, i), \({\mathcal {F}}\) in turn queries Σn with (m, i) and replies to \({\mathcal {F}}_{A}\) with \(\mathsf {Sign}^{\prime }_{i}(m) = \mathsf {Sign}_{i}(m)\).
After time at most t and with probability at least 𝜖, \({\mathcal {F}}_{A}\) outputs a valid aggregate forgery \((\sigma _{A}^{*},m_{1}^{*},\ldots ,m_{k}^{*},\)\(i^{*},\mathsf {pk}^{\prime }_{2},\ldots ,\mathsf {pk}^{\prime }_{k})\) for some k ∈ [nmax], where \((m_{1}^{*},i^{*})\) was not queried to \({\Sigma }^{\prime }_{n}\). For simplicity, let \(\mathsf {pk}^{\prime }_{1} = \mathsf {pk}_{i^{*}}\). Partition the indices [k] into the following three sets of “duplicates,” “new keys,” and “given keys”:
The set ID contains at least one element, 1. For each i in INK, \({\mathcal {F}}\) looks up the logarithm of \(\mathsf {H}^{\prime }(\mathsf {pk}^{\prime }_{i} \vert \vert m^{*}_{i})\) to base g1, i.e., the value of \(r_{nk_{i}}\) such that \(\mathsf {H}^{\prime }(\mathsf {pk}^{\prime }_{i} \vert \vert m^{*}_{i}) = {g_{1}}^{r_{nk_{i}}}\). For each i in IGK, \({\mathcal {F}}\) queries the signing oracle Σn with \((m^{*}_{i},gk_{i})\) to get \(\mathsf {Sign}_{gk_{i}}(m^{*}_{i})\). Since \({\mathcal {F}}_{A}\) output a valid forgery, \(\sigma _{A}^{*}\) satisfies the following equations:
|ID|−1 mod p exists as long as |ID| < p, which is a reasonable assumption since otherwise \(\mathcal {F}\) could find a secret key by trial exponentiation. \({\mathcal {F}}\) outputs \((\sigma ^{*}, m^{*}_{1}, i^{*})\), which is valid because \(e(\sigma ^{*},g_{2}) = e(\mathsf {H}(\mathsf {pk}_{i^{*}} \vert \vert m_{1}^{*}), y_{{2,i}^{*}}))\).
The additional work done by \({\mathcal {F}}\) was computing at most qh + nmax + 1 exponentiations and nmax − 1 multiplications in G1, so t′≤ t + (qh + nmax + 1)te + (nmax − 1)tm. \({\mathcal {F}}\) made at most as many hashing queries as \({\mathcal {F}}_{A}\), qh, and it made \(q^{\prime }_{s} \leqslant q_{s} + n_{max} -1\) signing queries. It always succeeds whenever \({\mathcal {F}}_{A}\) succeeds, so 𝜖′ = 𝜖. Thus, we have built a multi-user forger for BLS-KP given a multi-user aggregate forger for BGLS-KP with the required time and query bounds. □
The previous reduction is tight. We can compose it with the reduction from multi-user BLS-KP security to single-user BLS security (Theorem 1) and the security reduction for single-user BLS security. The result is a security reduction for BGLS-KP based on the co-CDH problem that has a tightness gap of about qs.
Given that there is a tight security reduction for BGLS in the chosen-key model due to Katz and Wang, it is natural to wonder whether this result can be lifted to the multi-user model. Our last theorem provides an affirmative answer for this variant of BGLS-KP: there is a tight security reduction, illustrated in Fig. 7, for BGLS-KP-KW in the multi-user setting.
Fig. 7
Security reduction for multi-user BGLS-KP-KW
×
Theorem 3 (Security reduction for multi-user BGLS-KP-KW)
If the co-CDH problem is (t′, 𝜖′)-hardinG1 × G2, then the BGLS-KP-KW aggregate signature scheme is resistant to multi-user (t, 𝜖, n, nmax, qh, qs)-existentialaggregate forgery under adaptive chosen-message attacks (MU-A-EUF-CMA),for anyt, 𝜖, n, nmax, qh, andqssatisfying
We show how to build a solver \({\mathcal {S}}\) for the co-CDH problem given an aggregate forger \({\mathcal {F}}_{A}\) for BGLS-KP-KW. \({\mathcal {S}}\) receives an instance of the co-CDH problem, a triple \((h,{g_{1}}^{x^{*}},{g_{2}}^{x^{*}}) \in G_{1}\times G_{1} \times G_{2}\), for some unknown integer \(x^{*} \in \mathbb {Z}_{p}\). It must compute \(h^{x^{*}} \in G_{1}\). First, \({\mathcal {S}}\) gives \({\mathcal {F}}_{A}\) n public keys of the form \(\mathsf {pk}_{i} = ({g_{1}}^{x^{*}}\cdot {g_{1}}^{r_{i}}, {g_{2}}^{x^{*}}\cdot {g_{2}}^{r_{i}})\), where \(r_{i} \leftarrow _{\$} \mathbb {Z}_{p}\). For each of these i, \({\mathcal {S}}\) records (i, ri). When \({\mathcal {F}}_{A}\) requests the hash of a message m, \({\mathcal {S}}\)’s reply depends on the message’s format:
$$\mathsf{H}(m) = \left\{\begin{array}{ll} h^{b \bigoplus b_{m^{\prime},i}}\cdot {g_{1}}^{s} & \text{ if } m=b\vert\vert \mathsf{pk} \vert\vert m^{\prime} \text{ where } b\in\{0,1\}, \mathsf{pk}=\mathsf{pk}_{i} \text{ for an } i\in [n] \\ {g_{1}}^{s} & \text{else} \end{array}\right. $$
for some \(s\leftarrow _{\$} \mathbb {Z}_{p}\), where \(b_{m^{\prime },i} \leftarrow _{\$}\{0,1\}\). In the first case, \({\mathcal {S}}\) stores \((m^{\prime },i,b_{m^{\prime },i})\) and (m′, i, b, s); in the second case, \({\mathcal {S}}\) stores (m, s).
When \({\mathcal {F}}_{A}\) queries the signing oracle Σn with (m, i), \({\mathcal {S}}\) always chooses to sign with b = bm, i. It looks up the value of s corresponding to (m, i, b) and returns \(\mathsf {Sign}_{i}(m) = (b,({g_{1}}^{x^{*}}\cdot {g_{1}}^{r_{i}})^{s})\), which is a valid signature since \(({g_{1}}^{x^{*}}\cdot {g_{1}}^{r_{i}})^{s} = ({g_{1}}^{s})^{x^{*} + r_{i}} = \mathsf {H}(b\vert \vert \mathsf {pk}_{i} \vert \vert n)^{x^{*} + r_{i}}\).
After time at most t and with probability at least 𝜖, \({\mathcal {F}}_{A}\) outputs a valid aggregate forgery \((\sigma _{A}^{*},m_{1}^{*},\ldots ,m_{k}^{*},\)\(i^{*},\mathsf {pk}^{\prime }_{2},\ldots ,\mathsf {pk}^{\prime }_{k},b^{*}_{1},\ldots ,b^{*}_{k})\) for some k ∈ [nmax], where Σn never answered a query for \((m_{1}^{*},i^{*})\) with \(b=b^{*}_{1}\). For ease of notation, let \(\mathsf {pk}^{\prime }_{1} = \mathsf {pk}_{i^{*}}\). Partition the indices [k] into the following three sets corresponding to “new keys,” “random hashes,” and “h-dependent hashes”:
\(I_{RH} := \{i \in [k] \setminus I_{NK} : \mathsf {pk}^{\prime }_{i} = \mathsf {pk}_{gk_{i}} \text { for some } gk_{i} \in [n]\) and \(b^{*}_{i} = b_{m^{*}_{i},i} \}\)
\(I_{HH} := \{i \in [k] \setminus I_{NK} : \mathsf {pk}^{\prime }_{i} = \mathsf {pk}_{gk_{i}} \text { for some } gk_{i} \in [n]\) and \(b^{*}_{i} \neq b_{m^{*}_{i},i} \}\)
With probability 1/2, \(b^{*}_{1} \neq b_{m^{*}_{1},i^{*}}\) and therefore 1 ∈ IHH. (If not, then \({\mathcal {S}}\) aborts.) For each i ∈ INK ∪ IRH, \({\mathcal {S}}\) can look up the value of si such that \(\mathsf {H}^{\prime }(b^{*}_{i} \vert \vert \mathsf {pk}^{\prime }_{i} \vert \vert m^{*}_{i}) = {g_{1}}^{s_{i}}\). Similarly, for each i ∈ IHH, \({\mathcal {S}}\) can look up the value of si such that \(\mathsf {H}^{\prime }(b^{*}_{i} \vert \vert \mathsf {pk}^{\prime }_{i} \vert \vert m^{*}_{i}) = h {g_{1}}^{s_{i}}\). Since \({\mathcal {F}}_{A}\) output a valid forgery, \(\sigma _{A}^{*}\) satisfies the following equations:
\({\mathcal {S}}\) had to compute 2n + qh + qs + 2nmax + 1 exponentiations and 2n + qh + qs + 2n multiplications in G1 or G2. \({\mathcal {S}}\) succeeds whenever \({\mathcal {F}}_{A}\) does and \(b^{*}_{1} \neq b_{m^{*}_{1},i^{*}}\), so 𝜖′≥ 𝜖/2, as required. □
Although the length of a BGLS-KP-KW aggregate signature increases by 1 bit for each component, Bellare, Namprempre, and Neven argue that the BGLS-KP-KW scheme could be as efficient as BGLS-KP: the tighter reduction means that a smaller prime p can be used for the same level of security [3].
4 Conclusions
Inspired by the recent analysis of Schnorr signatures in the multi-user setting, we examined reductions for BLS and BGLS signatures in the multi-user setting. We obtained a tight reduction from the multi-user security of BLS-KP, a key-prefixed variant of BLS, to BLS in the single-user setting. We introduced a notion of security (MU-A-EUF-CMA) for general aggregate signature schemes in the multi-user setting, which we believe is more realistic than the current standard. The security of any general aggregate signature scheme in this new multi-user setting reduces to its security in the original chosen-key setting with a tightness loss of the number of users. For BGLS, it is possible to do better: we presented a tight reduction from multi-user BGLS-KP security to multi-user BLS-KP security in the random-oracle model. BGLS-KP is not only a natural extension of BLS-KP, which has a tight reduction to single-user BLS, but BGLS-KP also avoids a known rogue-key attack and has no requirement for the distinctness of (enhanced) messages. Composing this reduction with our first result—the tight multi-user BLS-KP to single-user BLS reduction—and with the standard BLS security reduction yields a security reduction for BGLS-KP with a tightness gap of qs. Finally, we presented a tight security reduction for BGLS-KP-KW, the Katz-Wang variant of BGLS with key-prefixing, in the multi-user setting. The tightness gap of this reduction is only 2, but it is in the random oracle model. It would be interesting to perform a similar analysis on the security models for sequential aggregate signature schemes.
Although the importance of developing appropriate security models may be well known, interpreting the tightness of security reductions is still difficult. In this paper, we proved that prefixing a random bit to each enhanced message makes the BGLS-KP security reduction tight in the random oracle model. However, without these single bits, which are sent in the clear with the signature, the security reduction may lose tightness by a factor of up to qs, the number of signature queries an adversary can make—which could be as much as 220. The question of which of these two results should guide the choice of parameter sizes in practice is difficult to answer.
Acknowledgements
This work is supported by the European Union’s Horizon 2020 research and innovation programme under grant agreement No. H2020-MSCA-ITN-2014-643161 ECRYPT-NET. The author thanks Kenny Paterson for his comments on an earlier version of this work, Alfred Menezes for his guidance on related work completed in the Department of Combinatorics and Optimization at the University of Waterloo as part of the MMath programme, and the reviewers for their valuable comments.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
