Paper 2019/1464

New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions and Interaction

Marshall Ball and Dana Dachman-Soled and Mukul Kulkarni

Abstract

We investigate the minimal assumptions necessary for minimal interaction zero-knowledge type primitives—ZAPs (two-round, public coin, witness indistinguishable proofs), NIWI (non-interactive witness indistinguishable proofs) and NIZK (non-interactive zero-knowledge proofs)—in the standard (no trusted setup) model. Since our goal is to obtain constructions from Minicrypt and/or worst-case assumptions only, we consider the setting where the prover is computationally more powerful than the simulator/zero-knowledge distinguisher. This covers both the traditional setting of computationally unbounded provers, as well as a new “fine-grained” setting that we introduce, where the prover is polynomial time and the verifier/simulator/zero-knowledge adversary are in a lower complexity class, such as NC1. We present constructions of ZAPs and NIWI for AM from Minicrypt and worst-case assumptions. We also present (a form of) NIZK with uniform soundness for NP, from Minicrypt and worst-case assumptions. We present analogous “fine-grained” constructions of all of the above, where the zero- knowledge adversary is limited to NC1. Specifically, we achieve “fine-grained” ZAPs and NIWI for NP from worst-case assumptions only and achieve a form of “fine-grained” NIZK with uniform soundness for NP from worst-case and Minicrypt assumptions.