TL;DR
This paper introduces efficient, non-interactive verifiable secret sharing (VSS) schemes that can handle a broader range of access structures than previous methods. They achieve this by building 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 groups 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, constructing VSS schemes that are both efficient (avoiding generic zero-knowledge techniques) and non-interactive (requiring minimal communication from the dealer) for arbitrary access structures has been a significant challenge. Previous efficient constructions were limited to access structures representable by linear secret sharing schemes (LSSS). This paper addresses the gap by enabling efficient and non-interactive VSS for access structures defined by monotone Boolean circuits, which are believed to be a more general class than those handled by LSSS.
Methods
The authors propose two VSS protocols built upon a novel "locally verifiable" secret sharing scheme. This core scheme is based on the standard RSA assumption and uses a "tagging" function that is multiplicatively homomorphic. The verification process involves checking if a party's private share is consistent with a public "tag" associated with it.
The two main protocols are:
- Non-interactive with complaints: This scheme allows parties to detect if they received an incorrect share and to "complain" by revealing their share and a proof. This proof allows others to verify the dealer's misbehavior without revealing the secret.
- Non-interactive and publicly verifiable (in the random oracle model): This more advanced scheme uses non-interactive zero-knowledge proofs (NIZKs) based on the Fiat-Shamir heuristic. This allows anyone to verify the validity of the entire sharing process without needing any private information.
A key technical contribution is the decomposition of circuits with fanout gates into equivalent circuits without fanout gates, simplifying the privacy proof.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Extending Access Structures: The paper significantly broadens the types of access structures that can be handled by efficient and non-interactive VSS schemes, moving beyond LSSS to monotone Boolean circuits. This is a major step towards more flexible and practical VSS.
- Locally Verifiable Secret Sharing: The introduction of a "locally verifiable" secret sharing scheme as a building block is a crucial innovation. This allows individual parties to check their shares against public information, a necessary precursor to global verifiability.
- Tagging for Verification: The use of a homomorphic "tagging" function on shares is a clever way to enable verification without revealing the secret. The verification process essentially checks if the tags of the shares are consistent with the expected output of the circuit.
- Circuit Decomposition for Proofs: The technique of decomposing circuits with fanout gates into simpler circuits without fanout gates is a powerful tool for simplifying and strengthening the privacy proofs.
Key Results
The paper presents two new VSS schemes:
- 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, meaning their complexity is polynomial in the size of the monotone Boolean circuit defining the access structure, and they avoid generic zero-knowledge techniques. The communication complexity is primarily dependent on the circuit's fan-out, not its overall complexity.
Limitations and Future Work
- Random Oracle Model: The publicly verifiable scheme relies on the random oracle model, which is a theoretical construct. Removing this assumption for publicly verifiable schemes would be a significant advancement.
- RSA Assumption: The security of the schemes relies on the hardness of the RSA problem.
- Efficiency for Complex Circuits: While efficient compared to generic methods, the complexity still depends on the circuit size. Further optimizations for very complex circuits might be desirable.
- Asynchronous Environments: While the schemes aim for non-interactivity, the "complaints" mechanism in one scheme implies some level of interaction is needed to resolve disputes. Further work could explore fully asynchronous VSS.
Summary updated