TL;DR
This paper introduces efficient, non-interactive zero-knowledge (NIZK) proof systems designed for scenarios where a single prover needs to convince multiple verifiers simultaneously. They achieve this by developing novel multi-verifier zero-knowledge (MVZK) protocols that are highly scalable and memory-efficient, even for very large circuits.
What Problem Does This Paper Address?
Proving the validity of a computation (like a circuit evaluation) without revealing the underlying secret data is a cornerstone of modern cryptography, known as zero-knowledge (ZK) proofs. While non-interactive ZK (NIZK) proofs are great for proving to many verifiers because the proof can be reused, they can be computationally expensive. On the other hand, designated-verifier ZK (DVZK) proofs are more efficient for a single verifier but don't scale well to many verifiers, as the prover must run a separate protocol with each. This paper tackles the challenge of efficiently proving to multiple verifiers in a non-interactive way, bridging the gap between NIZK and DVZK, especially in settings where a majority of verifiers are honest.
Methods
The authors propose several novel MVZK protocols, primarily focusing on the "honest-majority" setting (where fewer than half the verifiers are malicious). Their core techniques include:
- "Commit-and-Prove" Paradigm: Secrets are committed using linear secret sharing schemes (like Shamir's or packed secret sharing).
- Information-Theoretic Protocols: They first construct a protocol that relies on ideal functionalities (like a coin-tossing service) for efficiency, achieving non-interactivity between the prover and verifiers.
- Fiat-Shamir Transform: To achieve strong non-interactivity (where verifiers only communicate amongst themselves for one round), they adapt the Fiat-Shamir heuristic. This is particularly challenging in the multi-verifier setting because verifiers need to generate a common random challenge without direct interaction, even if some collude with the prover. They develop clever ways to distribute commitments and use random oracles to achieve this.
- Packed Secret Sharing (PSS): For improved communication efficiency, especially when the number of corrupted verifiers is significantly less than half, they leverage PSS. This allows packing multiple secrets into a single sharing, reducing the overall communication overhead.
- Streamable Proofs: A key feature of their protocols is that they are "streamable." This means the prover can generate and send the proof on-the-fly, without needing to store the entire proof in memory. This is crucial for proving very large circuits.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Bridging NIZK and DVZK: The paper demonstrates that by assuming an honest majority of verifiers, it's possible to achieve the benefits of both NIZK (non-interactivity) and DVZK (efficiency) in a multi-verifier setting.
- Scalability through Non-Interactivity: The core innovation is enabling a single prover to efficiently convince many verifiers simultaneously without requiring multiple rounds of interaction between the prover and verifiers.
- Fiat-Shamir in a Distributed Setting: Adapting Fiat-Shamir for multi-verifier proofs, especially when the prover might collude with a subset of verifiers, is a significant technical hurdle. The paper presents a novel approach to overcome this.
- PSS for Communication Efficiency: The use of packed secret sharing is shown to dramatically reduce communication costs, particularly when the corruption threshold is low.
- Streamability for Large Circuits: The streamable nature of the proofs is a practical breakthrough, allowing for the verification of circuits that might otherwise be too large to handle due to memory constraints.
Key Results
The paper presents several MVZK protocols with varying trade-offs:
- Information-Theoretic NIMVZK: Prover sends $1 + o(1)$ field elements per multiplication gate per verifier. Verifiers interact for logarithmic rounds.
- Strong NIMVZK (Computational):
- Using Shamir secret sharing: Prover sends $1/2 + o(1)$ field elements per multiplication gate per verifier. Verifiers communicate for one round.
- Using PSS (for $t < n(1/2 - \epsilon)$): Prover sends $O(1/n)$ field elements per multiplication gate per verifier. Verifiers communicate for one round. This offers significant communication savings.
- Streamable Proofs: All proposed protocols are streamable, meaning memory usage is proportional to evaluating the circuit in the clear.
- Asymmetric Communication: For some protocols, a subset of verifiers can have sublinear communication complexity, making them suitable for heterogeneous environments (e.g., powerful servers and less powerful mobile devices).
Limitations and Future Work
- Honest Majority Assumption: The primary limitation is the reliance on the honest-majority assumption ($t < n/2$). The protocols are not designed for settings where a majority of verifiers can be corrupted.
- Random Oracle Model: Some protocols rely on the random oracle model, which is a standard cryptographic assumption but not strictly "real-world."
- Future Work: The authors suggest exploring MVZK protocols for different settings, such as those without the honest-majority assumption, and further optimizing communication and computation costs. They also highlight the potential for their protocols to be used in applications like honest-majority MPC with input predicate checks and private aggregation systems.
Summary updated