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

Carsten Baum, Ward Beullens, Shibam Mukherjee (Autor:in und Vortragende:r), Emmanuela Orsini, Sebastian Ramacher, Christian Rechberger, Lawrence Roy, Peter Scholl

Publikation: Beitrag in Buch oder TagungsbandVortrag mit Beitrag in TagungsbandBegutachtung

Abstract

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.
OriginalspracheEnglisch
TitelAdvances in Cryptology – ASIACRYPT 2024
Untertitel30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part I
Redakteure/-innenKai-Min Chung, Yu Sasaki
Herausgeber (Verlag)Springer
Seiten463–493
Band15484
ISBN (elektronisch)978-981-96-0875-1
ISBN (Print)978-981-96-0874-4
DOIs
PublikationsstatusVeröffentlicht - Dez. 2024
Veranstaltung30th International Conference on the Theory and Application of Cryptology and Information Security - Kolkata, Kolkata, Indien
Dauer: 9 Dez. 202413 Dez. 2024

Publikationsreihe

NameASIACRYPT: International Conference on the Theory and Application of Cryptology and Information Security
Herausgeber (Verlag)Springer

Konferenz

Konferenz30th International Conference on the Theory and Application of Cryptology and Information Security
Land/GebietIndien
StadtKolkata
Zeitraum9/12/2413/12/24

Research Field

  • Cyber Security

Fingerprint

Untersuchen Sie die Forschungsthemen von „One Tree to Rule Them All: Optimizing GGM Trees and OWFs for Post-Quantum Signatures“. Zusammen bilden sie einen einzigartigen Fingerprint.

Diese Publikation zitieren