DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures

An interactive aggregate signature scheme enables $n$ signers, each with their own secret/public key pair $(\mathit{sk}_i, \mathit{pk}_i)$ and message $m_i$, to collaboratively produce a single compact signature that attests that each message $m_i$ has been signed under the corresponding public key $\mathit{pk}_i$. Despite their potential for significant space and verification time savings when compared to the processing of many individual signatures, aggregate signatures have received considerably less attention than other multi-party signatures such as multi-signatures and threshold signatures.

In this paper, we propose $\mathsf{DahLIAS}$, the first aggregate signature scheme with constant-size signatures based directly on discrete logarithms in pairing-free groups. Its signing protocol consists of two rounds, the first of which can be preprocessed without knowledge of the messages to be signed. An aggregate signature has the same shape as standard Schnorr signatures, and its verification time is dominated by a multi-exponentiation of size $n+1$, which achieves a $2\times$ asymptotic speedup over batch verification of $n$ individual Schnorr signatures. With its explicit support for key tweaking, a technique commonly used for advanced key derivation in cryptocurrencies, $\mathsf{DahLIAS}$ is designed to be secure in real-world applications. We prove $\mathsf{DahLIAS}$ secure in the concurrent setting with key tweaking under the algebraic one-more discrete logarithm assumption in the random oracle model.