Proof of membership in an aggregated BLS signature

Question

Is it possible to prove that a given signature is a part of an aggregated BLS signature? Specifically, given:

• $m_1...m_n$ are $n$ distinct messages
• $p_1...p_n$ are private keys with $P_1...P_n$ being the corresponding public keys
• $S_1...S_n$ are BLS signatures such that $S_i = sig(m_i, p_i)$
• $A = S_1 + S_2 + ... + S_n$ is the aggravated BLS signature

Is it possible to prove that a signature $S_i$ is contained within $A$ using only publicly available data: $A$, $S_i$, $P_i$, and $m_i$?

Answer 1

Yes, it is possible. What you are referring to is called local aggregation. The proof is a small hint that is calculated from the set. The verifier can verify a signature on a message without knowing the full set. Thus, the runtime of the verifier is independent of the size of the set; unlike the other answer.

This paper, Locally Verifiable Signatures and Key Aggregation, from Goyal & Vaikuntanathan was published recently in CRYPTO22.