Transparent Fully Batchable Polynomial Commitment with Application to Scalable VSS

Verifiable secret sharing (VSS) is a fundamental cryptographic primitive, and one of the most popular ways to construct VSS is to use polynomial commitments (PC). In the realm of PC-based VSS, two research directions have been explored to improve the efficiency of VSS. The first is optimizing the dealer time by designing PC schemes that support batch evaluation, i.e., generating multiple proofs in one shot. The second is reducing the broadcast cost by designing PC schemes that support batch opening, i.e., generating a succinct proof for multiple evaluations. Recently, Zhang et al. (Usenix Security 2022) proposed a transparent PC scheme that supports batch evaluation and obtained a transparent VSS scheme with optimal dealer time. However, their PC scheme does not support batch opening, leading to high broadcast costs in VSS. Prior transparent PC schemes focus on either batch evaluation or batch opening, but not both simultaneously, which limits the performance of VSS. In this paper, we propose a transparent fully batchable polynomial commitment (FB-PC) scheme that simultaneously supports batch evaluation and batch opening. Leveraging our FB-PC scheme, we present a VSS scheme with optimal asymptotic complexity: \(O(n\log n)\) dealer time, O(n) participant time, and O(n) communication cost. Furthermore, we implement our VSS scheme and compare it with Zhang et al.’s VSS. Results show that our scheme achieves a \(494\text {-}26,907\times \) speedup in participant time and a \(507\text {-}549,484\times \) reduction in communication cost for \(2^{11}\) to \(2^{21}\) participants.