Paper 2026/918

Efficient 1-Round MVZK for Dishonest Majority with Superior Online Overhead

Abstract

Zero-knowledge proofs allow to prove a statement while not revealing anything about the witness. In particular, non-interactive zero-knowledge (NIZK) has emerged as the preferred paradigm due to its public verifiability. However, existing NIZK protocols often suffer from high prover overhead for large statements. Conversely, designated-verifier zero-knowledge (DVZK) offers superior prover efficiency and scalability, but is restricted to a single, designated verifier. This leaves a critical gap in scenarios requiring a prover to efficiently convince a group of n verifiers without incurring massive prover overhead of non-interactive systems. To reconcile this, we focus on multi-verifier zero-knowledge (MVZK) protocols, which efficiently prove the same statement to n verifiers simultaneously. MVZK protocols inherit the prominent prover efficiency of DVZK and extend its utility to the multi-party setting. In this work, we propose a highly efficient MVZK protocol in the preprocessing model, secure against a dishonest majority. It tolerates a corrupted prover and up to n-1 corrupted verifiers, where the prover sends only a single message to verifiers, while several prior works require at least two online rounds. Furthermore, compared to the state-of-the-art 1-round protocol by Zhou et al. (PKC 2025), our protocol eliminates the extension-field multiplications from 4n to 0 over any field, achieving superior online efficiency. Experimental results demonstrate that our protocol achieves 9x faster proving and 47x faster verification when evaluating Boolean circuits with 10^4 AND gates.