Computational Verifiable Secret Sharing Revisited

Michael Backes, Aniket Kate, Arpita Patra

TL;DR

This paper revisits Verifiable Secret Sharing (VSS) in the computational setting, demonstrating that homomorphic commitments, previously thought essential, are not necessary for efficient VSS. The authors introduce new VSS schemes that achieve optimal round complexity and communication efficiency, offering a practical alternative to existing methods and paving the way for more robust distributed systems.

What Problem Does This Paper Address?

Verifiable Secret Sharing (VSS) is a fundamental cryptographic primitive that allows a dealer to securely distribute a secret among multiple parties, ensuring that even if some parties are malicious, honest parties can reconstruct the secret. In the computational setting, where adversaries have limited computational power, VSS schemes have been developed using cryptographic commitments. However, a significant challenge has been the reliance of these schemes on homomorphic commitments, a property not inherent to all commitments and potentially vulnerable to future advancements (like quantum computing). Furthermore, the optimal round complexity for computational VSS, especially in synchronous networks, remained an open question, with existing schemes matching the round complexity of unconditional VSS. This paper aims to:

  1. Remove the necessity of homomorphic commitments for computational VSS, relying instead on the basic definitional properties of commitments.
  2. Achieve optimal round complexity for computational VSS, particularly in the synchronous setting, by proving lower bounds and presenting new, more efficient schemes.

Methods

The authors introduce novel VSS schemes by leveraging the fundamental properties of cryptographic commitments, specifically their binding and hiding properties, without requiring homomorphism.

  • Synchronous VSS:
    • They present a 2-round VSS scheme for optimal resilience ($n \ge 2t+1$) using any commitment scheme. This scheme cleverly collapses accusation and resolution rounds from previous 3-round protocols into a single round, achieving a significant improvement. They achieve this by using bivariate polynomials and a novel interaction protocol.
  • They prove a lower bound of 2 rounds for computational VSS in the standard model for $n \ge 2t+1$, demonstrating the optimality of their 2-round scheme.
  • They also present a 1-round VSS scheme for the specific case of $t=1$ and $n \ge 4$, where the dealer is one of the participants.
  • A separate efficient 2-round VSS scheme using homomorphic commitments is also presented, which matches the communication complexity of existing 3-round schemes but requires one less round.
  • Asynchronous VSS:
    • They demonstrate that homomorphism is not necessary for asynchronous VSS either. They adapt existing asynchronous VSS protocols to work with non-homomorphic commitments, maintaining optimal resilience ($n \ge 3t+1$) and comparable communication complexity.
  • They also propose a protocol that achieves the strong commitment property in the asynchronous setting.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Homomorphism is Overrated for VSS: The most significant insight is that the complex homomorphic property of commitments is not a prerequisite for building efficient and secure VSS schemes, especially in the computational setting. This opens up VSS construction to a wider range of cryptographic primitives.
  • Optimal Round Complexity Achieved: The paper establishes that 2 rounds are both necessary and sufficient for computational VSS in the synchronous setting with optimal resilience ($n \ge 2t+1$), a significant improvement over previous schemes that required 3 rounds.
  • Bridging the Gap with Unconditional VSS: The new computational VSS schemes offer communication complexities that are comparable to or better than unconditional VSS schemes, making them a more practical choice for many applications.
  • Bivariate Polynomials as a Tool: The use of bivariate polynomials in the synchronous setting is a key technique that allows for the reduction in rounds without sacrificing security or correctness, especially when dealing with non-homomorphic commitments.

Key Results

  • 2-Round VSS for $n \ge 2t+1$ (Synchronous): A new VSS scheme that requires only 2 rounds for sharing, using any commitment scheme.
  • 1-Round VSS for $t=1, n \ge 4$ (Synchronous): A specialized 1-round scheme for a specific, common scenario.
  • Lower Bound: 2 Rounds Necessary: Proved that 1-round VSS is impossible for $t>1$ and $n \ge 4$, and for $n \le 3t$, establishing 2 rounds as optimal for general cases.
  • Asynchronous VSS without Homomorphism: Demonstrated that asynchronous VSS can be constructed efficiently without relying on homomorphic commitments.
  • Improved Communication Complexity: The proposed schemes offer competitive or superior communication complexity compared to existing unconditional and computational VSS protocols.

Limitations and Future Work

  • Communication Complexity Gap: While the new schemes are efficient, they acknowledge that their communication complexity is still a factor of 'n' higher than protocols using homomorphic commitments. They pose this as an open question: is this gap inevitable?
  • Applications Relying on Homomorphism: Many advanced applications like proactive share renewal, share recovery, and distributed key generation heavily rely on commitment homomorphism. It's an open problem whether these applications can be improved by using VSS schemes that don't require homomorphism, or if expensive zero-knowledge proofs are still needed.
  • Standalone Primitive: The paper treats VSS as a standalone primitive. Exploring its integration into applications like asynchronous Byzantine agreement protocols is suggested.

Summary updated

BibTeX
@article{backes2011computational,
  author = {Michael Backes and Aniket Kate and Arpita Patra},
  title = {{Computational Verifiable Secret Sharing Revisited}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2011},
  url = {https://openreview.net/forum?id=5JDbPYLLUI},
}

Loading related content...

Figure