Welcome to the resource topic for 2023/1365
Title:
On The Black-Box Complexity of Correlation Intractability
Authors: Nico Döttling, Tamer Mour
Abstract:Correlation intractability is an emerging cryptographic paradigm that enabled several recent breakthroughs in establishing soundness of the Fiat-Shamir transform and, consequently, basing non-interactive zero-knowledge proofs and succinct arguments on standard cryptographic assumptions. In a nutshell, a hash family is said to be \emph{correlation intractable} for a class of relations \mathcal{R} if, for any relation R\in\mathcal{R}, it is hard given a random hash function h\gets H to find an input z s.t. (z,h(z))\in R, namely a correlation.
Despite substantial progress in constructing correlation intractable hash functions, all constructions known to date are based on highly-structured hardness assumptions and, further, are of complexity scaling with the circuit complexity of the target relation class.
In this work, we initiate the study of the barriers for building correlation intractability. Our main result is a lower bound on the complexity of any black-box construction of CIH from collision resistant hash (CRH), or one-way permutations (OWP), for any sufficiently expressive relation class. In particular, any such construction for a class of relations with circuit complexity $t$ must make at least $\Omega(t)$ invocations of the underlying building block.
We see this as a first step in developing a methodology towards broader lower bounds.
ePrint: https://eprint.iacr.org/2023/1365
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .