Welcome to the resource topic for 2024/1806
Title:
Encrypted RAM Delegation: Applications to Rate-1 Extractable Arguments, Homomorphic NIZKs, MPC, and more
Authors: Abtin Afshar, Jiaqi Cheng, Rishab Goyal, Aayush Yadav, Saikumar Yadugiri
Abstract:In this paper we introduce the notion of encrypted RAM delegation. In an encrypted RAM delegation scheme, the prover creates a succinct proof for a group of two input strings x_\mathsf{pb} and x_\mathsf{pr}, where x_\mathsf{pb} corresponds to a large \emph{public} input and x_\mathsf{pr} is a \emph{private} input. A verifier can check correctness of computation of \mathcal{M} on (x_\mathsf{pb}, x_\mathsf{pr}), given only the proof \pi and x_\mathsf{pb}.
We design encrypted RAM delegation schemes from a variety of standard assumptions such as DDH, or LWE, or k-linear. We prove strong knowledge soundness guarantee for our scheme as well as a special input hiding property to ensure that \pi does not leak anything about x_\mathsf{pr}.
We follow this by describing multiple applications of encrypted RAM delegation. First, we show how to design a rate-1 non-interactive zero-knowledge (NIZK) argument system with a straight-line extractor. Despite over 30+ years of research, the only known construction in the literature for rate-1 NIZKs from standard assumptions relied on fully homomorphic encryption. Thus, we provide the first rate-1 NIZK scheme based purely on DDH or k-linear assumptions.
Next, we also design fully-homomorphic NIZKs from encrypted RAM delegation. The only prior solution crucially relied on algebraic properties of pairing-based NIZKs, thus was only known from the decision linear assumption. We provide the first fully-homomorphic NIZK system from LWE (thus post-quantum security) and from DDH-hard groups.
We also provide a communication-complexity-preserving compiler for a wide class of semi-malicious multiparty computation (MPC) protocols to obtain fully malicious MPC protocols. This gives the first such compiler for a wide class of MPC protocols as any comparable compiler provided in prior works relied on strong non-falsifiable assumptions such as zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs). Moreover, we also show many other applications to composable zero-knowledge batch arguments, succinct delegation of committed programs, and fully context-hiding multi-key multi-hop homomorphic signatures.
ePrint: https://eprint.iacr.org/2024/1806
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .