Introduction
Verifiable Secret Sharing (VSS) is a cornerstone of distributed cryptography, serving as a critical building block for Multi-Party Computation (MPC), Byzantine Agreement, and threshold cryptography. In a VSS protocol, a "dealer" distributes shares of a secret among $n$ parties. The protocol ensures two properties: first, that the secret can be reconstructed even if the dealer or a subset of parties are malicious; and second, that the secret remains hidden from any unauthorized coalition of parties.
For decades, the most efficient computational VSS schemes—most notably those by Feldman and Pedersen—have relied heavily on homomorphic commitments. These cryptographic primitives allow parties to perform mathematical operations on committed values without revealing the underlying data. However, this reliance creates a bottleneck: homomorphic properties are not universal and are typically tied to specific algebraic assumptions. This paper challenges the long-standing assumption that homomorphism is essential for efficient VSS and provides the first formal analysis of round complexity in the computational setting.
Rethinking the Necessity of Homomorphism
The authors demonstrate that the fundamental properties of commitment schemes—binding and hiding—are sufficient to achieve VSS. To bypass the need for homomorphism, the research introduces a construction based on symmetric bivariate polynomials $F(x, y)$ rather than the standard univariate polynomials used in Shamir’s Secret Sharing.
In this model, the dealer commits to the coefficients of the bivariate polynomial. This structure allows parties to perform pairwise consistency checks: party $i$ and party $j$ can verify that their respective shares are consistent (i.e., $f_i(j) = f_j(i)$) using standard commitments. This approach effectively replaces the need to "add" commitments together, allowing VSS to be built from any standard commitment scheme, including those based on simple one-way functions or collision-resistant hash functions. This shift significantly broadens the cryptographic foundations of VSS, potentially paving the way for more robust post-quantum protocols.
Achieving Optimal Round Complexity
A major contribution of this work is the formalization of round complexity for computational VSS. In the synchronous communication model, traditional protocols often require three rounds (distribute, accuse, and resolve). The authors prove that while 1-round VSS is impossible for most practical scenarios ($t \ge 2$ or $n \le 3t$), a 2-round protocol is achievable and optimal.
To reach this 2-round "sweet spot," the authors utilize a technique where parties send randomness to the dealer in the first round. The dealer then uses this randomness as a "blinding pad" to broadcast shares in the second round. This collapses the interaction while maintaining optimal resiliency ($n \ge 2t+1$). Furthermore, the authors provide a new 2-round VSS scheme using homomorphic commitments that matches the communication complexity of classic 3-round schemes, offering a direct efficiency upgrade for existing systems.
Asynchronous Feasibility and Trade-offs
The paper extends its analysis to the asynchronous model, where message delays are unpredictable. The authors introduce an asynchronous VSS (AVSS) protocol for $n \ge 3t+1$ that maintains $O(n^2)$ message complexity without requiring homomorphism. This demonstrates that the flexibility of non-homomorphic commitments extends across different network assumptions.
However, removing the homomorphism requirement is not without cost. The authors identify a communication trade-off: non-homomorphic schemes require approximately $O(n^2\kappa)$ bits of communication, which is a linear factor $n$ higher than their homomorphic counterparts. This increase stems from the dealer's need to commit to a larger number of points to ensure consistency across the network.
Conclusion and Future Directions
This research establishes that homomorphic commitments are a luxury rather than a necessity for Verifiable Secret Sharing. By providing tight lower bounds and optimal 2-round constructions, the paper clarifies the theoretical limits of computational VSS.
While the bandwidth overhead of non-homomorphic schemes remains a limitation, the ability to build VSS from any commitment scheme is a significant theoretical advancement. Future work remains to determine if the linear-factor gap in communication complexity is an inherent cost of removing algebraic assumptions and how these non-homomorphic techniques can be integrated into higher-level protocols like distributed key generation (DKG) that currently rely on homomorphic properties.
Summary updated