Faster VOLEitH Signatures from All-but-One Vector Commitment and Half-Tree

Dung Bui; Kelong Cong; Cyprien Delpech de Saint Guilhem

Paper 2024/097

Faster VOLEitH Signatures from All-but-One Vector Commitment and Half-Tree

Dung Bui

, IRIF, Université Paris Cité

Kelong Cong

, Zama

Cyprien Delpech de Saint Guilhem

, 3MI Labs

Abstract

Post-quantum digital signature schemes have recently received increased attention due to the NIST standardization project for additional signatures. MPC-in-the-Head and VOLE-in-the-Head are general techniques for constructing such signatures from zero-knowledge proof systems. A common theme between the two is an all-but-one vector commitment scheme which internally uses GGM trees. This primitive is responsible for a significant part of the computational time during signing and verification. A more efficient technique for constructing GGM trees is the half-tree technique, introduced by Guo et al. (Eurocrypt 2023). Our work builds an all-but-one vector commitment scheme from the half-tree technique, and further generalizes it to an all-but- vector commitment scheme. Crucially, our work avoids the use of the random oracle assumption in an important step, which means our binding proof is non-trivial and instead relies on the random permutation oracle. Since this oracle can be instantiated using fixed-key AES which has hardware support, we achieve faster signing and verification times. We integrate our vector commitment scheme into FAEST (faest.info), a round one candidate in the NIST standardization process, and demonstrate its performance with a prototype implementation. Our implementation is between and faster across all parameter sets.

Note: Revised the construction and resolved issues related to binding security.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Major revision. ACISP 2025
Keywords: Vector commitment Correlation robustness Post-quantum signature Zero-knowledge proof
Contact author(s): bui @ irif fr
kelong cong @ zama ai
cyprien @ 3milabs tech
History: 2025-05-23: last of 8 revisions; 2024-01-22: received; See all versions
Short URL: https://ia.cr/2024/097
License: CC BY

BibTeX

@misc{cryptoeprint:2024/097,
      author = {Dung Bui and Kelong Cong and Cyprien Delpech de Saint Guilhem},
      title = {Faster {VOLEitH} Signatures from All-but-One Vector Commitment and Half-Tree},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/097},
      year = {2024},
      url = {https://eprint.iacr.org/2024/097}
}