Paper 2026/1474

Mu-qt-PEGASIS: Interactive Aggregate Signatures from Effective Isogenies in the Programmable Random-Oracle Model

Abstract

We present Mu-qt-PEGASIS, a mathematically precise con- ditional compiler for interactive aggregate signatures built from the qt-PEGASIS effective class-group action. Our central observation is that the torsor structure of the public-key space blocks the standard Schnorr- or BLS-style verification equations used in conventional aggregate sig- natures. We resolve this by separating verification into two layers: a proof-authentication layer that certifies public-key registration and round- robin key aggregation, and a transcript-consistency layer that verifies the final aggregate signature relative to an authenticated aggregate key. The resulting framework is formulated in the programmable random-oracle model. Public-key registration and linked aggregation are authenticated via Fiat–Shamir compilations of explicit public-coin Σ-protocols for the relations Rreg and Rlink . Under the hardness of the Group Action Inverse Problem (GAIP), together with the random-oracle assumptions for Hnizk and Hsig , we prove MU-EUF-CMA security against static corruptions. At the protocol level, for a fixed Fiat–Shamir repetition parameter t, the aggregate signature has size O(t) and is independent of the number of signers n, while the authenticated registration and aggregation transcript remain linear in n.