[Resource Topic] 2023/1820: Chipmunk: Better Synchronized Multi-Signatures from Lattices

Welcome to the resource topic for 2023/1820

Chipmunk: Better Synchronized Multi-Signatures from Lattices

Authors: Nils Fleischhacker, Gottfried Herold, Mark Simkin, Zhenfei Zhang


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.

ePrint: https://eprint.iacr.org/2023/1820

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .