BACON: An Improved Vector Commitment Construction with Applications to Signatures

Yalan Wang; Bryan Kumara; Harsh Kasyap; Liqun Chen; Sumanta Sarkar; Christopher J.P. Newton; Carsten Maple; Ugur Ilker Atmaca

Paper 2025/1411

BACON: An Improved Vector Commitment Construction with Applications to Signatures

Yalan Wang, University of Surrey

Bryan Kumara, The Alan Turing Institute

Harsh Kasyap, The Alan Turing Institute, University of Warwick

Liqun Chen, University of Surrey

Sumanta Sarkar, University of Essex

Christopher J.P. Newton, University of Surrey

Carsten Maple, The Alan Turing Institute, University of Warwick

Ugur Ilker Atmaca, The Alan Turing Institute, University of Warwick

Abstract

All-but-one Vector Commitments (AVCs) allow a committed vector to be verified by randomly opening all but one of the committed values. Typically, AVCs are instantiated using Goldwasser-Goldreich-Micali (GGM) trees. Generating these trees comprises a significant computational cost for AVCs due to a large number of hash function calls. Recently, correlated GGM (cGGM) trees were proposed to halve the number of hash calls and Batched AVCs (BAVCs) using one large GGM tree were integrated to FAEST to form the FAEST version 2 signature scheme, which improves efficiency and reduces the signature size. However, further optimizations on BAVC schemes remain possible. Inspired by the large-GGM based BAVC and the cGGM tree, this paper proposes BACON, a BAVC with aborts scheme by leveraging a large cGGM tree. BACON executes multiple instances of AVC in a single batch and enables an abort mechanism to probabilistically reduce the commitment size. We prove that BACON is secure under the ideal cipher model and the random oracle model. We also discuss the possible application of the proposed BACON, i.e., FAEST version 2. Furthermore, because the number of hash calls in a large cGGM tree is halved compared with that used in a large GGM tree, theoretically, our BACON is more efficient than the state-of-the-art BAVC scheme.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Correlated GGM trees Batched all-but-one vector commitments Post-quantum signatures
Contact author(s): yw0010 @ surrey ac uk
kumara bryan @ gmail com
hkasyap @ turing ac uk
liqun chen @ surrey ac uk
sumanta sarkar @ essex ac uk
c newton @ surrey ac uk
cmaple @ turing ac uk
uatmaca @ turing ac uk
History: 2025-08-04: revised; 2025-08-02: received; See all versions
Short URL: https://ia.cr/2025/1411
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1411,
      author = {Yalan Wang and Bryan Kumara and Harsh Kasyap and Liqun Chen and Sumanta Sarkar and Christopher J.P. Newton and Carsten Maple and Ugur Ilker Atmaca},
      title = {{BACON}: An Improved Vector Commitment Construction with Applications to Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1411},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1411}
}