Chapter status: ✅ in good shape ✅

Related puzzles: Puzzle 1

TODO:

• add details about hashing into groups
• write a more rigorous game-based proof for BLS
• write the security proof for aggregate BLS signatures

BLS Signatures

The BLS signature scheme was proposed by Boneh, Lynn, and Shacham [BLS01] (see also the corresponding journal paper [BLS04] and the IETF draft) and was one of the first applications of pairings to cryptography (shortly after tripartite Diffie-Hellman and identity-based encryption). Note that the BLS initialism can refer to two different things in cryptography: Boneh-Lynn-Shacham signatures discussed in this chapter and Barreto-Lynn-Scott curves, a family of pairing-friendly elliptic curves. It is possible to implement BLS (signatures) on BLS (curves).

Contents

• Description of BLS
• Security of BLS
  • Security Proof
  • Discussion
• Signature Aggregation
• A Note about Non-Repudiation
• Further Topics to Cover

Description of BLS

For the general syntax and the EUF-CMA security definition, refer to the corresponding chapter.

Let $\mathsf{PairingSetup}$ be a pairing group setup algorithm. The BLS signature scheme is defined as follows:

• The $\mathsf{Setup}$ algorithm, on input the security parameter $1^{\lambda },$ runs $$({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)\leftarrow \mathsf{PairingSetup}(1^{\lambda })$$ and draws a random generator $G_2$ of ${\mathbb{G}}_2.$ It also specifies a hash function $H:\{0,1{\}}^{\ast }\to {\mathbb{G}}_1$ mapping bit strings to group elements in ${\mathbb{G}}_1.$ The public parameters consist of the tuple $$par=({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e,G_2,H).$$

• The key generation algorithm $\mathsf{KeyGen}$ draws a random scalar $x{\leftarrow }_{\$}{\mathbb{Z}}_r$ and computes the point $X=x{G}_2$ on curve ${\mathbb{G}}_2;$ the secret key is $x$ and the public key is $X.$

• The signature algorithm $\mathsf{Sign},$ on input a secret key $x$ and a message $m,$ computes the point $S=xH(m)$ on curve ${\mathbb{G}}_1;$ the signature is $S.$

• The verification algorithm, on input a public key $X,$ a message $m,$ and a signature $S,$ returns 1 (i.e., declares the signature valid) if $$e(S,G_2)=e(H(m),X),\text{\hspace{1em}(17.1)}$$ otherwise it returns 0 (invalid signature).

A good way to think about BLS signatures is as follows: given a message $m$ with corresponding point $H(m)$ in ${\mathbb{G}}_1,$ the signature of $m$ is the point $S$ such that the discrete logarithm of $S$ in base $H(m)$ is equal to the discrete logarithm of $X$ in base $G_2$ (that is, the secret key $x).$ This is reminiscent of the Chaum-Antwerpen undeniable signature scheme [CA89]. Checking discrete logarithm equality is exactly what the pairing $e$ enables to do efficiently.

Note that the signature algorithm is deterministic and hence always returns the same signature for a given secret key/message pair; this is called a unique signature scheme.

The roles of ${\mathbb{G}}_1$ and ${\mathbb{G}}_2$ can be swapped, in which case public keys are in ${\mathbb{G}}_1$ and signatures in ${\mathbb{G}}_2$ (recall that bit string representations of elements are larger and arithmetic is less efficient for ${\mathbb{G}}_2$ than for ${\mathbb{G}}_1,$ so the choice depends on what is more important to optimize depending on the use case). In that case, the hash function must have outputs in ${\mathbb{G}}_2$ and hence this is not possible with a type-2 pairing.

The scheme is correct, meaning that for every key pair $(x,X)$ possibly output by the key generation algorithm and every message $m,$ the signature $S$ computed by the signature algorithm is declared valid by the verification algorithm. Indeed, $$\begin{array}{rl}e(S,G_2)& =e(xH(m),G_2)\\ & =e(H(m),G_2{)}^x\\ & =e(H(m),x{G}_2)\\ & =e(H(m),X),\end{array}$$ hence Eq. (17.1) is satisfied.

Security of BLS

Security Proof

The BLS scheme is provably EUF-CMA-secure assuming the so-called co-CDH${}^{\ast }$ problem is hard for $({\mathbb{G}}_1,{\mathbb{G}}_2)$ and modeling the hash function $H$ as a random oracle. The co-CDH${}^{\ast }$ problem for two groups ${\mathbb{G}}_1$ and ${\mathbb{G}}_2$ of order $r$ is defined as follows: given random generators $G_1$ and $G_2$ of ${\mathbb{G}}_1$ and ${\mathbb{G}}_2$ respectively, $X_1=x{G}_1$ and $X_2=x{G}_2$ for $x{\leftarrow }_{\$}{\mathbb{Z}}_r,$ and a random group element $Y\in {\mathbb{G}}_1,$ compute $xY.$ This might be thought of as CDH in ${\mathbb{G}}_1$ with additional "hint" $(G_2,X_2=x{G}_2)\in {\mathbb{G}}_2^2.$

Theorem 17.1. Assume that the co-CDH${}^{\ast }$ problem is hard for $\mathsf{PairingSetup}.$ Then the BLS signature scheme is EUF-CMA-secure in the random oracle model for $H.$ More precisely, for any adversary $\mathsf{A}$ against the EUF-CMA security of BLS making at most $q_{\mathrm{h}}$ random oracle queries and $q_{\mathrm{s}}$ signature queries, there exists an adversary $\mathsf{B}$ for the co-CDH${}^{\ast }$ problem running in time similar to the time of $\mathsf{A}$ and such that $${\mathbf{Adv}}_{\mathsf{A}}^{\text{euf-cma}}(\lambda )=(q_{\mathrm{h}}+1){\mathbf{Adv}}_{\mathsf{B}}^{\text{co-cdh∗}}(\lambda ).$$

Proof

Let $\mathsf{A}$ be an adversary against the EUF-CMA security of BLS making at most $q_{\mathrm{h}}$ random oracle queries and $q_{\mathrm{s}}$ signature queries. From $\mathsf{A},$ one can easily construct an adversary ${\mathsf{A}}^{\prime }$ having the same advantage as $\mathsf{A}$ and such that (i) ${\mathsf{A}}^{\prime }$ always makes the random oracle query $\text{H}(m^{\ast })$ before returning its forgery $(m^{\ast },S^{\ast })$ and (ii) ${\mathsf{A}}^{\prime }$ makes exactly $q_{\mathrm{h}}+1$ random oracle queries. From now one, we assume that $\mathsf{A}$ satisfies properties (i) and (ii).

We construct an adversary $\mathsf{B}$ for the co-CDH${}^{\ast }$ problem as follows. $\mathsf{B}$ takes as input pairing group parameters $pgpar=({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)$ and a co-CDH${}^{\ast }$ instance $$(G_1,X_1,G_2,X_2,Y)$$ with $X_1=x{G}_1$ and $X_2=x{G}_2.$ It runs $\mathsf{A}$ on input BLS parameters $$({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e,G_2,\text{H})$$ where $\text{H}$ is the interface to the random oracle (that $\mathsf{B}$ will simulate) and public key $X_2.$ At the beginning of the simulation, $\mathsf{B}$ draws a random integer $i^{\ast }{\leftarrow }_{\$}\{1,\dots ,q_{\mathrm{h}}+1\}$ and initializes a table $T$ for storing answers of the simulated random oracle $\text{H}.$ When $\mathsf{A}$ makes a random oracle query $\text{H}(m)$ such that $T(m)$ has not been defined yet, $\mathsf{B}$ either draws ${\rho }_i{\leftarrow }_{\$}{\mathbb{Z}}_r$ and returns $T(m):={\rho }_i{G}_1$ if this is the $i$-th query, $i\ne i^{\ast },$ or returns $T(m):=Y$ if this is the $i^{\ast }$-th query. When $\mathsf{A}$ makes a signing query $\text{Sign}(m),$ then:

• if $T(m)$ is undefined, then $\mathsf{B}$ draws $\rho {\leftarrow }_{\$}{\mathbb{Z}}_r,$ sets $T(m):=\rho G_1,$ and returns the signature $S:=\rho X_1;$ note that this signature is valid since $S=\rho x{G}_1=xT(m);$
• if $T(m)$ has already been defined, this was necessarily during the query $\text{H}(m)$ made by $\mathsf{A};$ if this was the $i$-th query, $i\ne i^{\ast },$ then $\mathsf{B}$ returns the signature $S:={\rho }_i{X}_1;$ again, this signature is valid since $S={\rho }_{i}x{G}_1=xT(m);$ otherwise, if $T(m)$ was defined by the $i^{\ast }$-th query, then $\mathsf{B}$ aborts the simulation of the game and returns $\perp .$

Eventually, when $\mathsf{A}$ halts and returns its forgery $(m^{\ast },S^{\ast }),$ three cases can occur (recall that by assumption $\mathsf{A}$ made the random oracle query $\text{H}(m^{\ast }),$ hence $T(m^{\ast })$ is necessarily defined):

• if $(m^{\ast },S^{\ast })$ is not a valid forgery (either because $m^{\ast }$ was queried to the sign oracle or because the signature is invalid), then $\mathsf{B}$ returns $\perp ;$
• if $(m^{\ast },S^{\ast })$ is a valid forgery and $T(m^{\ast })$ was defined during the $i$-th query to the random oracle, $i\ne i^{\ast },$ the $\mathsf{B}$ returns $\perp ;$
• if $(m^{\ast },S^{\ast })$ is a valid forgery and $T(m^{\ast })$ was defined during the $i^{\ast }$-th query to the random oracle, then $\mathsf{B}$ returns $S^{\ast }$ as solution to the co-CDH${}^{\ast }$ instance.

In the third case, one can easily check that $S^{\ast }$ is the correct solution since $T(m^{\ast })$ was defined as $Y$ so that $S^{\ast }=xT(m^{\ast })=xY.$ Moreover, conditioned on $\mathsf{A}$ being successful, the view of $\mathsf{A}$ is independent from $i^{\ast }$ and hence the third case occurs with probability $1/(q_{\mathrm{h}}+1).$ Hence, $${\mathbf{Adv}}_{\mathsf{B}}^{\text{co-cdh∗}}(\lambda )=\frac{1}{q_{\mathrm{h}}+1}{\mathbf{Adv}}_{\mathsf{A}}^{\text{euf-cma}}(\lambda ).$$

This reduction loses a factor roughly $q_{\mathrm{h}}$ in its success probability. One can obtain a better reduction losing a factor $q_{\mathrm{s}}$ by using a slightly more careful strategy for "embedding" the challenge $Y$ in the random oracle answers, see Section 15.5.1 of the Boneh-Shoup textbook.

Discussion

The various statements and proofs of the security of BLS signatures in the literature can be confusing. The security theorem that we just proved holds for any pairing group setup algorithm. However, depending on the pairing type, it can be rephrased slightly differently.

The original conference paper [BLS01] was only considering symmetric (a.k.a. type-1) pairings (i.e., ${\mathbb{G}}_1={\mathbb{G}}_2=\mathbb{G})$ and proved EUF-CMA security assuming the CDH problem in $\mathbb{G}$ is hard. Theorem 17.1 implies this specific case since for type-1 pairings, hardness of co-CDH${}^{\ast }$ is equivalent to hardness of CDH in $\mathbb{G},$ as we prove now.

Proposition 17.1. Let $\mathsf{PairingSetup}$ be a type-1 pairing group setup algorithm. Then co-CDH${}^{\ast }$ $\equiv$ CDH.

Proof

One the one hand, co-CDH${}^{\ast }$ $\leqq$ CDH is trivial. On the other hand, CDH $\leqq$ co-CDH${}^{\ast }$ can be proved as follows. Let $\mathsf{A}$ be an algorithm for the co-CDH${}^{\ast }$ problem. We construct an algorithm $\mathsf{B}$ for solving CDH as follows. On input $(G_1,X_1=x{G}_1,Y)\in {\mathbb{G}}^3,$ $\mathsf{B}$ draws a random value $\rho {\leftarrow }_{\$}{\mathbb{Z}}_r\setminus \{0\}$ and computes $G_2:=\rho G_1$ and $X_2:=\rho X_1.$ Then $X_2=\rho x{G}_1=x{G}_2$ and $G_2$ is distributed uniformly in $\mathbb{G}\setminus \{0\}$ and independently from $G_1.$ Hence, $(G_1,X_1,G_2,X_2,Y)$ is a correctly distributed instance of co-CDH${}^{\ast }$ that $\mathsf{B}$ can pass as input to $\mathsf{A}.$ The solution $xY$ of this co-CDH${}^{\ast }$ instance is also the solution to the original CDH instance. Hence, the advantage of $\mathsf{B}$ is equal to the advantage of $\mathsf{A}.$

Later, the journal paper [BLS04] considered asymmetric pairings (${\mathbb{G}}_1\ne {\mathbb{G}}_2)$ for which an efficiently computable group isomorphism $\psi$ from ${\mathbb{G}}_2$ to ${\mathbb{G}}_1$ is available (i.e., a type-2 pairing) and proved security assuming the co-CDH problem is hard.¹ The co-CDH problem is similar to the co-CDH${}^{\ast }$ problem except the adversary is only given $G_2\in {\mathbb{G}}_2,$ $X_2=x{G}_2,$ and $Y\in {\mathbb{G}}_1,$ and must compute $xY.$ Again, Theorem 17.1 implies this specific case since for type-2 pairings, co-CDH${}^{\ast }$ is equivalent to co-CDH.

Proposition 17.2. Let $\mathsf{PairingSetup}$ be a type-2 pairing group setup algorithm. Then co-CDH${}^{\ast }$ $\equiv$ co-CDH.

Proof

On the one hand, co-CDH${}^{\ast }$ $\leqq$ co-CDH is straightforward. Conversely, one can prove that co-CDH $\leqq$ co-CDH${}^{\ast }$ as follows. Let $\mathsf{A}$ be an adversary for the co-CDH${}^{\ast }$ problem. We construct an adversary $\mathsf{B}$ for the co-CDH problem as follows. On input $(G_2,X_2=x{G}_2,Y)\in {\mathbb{G}}_2^2\times {\mathbb{G}}_1,$ $\mathsf{B}$ draws a random value $\rho {\leftarrow }_{\$}{\mathbb{Z}}_r\setminus \{0\}$ and computes $G_1:=\psi (\rho G_2)$ and $X_1:=\psi (\rho X_2).$ Then $X_1=\psi (\rho x{G}_2)=x\psi (\rho G_2)=x{G}_1$ and $G_1$ is distributed uniformly in ${\mathbb{G}}_1\setminus \{0\}$ and independently from $G_2.$ Hence, $(G_1,X_1,G_2,X_2,Y)$ is a correctly distributed instance of co-CDH${}^{\ast }$ that $\mathsf{B}$ can pass as input to $\mathsf{A}.$ The solution $xY$ of this co-CDH${}^{\ast }$ instance is also the solution to the original co-CDH instance. Hence, the advantage of $\mathsf{B}$ is equal to the advantage of $\mathsf{A}.$

Interestingly, [BLS04] gives an example of type-3 pairing group setup algorithm (i.e., such that no efficiently computable isomorphism from ${\mathbb{G}}_2$ to ${\mathbb{G}}_1$ is known) for which co-CDH is conjectured to be hard but BLS over this pairing group setup algorithm is insecure. Let ${\mathbb{G}}_2={\mathbb{G}}_t$ be a subgroup of order $r$ of the multiplicative group ${\mathbb{Z}}_p^{\ast },$ let ${\mathbb{G}}_1$ be the additive group ${\mathbb{Z}}_r,$ and let $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_2$ be defined as $e(x,y)=y^x.$ Note that DL is easy in ${\mathbb{G}}_1,$ which implies that DL in ${\mathbb{G}}_2$ reduces to co-CDH (an algorithm solving co-CDH returns $xY,$ which allows to solve for $x$ by computing the discrete log of $xY$ in base $Y$ in ${\mathbb{G}}_1).$ As DL in ${\mathbb{G}}_2$ is conjectured hard for sufficiently large $p$ and $r,$ co-CDH is conjectured hard for $({\mathbb{G}}_1,{\mathbb{G}}_2)$ for such parameters as well. Hence, maybe counter-intuitively, hardness of co-CDH does not necessarily imply hardness of DL in ${\mathbb{G}}_1$! On the other hand, DL being easy in ${\mathbb{G}}_1$ implies that BLS is not EUF-CMA-secure. This shows the necessity of the stronger co-CDH${}^{\ast }$ assumption for proving the security of BLS for type-3 pairings. For type-2 pairings, hardness of co-CDH does imply hardness of DL in ${\mathbb{G}}_2$ (obviously) but also in ${\mathbb{G}}_1,$ as shown by the following proposition.

Proposition 17.3. Let $\mathsf{PairingSetup}$ be a type-2 pairing group setup algorithm. Then $$\text{co-CDH}\leqq {\text{CDH}}_{{\mathbb{G}}_1}\leqq {\text{DL}}_{{\mathbb{G}}_1}.$$

Proof

That CDH${}_{{\mathbb{G}}_1}$ $\leqq$ DL${}_{{\mathbb{G}}_1}$ is clear. Let us show that co-CDH $\leqq$ CDH${}_{{\mathbb{G}}_1}.$ Let $\mathsf{A}$ be an algorithm for solving CDH in ${\mathbb{G}}_1.$ We construct an algorithm $\mathsf{B}$ for the co-CDH problem as follows. On input $(G_2,X_2=x{G}_2,Y)\in {\mathbb{G}}_2^2\times {\mathbb{G}}_1,$ $\mathsf{B}$ computes $G_1:=\psi (G_2)$ and $X_1:=\psi (X_2).$ Then $(G_1,X_1,Y)$ is a correctly distributed CDH instance that $\mathsf{B}$ can pass as input to $\mathsf{A}.$ The solution $xY$ of this CDH instance is also a solution of the original co-CDH instance. Hence, the advantage of $\mathsf{B}$ is equal to the advantage of $\mathsf{A}.$

To finish, we note that hardness of co-CDH${}^{\ast }$ is actually equivalent to EUF-CMA-security of BLS (even for a type-3 pairing where no efficiently computable isomorphism $\psi :{\mathbb{G}}_2\to {\mathbb{G}}_1$ is known). Indeed, given an algorithm $\mathsf{A}$ solving co-CDH${}^{\ast },$ one can construct an adversary $\mathsf{B}$ breaking BLS as follows. Given $G_2$ and a public key $X_2=x{G}_2,$ $\mathsf{B}$ makes queries $G_1:=\text{H}(m)$ and $X_1:=\text{Sign}(m)$ for an arbitrary message $m.$ Note that $X_1=x{G}_1.$ Then it chooses an arbitrary message $m^{\ast }\ne m$ and queries $Y:=\text{H}(m^{\ast }).$ It runs $\mathsf{A}$ on input $(G_1,X_1,G_2,X_2,Y)$ which is a correctly distributed co-CDH${}^{\ast }$ challenge, unless $G_1=0$ which happens with negligible probability. If $\mathsf{A}$ returns the correct answer $S^{\ast }=xY$ to this co-CDH${}^{\ast }$ challenge, then $(m^{\ast },S^{\ast })$ is a valid forgery.

This equivalence holds because we considered the "random generator" variant of co-CDH${}^{\ast }$ where $G_1$ and $G_2$ are drawn at random. As noted in [CHKM10], for type-3 pairings, it is not known whether breaking EUF-CMA-security of BLS reduces to the "fixed generator" variant of co-CDH${}^{\ast }$ where $G_1$ and $G_2$ are fixed (the previous reduction does not work anymore since there is only a negligible chance to "hit" the fixed generator $G_1$ when making queries $\text{H}(m)).$

The following figure summarizes the above results (a double-arrow between two problems meaning equivalence):

graph TD;
    A(CDH) <-- type-1 --> C(co-CDH*);
    B(co-CDH) <-- type-2 --> C;
    C <-- type-1/2/3 --> D(EUF-CMA-sec of BLS);

Note that the notion of type-1/2/3 pairing was only introduced in 2008 [GPS08], a few years after the journal version of the BLS paper [BLS04]. For more discussion about type-2/type-3 pairings and the consequences of an efficiently computable isomorphism $\psi :{\mathbb{G}}_2\to {\mathbb{G}}_1$ in security proofs of pairing-based schemes, see [SV07], [CHKM10], and [CM09].

Signature Aggregation

BLS signatures have a handy property: they can be aggregated non-interactively [BGLS03]. This means that given $n$ signature ${\sigma }_i$ for respective public key/message pairs $(p{k}_i,m_i),$ $0\le i\le n-1,$ it is possible to compute a compact aggregate signature $\sigma$ (of size similar to the one of a single signature) that proves that message $m_i$ was signed by the owner of public key $p{k}_i$ for every $i\in \{0,\dots ,n-1\}$ (exactly as the tuple $({\sigma }_0,\dots ,{\sigma }_{n-1})$ would).

To turn BLS into an aggregate signature scheme, the aggregate signature for a tuple $(S_0,\dots ,S_{n-1})\in {\mathbb{G}}_1^n$ of $n$ signatures is simply defined as the sum of all signatures $S_i:$ $$S:=\sum _{i=0}^{n-1}{S}_i.$$ Note that aggregation can be performed "publicly" by an untrusted party different from all signers. It can also be performed "incrementally", meaning new signatures can be aggregated to an aggregate signature. One can even aggregate aggregate signatures (sic). The only requirement is to keep track of all public key/message pairs the signatures of which have been aggregated.

Given $n$ public key/message pairs $(X_i,m_i),$ $0\le i\le n-1,$ an aggregate signature $S$ is valid for these $n$ pairs if $$e(S,G_2)=\prod _{i=0}^{n-1}e(H(m_i),X_i).\text{\hspace{1em}(17.2)}$$ Even though the size of the aggregate signature is $O(1),$ the complexity of verification still scales linearly with the number of signatures. Correctness of the scheme can be verified similarly to standard BLS signatures.

The EUF-CMA security notion can easily be adapted to aggregate signature schemes: no polynomial-time adversary, being given a target public key $p{k}^{\ast }$ and having access to a standard signature oracle for the corresponding secret key $s{k}^{\ast }$ (i.e., returning non-aggregate signatures), should be able to return an $n$-tuple of public key/message pairs $((p{k}_0,m_0),\dots ,(p{k}_{n-1},m_{n-1}))$ and an aggregate signature $\sigma$ such that:

• $p{k}_i=p{k}^{\ast }$ for some $i\in \{0,\dots ,n-1\},$
• $m_i$ was not queried to the signature oracle,
• $\sigma$ is valid for the tuple $((p{k}_0,m_0),\dots ,(p{k}_{n-1},m_{n-1})).$

Note that the adversary can choose extra public keys $p{k}_j$ as it wishes, in particular as a function of the target public key $p{k}^{\ast }.$

BLS aggregate signatures are provably EUF-CMA-secure assuming hardness of the $\psi$-co-CDH problem and modeling the hash function $H$ as a random oracle. There is one caveat though: messages must be distinct, otherwise a so-called rogue key attack is possible. To see why, say the adversary is given a target public key $X^{\ast }\in {\mathbb{G}}_2.$ Then it can draw $y{\leftarrow }_{\$}{\mathbb{Z}}_r$ and compute a second public key $X^{\prime }:=y{G}_2-X^{\ast }.$ Now, for any message $m,$ the adversary can compute a forgery for the pair $((X^{\ast },m),(X^{\prime },m))$ as $S:=yH(m).$ This forgery satisfies the verification equation as $$\begin{array}{rl}e(H(m),X^{\ast })\cdot e(H(m),X^{\prime })& =e(H(m),X^{\ast })\cdot e(H(m),y{G}_2-X^{\ast })\\ & =e(H(m),X^{\ast }+y{G}_2-X^{\ast })\\ & =e(H(m),y{G}_2)\\ & =e(yH(m),G_2)\\ & =e(S,G_2).\end{array}$$

Note that the adversary does not know the secret key $y-x^{\ast }$ corresponding to public key $X^{\prime }=y{G}_2-X^{\ast },$ hence the name "rogue key attack".

A simple fix against this attack is simply to prepend the public key to the message in the hash function, meaning a signature on message $m$ for secret/public key pair $(x,X)$ is redefined as $$S:=xH(X\Vert m).$$ Then, the condition that messages should be different can safely be lifted [BNN07].

This, however, precludes an interesting optimization of the verification in case all messages are equal.² Indeed, when $m_0=m_1=\cdots =m_{n-1}=m,$ Eq. (17.2) simplifies to $$e(S,G_2)=e(H(m),{\sum }_{i=0}^{n-1}{X}_i).\text{\hspace{1em}(17.3)}$$ Hence, on the right hand-side, instead of a product of $n$ pairings, we now have to compute a single pairing applied to a sum of $n$ elliptic curve points, which can be computed more efficiently.

In order to be able to use (17.3) for verification when messages are equal, a different fix can be used to thwart rogue key attacks. Namely, each user must provide a proof of possession (PoP) of the secret key associated with his public key. The notion of PoP is somewhat informal as, to the best of my knowledge, there is not rigorous definition of the security properties it should have. The idea is that it should demonstrate that the user has access to the functionality associated with his public key, namely signing. Hence, a simple PoP consists of the user signing its own public key, $\pi :=x{H}^{\prime }(X).$ Intuitively, this makes sense since in a rogue key attack, the adversary cannot compute the secret key associated with the rogue public key (which it computes as a function of the target public key). This solution was proved secure assuming the hash function used for the PoP is different from the hash function used for actual message signing, which can be achieved from a single hash function by enforcing domain separation [RY07].

A Note about Non-Repudiation

Non-repudiation is often presented as a logical consequence of existential unforgeability (if no one except Alice can produce a valid signature on message $m,$ and a valid signature on message $m$ is presented to a judge, the judge should conclude that Alice actually did sign message $m).$ But what if Alice was able to choose her secret/public key pair $(sk,pk)$ in a way that allows her to find two messages $m$ and $m^{\prime }$ and a signature $\sigma$ which is valid for both messages, i.e., $$\mathsf{Verif}(pk,m,\sigma )=\mathsf{Verif}(pk,m^{\prime },\sigma )=1.\text{\hspace{1em}(17.4)}$$ Then, confronted by the judge with a valid signature $\sigma$ for message $m,$ Alice could claim that she has in fact signed $m^{\prime }$ instead. Hence, non-repudiation should rather be seen as the combination of existential unforgeability with a second security notion, often called message biding in the literature, which demands that no malicious user be able to generate a public key $pk,$ two messages $m$ and $m^{\prime },$ and a signature $\sigma$ such that $m\ne m^{\prime }$ and (17.4) holds.

It is easy to see that standard BLS signatures are message binding if $H$ is collision-resistant. Things are more subtle though when considering aggregate signatures [Qua21]. In particular, if $t\ge 2$ users collide (or if a single malicious user controls $t\ge 2$ public keys), they can arrange to choose their public keys $X_0,\dots ,X_{t-1}$ such that $$X_0+\cdots +X_{t-1}=0.$$ Then, in the PoP-based variant of the scheme where Eq. (17.3) is used for verification, $S=0$ is a valid signature for any message $m:$ the scheme is not message binding. Note that checking that $S\ne 0$ in the verification algorithm does not thwart the attack as $S$ can be further aggregated with other valid signatures $S_t,\dots ,S_{n-1}$ for arbitrary public key/message pairs $(X_t,m_t),$ $\dots ,$ $(X_{n-1},m_{n-1}),$ resulting in an aggregate signature $S^{\prime }\ne 0$ which still does not bound signers $0,\dots t-1$ to a specific message.

Further Topics to Cover

• BLS multi-signatures [BDN18]
• BLS threshold signatures [BL22]
• use of BLS signatures in the Ethereum beacon chain

---

1: Somehow confusingly, recent papers tend to use the name co-CDH for what we call co-CDH${}^{\ast }$ here.

2: The setting where all users sign the exact same message requires a primitive slightly different from an aggregate signature scheme called a multisignature scheme.