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

TY - GEN

T1 - One Tree to Rule Them All:

T2 - Optimizing GGM Trees and OWFs for Post-Quantum Signatures

AU - Baum, Carsten

AU - Beullens, Ward

AU - Mukherjee, Shibam

AU - Orsini, Emmanuela

AU - Ramacher, Sebastian

AU - Rechberger, Christian

AU - Roy, Lawrence

AU - Scholl, Peter

PY - 2025

Y1 - 2025

N2 - 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.

AB - 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.

KW - Post-Quantum

KW - Signature Schemes

KW - VOLEitH

UR - https://www.scopus.com/pages/publications/85213368982

U2 - 10.1007/978-981-96-0875-1_15

DO - 10.1007/978-981-96-0875-1_15

M3 - Article in proceedings

SN - 978-981-96-0875-1

T3 - Lecture Notes in Computer Science

SP - 463

EP - 493

BT - Advances in Cryptology - ASIACRYPT 2024

A2 - Chung, Kai-Min

A2 - Sasaki, Yu

PB - Springer Nature

CY - Singapore

ER -