2026-08-08T20:28:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19568 2024-03-06T11:04:21Z ddc:004 open_access

On the Black-Box Complexity of Correlation Intractability Döttling, Nico Mour, Tamer Correlation Intractability Fiat-Shamir Black-box Complexity Black-box Separations 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 correlation intractable for a class of relations ℛ if, for any relation R ∈ ℛ, it is hard given a random hash function h ← H to find an input z s.t. (z,h(z)) ∈ 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 Ω(t) invocations of the underlying building block. We see this as a first step in developing a methodology towards broader lower bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nico Döttling and Tamer Mour 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.40 urn:nbn:de:0030-drops-195683 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.40 eng https://creativecommons.org/licenses/by/4.0/legalcode