Paper 2023/1820

Chipmunk: Better Synchronized Multi-Signatures from Lattices

Nils Fleischhacker, Ruhr University Bochum
Gottfried Herold, Ethereum Foundation
Mark Simkin, Ethereum Foundation
Zhenfei Zhang, Ethereum Foundation

Multi-signatures allow for compressing many signatures for the same message that were generated under independent keys into one small aggregated signature. This primitive is particularly useful for proof-of-stake blockchains, like Ethereum, where the same block is signed by many signers, who vouch for the block's validity. Being able to compress all signatures for the same block into a short string significantly reduces the on-chain storage costs, which is an important efficiency metric for blockchains. In this work, we consider multi-signatures in the synchronized setting, where the signing algorithm takes an additional time parameter as input and it is only required that signatures for the same time step are aggregatable. The synchronized setting is simpler than the general multi-signature setting, but is sufficient for most blockchain related applications, as signers are naturally synchronized by the length of the chain. We present Chipmunk, a concretely efficient lattice-based multi-signature scheme in the synchronized setting that allows for signing an a-priori bounded number of messages. Chipmunk allows for non-interactive aggregation of signatures and is secure against rogue-key attacks. The construction is plausibly secure against quantum adversaries as our security relies on the assumed hardness of the short integer solution problem. We significantly improve upon the previously best known construction in this setting by Fleischhacker, Simkin, and Zhang (CCS 2022). Our aggregate signature size is $5.6 \times$ smaller and for $112$ bits of security our construction allows for compressing 8192 individual signatures into a multi-signature of size around $136$ KB. We provide a full implementation of Chipmunk and provide extensive benchmarks studying our construction's efficiency.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. 2023 ACM SIGSAC Conference on Computer and Communications Security
Multi-SignaturesLatticesConcrete Efficiency
Contact author(s)
mail @ nilsfleischhacker de
gottfried herold @ ethereum org
mark simkin @ ethereum org
zhenfei zhang @ ethereum org
2023-11-27: revised
2023-11-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nils Fleischhacker and Gottfried Herold and Mark Simkin and Zhenfei Zhang},
      title = {Chipmunk: Better Synchronized Multi-Signatures from Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1820},
      year = {2023},
      doi = {3576915.3623219},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.