An Improved Vector Commitment Construction with Applications to Signatures

All-but-one Vector Commitments (AVCs) randomly opens all but one of the committed vector 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. Correlated GGM (cGGM) trees have been proposed to halve the number of hash calls and Batched AVCs (BAVCs) using a single GGM tree were integrated in the FAEST signature scheme, which improves efficiency and reduces the signature sizes. This paper proposes BACON, a BAVC with aborts that leverages a single 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 and show the theoretical efficiency compared to state-of-the-art.