Paper 2022/548

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

Yuyu Wang and Jiaxin Pan

Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in EUROCRYPT 2022
Keywords
Fine-grained cryptographynon-interactive zero-knowledge prooffully homomorphic encryption
Contact author(s)
wangyuyu @ uestc edu cn
jiaxin pan @ ntnu no
History
2022-05-10: received
Short URL
https://ia.cr/2022/548
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/548,
      author = {Yuyu Wang and Jiaxin Pan},
      title = {Non-Interactive Zero-Knowledge Proofs with Fine-Grained Security},
      howpublished = {Cryptology ePrint Archive, Paper 2022/548},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/548}},
      url = {https://eprint.iacr.org/2022/548}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.