Aggregation signature forgery attack

1. Initialization. The aggregate signature forger 𝒜 obtains a randomly generated public key pk₁.

2. Queries. Proceeding adaptively, 𝒜 requests signatures with pk₁ on messages of his choice.

3. Response. Finally, 𝒜 outputs k − 1 additional public keys pk₂, …, pk_k. Here k is a game parameter, at most N. These keys and the initial key pk₁ will be included in the aggregate signature forged by 𝒜. 𝒜 also outputs messages m₁, …, m_k, and finally, 𝒜 generates an aggregate signature σ that is signed by k users on their corresponding messages.

4. If the aggregate signature σ is an effective aggregation of messages m₁, …, m_k under the keys pk₁, …, pk_k, and σ is nontrivial, i.e., that is, 𝒜 did not request a signature on M₁ under pk₁, the forger wins. The probability is over the coin tosses of the key-generation algorithm and of 𝒜.