CISPA
Browse
LIPIcs.ITCS.2024.40.pdf (1.06 MB)

On the Black-Box Complexity of Correlation Intractability.

Download (1.06 MB)
conference contribution
posted on 2024-05-22, 12:25 authored by Nico DöttlingNico Döttling, Tamer Mour
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.

History

Editor

Guruswami V

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

Innovations in Theoretical Computer Science (ITCS)

Journal

ITCS

Volume

287

Page Range

40:1-40:1

Publisher

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

BibTeX

@conference{Döttling:Mour:2024, title = "On the Black-Box Complexity of Correlation Intractability.", author = "Döttling, Nico" AND "Mour, Tamer", editor = "Guruswami, Venkatesan", year = 2024, month = 1, journal = "ITCS", pages = "40:1--40:1", publisher = "Schloss Dagstuhl - Leibniz-Zentrum für Informatik" }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC