Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Zero-Knowledge, NIZK, ZAP, NIWI, fine-grained, inefficient prover, minicrypt, derandomization

Date: received 18 Dec 2019

Contact author: marshall at cs columbia edu

Available format(s): PDF | BibTeX Citation

Version: 20191218:195618 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]