Non-Interactive Zero-Knowledge Proofs with Fine-Grained Security

We construct the first non-interactive zero-knowledge (NIZK) proof systems in the fine-grained setting where adversaries’ resources are bounded and honest users have no more resources than an adversary. More concretely, our setting is the NC1-fine-grained setting, namely, all parties (including adversaries and honest participants) are in NC1. Our NIZK systems are for circuit satisfiability (SAT) under the worst-case assumption, NC1 being unequal to Parity-L/poly. As technical contributions, we propose two approaches to construct NIZKs in the NC1-fine-grained setting. In stark contrast to the classical Fiat-Shamir transformation, both our approaches start with a simple Sigma protocol and transform it into NIZKs for circuit SAT without random oracles. Additionally, our second approach firstly proposes a fully homomorphic encryption (FHE) scheme in the fine-grained setting, which was not known before, as a building block. Compared with the first approach, the resulting NIZK only supports circuits with constant multiplicative depth, while its proof size is independent of the statement circuit size. Extending our approaches, we obtain two NIZK systems in the uniform reference string model and two non-interactive zaps (namely, non-interactive witness-indistinguishability proof systems in the plain model). While the previous constructions from Ball, Dachman-Soled, and Kulkarni (CRYPTO 2020) require provers to run in polynomial-time, our constructions are the first one with provers in NC1.