Non-Interactive Verifiable Secret Sharing for Monotone Circuits

Ge Bai, Ivan Damgård, Claudio Orlandi, Yu Xia

TL;DR

This paper introduces new, efficient, and non-interactive verifiable secret sharing (VSS) schemes that can handle a broader range of access structures than previous methods. This is achieved by constructing VSS from monotone Boolean circuits, extending previous work that was limited to linear secret sharing schemes.

What Problem Does This Paper Address?

Secret sharing schemes are crucial for securely distributing secrets among multiple parties, ensuring that only authorized subsets can reconstruct the secret. Verifiable secret sharing (VSS) adds a layer of security by allowing parties to verify the integrity of their shares, even if the dealer is malicious. However, existing VSS schemes often require significant interaction or are limited to specific types of access structures (like those representable by linear secret sharing schemes). This paper tackles the challenge of creating VSS schemes that are both non-interactive (minimizing dealer involvement) and capable of supporting a wider class of access structures, specifically those defined by monotone Boolean circuits, while maintaining efficiency.

Methods

The authors build upon a computational secret sharing (CS3) scheme proposed by Vinod et al. [VNS+03] and extend it to achieve verifiability. Their core contribution is a "locally verifiable" secret sharing scheme. This scheme uses a novel "tagging" mechanism based on RSA and a homomorphic tagging function. Each player receives a private share and a public "tag" for that share. Players can verify if their private share is consistent with the public tag.

To achieve non-interactivity and public verifiability, they propose two approaches:

  1. Non-Interactive with Complaints: This scheme uses a verifiable opening technique, allowing a player to prove their share is correct if they suspect the dealer cheated.
  2. Non-Interactive and Publicly Verifiable (in the Random Oracle Model): This approach leverages efficient non-interactive zero-knowledge proofs (NIZKs) and a specific encryption scheme (based on ElGamal in the RSA group) to allow anyone to verify the entire sharing process without needing decryption keys.

The construction cleverly uses properties of RSA, homomorphic functions, and symmetric encryption to ensure that the verification process is efficient and does not significantly increase the communication or computational overhead compared to the original non-verifiable scheme.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging the Gap: The paper successfully bridges the gap between monotone Boolean circuits and efficient verifiable secret sharing, a significant extension beyond previous work limited to linear secret sharing schemes.
  • The Power of Tags: The introduction of deterministic "tags" for private shares, combined with a homomorphic tagging function, is a key innovation. These tags allow for local verification without revealing the secret itself.
  • Commutativity is Key: The clever use of encryption schemes and tagging functions that "commute" is crucial for proving the correctness and verifiability of the scheme, especially when dealing with complex circuit structures.
  • Efficiency without Generic ZK: The authors demonstrate how to achieve efficient VSS without resorting to generic zero-knowledge techniques, which often incur prohibitive overhead.

Key Results

The paper presents two main VSS protocols:

  • A non-interactive with complaints scheme.
  • A non-interactive and publicly verifiable scheme (in the random oracle model).

Both schemes are computationally secure and efficient, with communication complexity that depends on the circuit size and fan-out, but not on the complexity of the dealer's computation itself. They efficiently handle access structures that were previously intractable for efficient VSS constructions.

Limitations and Future Work

  • Random Oracle Model: One of the proposed schemes relies on the random oracle model, which is a theoretical construct. Future work could aim to remove this assumption for practical implementations.
  • RSA Assumption: The security of the schemes relies on the hardness of the RSA problem.
  • Efficiency of Fanout Gates: While the schemes handle fanout gates, the proof of privacy involves a complex reduction that decomposes the circuit to remove fanout gates, suggesting potential areas for further optimization.
  • Asynchronous Environments: While the paper aims for non-interactivity, the "non-interactive with complaints" scheme still requires a broadcast channel for complaints, hinting at further research into truly asynchronous VSS.

Summary updated

BibTeX
@article{bai2016non,
  author = {Ge Bai and Ivan Damgård and Claudio Orlandi and Yu Xia},
  title = {{Non-Interactive Verifiable Secret Sharing for Monotone Circuits}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2016},
  url = {https://openreview.net/forum?id=nOClb8OJWkc},
}

Loading related content...

Figure