Paper 2024/490

One Tree to Rule Them All: Optimizing GGM Trees and OWFs for Post-Quantum Signatures

Carsten Baum, Aarhus University
Ward Beullens, IBM Research Zurich
Shibam Mukherjee, Graz University of Technology
Emmanuela Orsini, Bocconi University
Sebastian Ramacher, Austrian Institute of Technology
Christian Rechberger, Graz University of Technology
Lawrence Roy, Aarhus University
Peter Scholl, Aarhus University

The use of MPC-in-the-Head (MPCitH)-based zero-knowledge proofs of knowledge (ZKPoK) to prove knowledge of a preimage of a one-way function (OWF) is a popular approach towards constructing efficient post-quantum digital signatures. Starting with the Picnic signature scheme, many optimized MPCitH signatures using a variety of (candidate) OWFs have been proposed. Recently, Baum et al. (CRYPTO 2023) showed a fundamental improvement to MPCitH, called VOLE-in-the-Head (VOLEitH), which can generically reduce the signature size by at least a factor of two without decreasing computational performance or introducing new assumptions. Based on this, they designed the FAEST signature which uses AES as the underlying OWF. However, in comparison to MPCitH, the behavior of VOLEitH when using other OWFs is still unexplored. In this work, we improve a crucial building block of the VOLEitH and MPCitH approaches, the so-called all-but-one vector commitment, thus decreasing the signature size of VOLEitH and MPCitH signature schemes. Moreover, by introducing a small Proof of Work into the signing procedure, we can improve the parameters of VOLEitH (further decreasing signature size) without compromising the computational performance of the scheme. Based on these optimizations, we propose three VOLEitH signature schemes FAESTER, KuMQuat, and MandaRain based on AES, MQ, and Rain, respectively. We carefully explore the parameter space for these schemes and implement each, showcasing their performance with benchmarks. Our experiments show that these three signature schemes outperform MPCitH-based competitors that use comparable OWFs, in terms of both signature size and signing/verification time.

Available format(s)
Cryptographic protocols
Publication info
Post-QuantumVOLEitHSignature Schemes
Contact author(s)
cabau @ dtu dk
ward @ beullens com
shibam mukherjee @ iaik tugraz at
emmanuela orsini @ unibocconi it
sebastian ramacher @ ait ac at
christian rechberger @ tugraz at
ldr709 @ gmail com
peter scholl @ cs au dk
2024-03-27: approved
2024-03-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carsten Baum and Ward Beullens and Shibam Mukherjee and Emmanuela Orsini and Sebastian Ramacher and Christian Rechberger and Lawrence Roy and Peter Scholl},
      title = {One Tree to Rule Them All: Optimizing {GGM} Trees and {OWFs} for Post-Quantum Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2024/490},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.