CryptoDB
NIZK from LPN and Trapdoor Hash via Approximate-Correlation Intractability
| Authors: |
|
|---|---|
| Download: |
|
| Conference: | CRYPTO 2020 |
| 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). TDH can be based on a number of standard assumptions, including DDH, QR, DCR, and LWE. We rely on the Correlation Intractability (CI) framework for converting \Sigma-protocols into NIZK, but deviate from prior works in considering CI for searchable relations where the search function has a probabilistic representation by a simple function class (linear or constant degree in our instantiations). Namely, there is a distribution over simple functions that computes each output bit of the search function with all but small (constant) probability. We present a new tool for proving CI for such function classes via a notion that we call Approximate-Correlation Intractability. This notion requires that CI holds even against approximations of a given function class. We show that approximate-correlation intractability for just constant degree functions suffices if the underlying \Sigma-protocol is implemented using an extractable commitment scheme with approximately low-degree extraction, and that such a commitment scheme can be constructed based on LPN. We then show how to construct approximate CI hash functions for this class from any suitable rate-1 TDH (with an enhanced correctness property that is satisfied by all existing constructions). |
Video from CRYPTO 2020
BibTeX
@inproceedings{crypto-2020-30423,
title={NIZK from LPN and Trapdoor Hash via Approximate-Correlation Intractability},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-56877-1_26},
author={Zvika Brakerski and Venkata Koppula and Tamer Mour},
year=2020
}