Paper 2020/258

NIZK from LPN and Trapdoor Hash via Correlation Intractability for Approximable Relations

Zvika Brakerski, Venkata Koppula, and Tamer Mour


We present new non-interactive zero-knowledge argument systems (NIZK), based on standard assumptions that were previously not known to imply it. In particular, we rely on the hardness of both the learning parity with noise (LPN) assumption, and the existence of trapdoor hash functions (TDH, defined by Döttling et al., Crypto 2019). Such TDH can be based on a number of standard assumptions, including DDH, QR, DCR, and LWE. We revisit the correlation intractability (CI) framework for converting $\Sigma$-protocols into NIZK, and present a different strategy for instantiating it by putting together two new components. First, while prior works considered the search-complexity of the relations for which CI is sought,we consider their probabilistic representation. Namely, a distribution over lower-complexity functions that bitwise-computes the target function with all but small (constant) probability. The second component is a new perspective for quantifying the class of relations for which CI is achieved. We show that it is instructive to consider CI for approximable relations (CI-Apx) which is quantified by a class of relations, but requires CI to hold against any approximation of any relation in this class. We show that CI-Apx for just constant-degree polynomials suffices for NIZK, if the under-lying $\Sigma$-protocol is implemented using a suitable commitment scheme. We show that such a commitment scheme can be constructed based on LPN. We then show how to construct CI-Apx for constant-degree polynomials from any suitable TDH (with an enhanced correctness property that is satisfied by all existing TDH constructions).

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2020
Non-interactive Zero KnowledgeCorrelation Intractability
Contact author(s)
zvika brakerski @ weizmann ac il
venkata koppula @ weizmann ac il
tamer mour @ weizmann ac il
2020-07-14: last of 2 revisions
2020-02-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zvika Brakerski and Venkata Koppula and Tamer Mour},
      title = {NIZK from LPN and Trapdoor Hash via Correlation Intractability for Approximable Relations},
      howpublished = {Cryptology ePrint Archive, Paper 2020/258},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.