Paper 2021/1048

Aggregating and thresholdizing hash-based signatures using STARKs

Irakliy Khaburzaniya, Konstantinos Chalkias, Kevin Lewi, and Harjasleen Malvai


This work presents an approach for compressing hash-based signatures using STARKs (Ben-Sasson et. al.'18). We focus on constructing a hash-based t-of-n threshold signature scheme, as well as an aggregate signature scheme. In both constructions, an aggregator collects individual one-time hash-based signatures and outputs a STARK proof attesting that the signatures are valid and meet the required thresholds. This proof then serves the role of the aggregate or threshold signature. We demonstrate the concrete performance of such constructions, having implemented the algebraic intermediate representations (AIR) for them, along with an experimental evaluation over our implementation of the STARK protocol. We find that, even when we aggregate thousands of signatures, the final aggregated size ranges between 100KB and 200KB. This makes our schemes attractive when there exist at least $50$ one-or-few-times hash-based signatures -- such as in the blockchain setting. We also observe that for STARK-based signature aggregation, the size of individual signatures is less important than the number of hash invocations and the complexity of the signature verification algorithm. This implies that simple hash-based signature variants (e.g. Lamport, HORST, BPQS) are well-suited for aggregation, as their large individual signatures serve only as witnesses to the ZKP circuit and are not needed for aggregate signature verification. Our constructions are directly applicable as scalable solutions for post-quantum secure blockchains which typically employ blocks of hundreds or thousands of signed transactions. Moreover, stateful hash-based one-or-few-times signatures are already used in some PQ-ready blockchains, as address reuse is typically discouraged for privacy reasons.

Available format(s)
Publication info
Published elsewhere. Minor revision.AsiaCCS 2022
digital signaturehash-based schemessignature aggregationthreshold signaturesblockchain compressionSTARK proofs
Contact author(s)
kostascrypto @ fb com
irakliyk @ fb com
klewi @ fb com
chalkiaskostas @ gmail com
bobbinth @ protonmail com
hmalvai2 @ illinois edu
2022-03-14: revised
2021-08-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Irakliy Khaburzaniya and Konstantinos Chalkias and Kevin Lewi and Harjasleen Malvai},
      title = {Aggregating and thresholdizing hash-based signatures using STARKs},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1048},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.