Cryptology ePrint Archive: Report 2021/1048

Aggregating hash-based signatures using STARKs

Irakliy Khaburzaniya and Konstantinos Chalkias and Kevin Lewi and Harjasleen Malvai

Abstract: This work presents an approach for compressing regular 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, making our schemes attractive when there exist at least 50 one-or-few-times hash-based signatures. 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.

Category / Keywords: applications / digital signature, hash-based schemes, signature aggregation, threshold signatures, blockchain compression, STARK proofs

Date: received 12 Aug 2021

Contact author: kostascrypto at fb com, irakliyk at fb com, klewi at fb com, chalkiaskostas at gmail com, bobbinth at protonmail com

Available format(s): PDF | BibTeX Citation

Version: 20210816:131309 (All versions of this report)

Short URL: ia.cr/2021/1048


[ Cryptology ePrint archive ]