Cryptology ePrint Archive: Report 2020/258

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

Zvika Brakerski and Venkata Koppula and Tamer Mour

Abstract: 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).

Category / Keywords: cryptographic protocols / Non-interactive Zero Knowledge, Correlation Intractability

Original Publication (with minor differences): IACR-CRYPTO-2020

Date: received 25 Feb 2020, last revised 14 Jul 2020

Contact author: zvika brakerski at weizmann ac il, venkata koppula@weizmann ac il, tamer mour@weizmann ac il

Available format(s): PDF | BibTeX Citation

Version: 20200714:124129 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]