Paper 2022/694

Squirrel: Efficient Synchronized Multi-Signatures from Lattices

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

The focus of this work are multi-signatures schemes in the synchronized setting. A multi-signature scheme allows multiple signatures for the same message but from independent signers to be compressed into one short aggregated signature, which allows verifying all of the signatures simultaneously. In the synchronized setting, the signing algorithm takes the current time step as an additional input. It is assumed that no signer signs more than one message per time step and we aim to aggregate signatures for the same message and same time step. This setting is particularly useful in the context of blockchains, where validators are naturally synchronized by the blocks they sign. We present Squirrel, a concretely efficient lattice-based multi-signature scheme in the synchronized setting that works for a bounded number of $2^{\tau}$ time steps and allows for aggregating up to $\rho$ signatures at each step, where both $\tau$ and $\rho$ are public parameters upon which the efficiency of our scheme depends. Squirrel allows for non-interactive aggregation of independent signatures and is proven secure in the random oracle model in the presence of rogue-key attacks assuming the hardness of the short integer solution problem in a polynomial ring. We provide a careful analysis of all parameters and show that Squirrel can be instantiated with good concrete efficiency. For $\tau = 24$ and $\rho = 4096$, a signer could sign a new message every 10 seconds for 5 years non-stop. Assuming the signer has a cache of 112 MB, signing takes 68 ms and verification of an aggregated signature takes 36 ms. The size of the public key is 1 KB, the size of an individual signature is 52 KB, and the size of an aggregated signature is 771 KB.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. ACM CCS 2022
Lattices Multi-Signatures Squirrels SIS
Contact author(s)
mail @ nilsfleischhacker de
mark simkin @ ethereum org
zhenfei zhang @ ethereum org
2022-09-01: revised
2022-06-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nils Fleischhacker and Mark Simkin and Zhenfei Zhang},
      title = {Squirrel: Efficient Synchronized Multi-Signatures from Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2022/694},
      year = {2022},
      doi = {10.1145/3548606.3560655},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.