Subset-optimized BLS Multi-signature with Key Aggregation

You can find the slides in this here.

• Introduction
  • Focus on improving BLS (Boneh-Lynn-Shacham) multi-signatures with subset optimization and key aggregation.
  • Presented at FC’24 by Mahdi Sedaghat and co-authors.
• Multi-Signatures Overview
  • Allows n signers to produce a single signature on the same message m.
  • Challenges:
    • Signature size grows linearly with the number of signers (O(n)).
    • Rogue key attacks pose a security threat.
  • Goals:
    • Efficient signature aggregation and verification.
    • Key aggregation to produce a single aggregate public key (apk).
• Applications of Multi-Signatures
  • Multi-user wallets.
  • Layer-2 protocols.
  • Collective signing of digital certificates.
  • Block validation in Proof-of-Stake (PoS) or permissioned ledgers.
• Technical Details
  • Uses Type-III bilinear groups for efficient pairing-based signatures.
  • Subset optimization:
    • Signatures are aggregated within a subset of k validators out of a fixed committee of n members.
    • Reduces computational costs by focusing on subsets rather than the entire committee.
  • Key aggregation:
    • Aggregates public keys of validators into a single key (apk).
    • Key aggregation is performed once per epoch for efficiency.
• Security Properties
  • Based on assumptions:
    • Computational Diffie-Hellman (CDH).
    • Discrete Logarithm (DL) and Random Modular Subset Sum (RMSS) assumptions.
  • Proofs provided for both weak and strong adversaries.
• Performance
  • Implementation details:
    • Developed over the BLS12-381 curve using the Rust blst library.
    • Tested on an AWS t3.medium instance with 2 virtual CPUs.
  • Performance results:
    • Signature aggregation takes less than 0.2 ms for 100 signers.
    • Verification takes less than 1.5 ms.
    • Outperforms baseline [BDN’18], saving 25 ms for aggregation and 50 ms for public key generation.
• Conclusion and Open Problems
  • Subset-optimized multi-signature schemes enhance efficiency and security in PoS systems.
  • Open questions:
    • Extend SMSKR (Subset Multi-Signature with Key Randomization) to other schemes like Schnorr and MuSig2.
    • Eliminate reliance on the RMSS assumption.