Multi-signatures are a crucial cryptographic primitive in distributed systems. Of particular interest are constructions over pairing-free cyclic groups with a two-round signing protocol. Additionally, support for key aggregation is highly desired, as it allows combining multiple public keys into a single succinct aggregate public key for verification. To enhance the concrete security, several works have proposed constructions with tight security proofs. Unfortunately, these constructions have major limitations. T-Spoon by Bacho and Wagner (Crypto 2025) is the only pairing-free two-round multi-signature scheme to achieve tight security and support key aggregation. However, it suffers from prohibitively large signatures, consisting of 9 field elements and 2 group elements. In this work, we propose Earpick-MS, a tightly secure, two-round multi-signature scheme with key aggregation and compact signatures. The signature consists of only three field elements plus a single bit. This improves upon the state-of-the-art T-Spoon by a factor of more than 3.5. We also propose a threshold signature variant of our scheme, Earpick-TS. It features the same compact signature size and is the first pairing-free two-round threshold signature scheme with tight security. Previously, such schemes required at least three rounds (Chen, PKC 2025).

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Earpicks: Tightly Secure Two-Round Multi and Threshold Signatures

  • Renas Bacho,
  • Yanbo Chen

摘要

Multi-signatures are a crucial cryptographic primitive in distributed systems. Of particular interest are constructions over pairing-free cyclic groups with a two-round signing protocol. Additionally, support for key aggregation is highly desired, as it allows combining multiple public keys into a single succinct aggregate public key for verification. To enhance the concrete security, several works have proposed constructions with tight security proofs. Unfortunately, these constructions have major limitations. T-Spoon by Bacho and Wagner (Crypto 2025) is the only pairing-free two-round multi-signature scheme to achieve tight security and support key aggregation. However, it suffers from prohibitively large signatures, consisting of 9 field elements and 2 group elements. In this work, we propose Earpick-MS, a tightly secure, two-round multi-signature scheme with key aggregation and compact signatures. The signature consists of only three field elements plus a single bit. This improves upon the state-of-the-art T-Spoon by a factor of more than 3.5. We also propose a threshold signature variant of our scheme, Earpick-TS. It features the same compact signature size and is the first pairing-free two-round threshold signature scheme with tight security. Previously, such schemes required at least three rounds (Chen, PKC 2025).