Practical secure outsourcing computation in complex cloud environments

Abstract

In our research, we propose the first practically deployable construction of a multi-prover zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) protocol specifically tailored for restricted multiplication straight-line (RMS) programs, a computation model widely applicable in evaluating polynomials. Our protocol ensures input privacy, zero-knowledge, and security against fully malicious provers, all while eliminating the need for any inter-prover communication, making it highly suitable for distributed cloud environments. At the core of our approach is the introduction of the Restricted Quadratic Arithmetic Program model, an algebraic structure aligned with RMS semantics that enables provers to independently generate local proofs. We instantiate our framework using the Pinocchio protocol, resulting in a system that requires only 9 group elements per proof and 10 pairings for verification, nearly matching the efficiency of its single-prover counterpart. By leveraging our multi-prover zkSNARK protocol within a multi-server verification computation framework, we enable secure outsourcing of computations to the cloud of fully untrusted cloud servers. Compared to existing works, our protocol uniquely eliminates the need for any inter-server communication while achieving security even against adversaries controlling all servers.