Cryptology ePrint Archive: Report 2021/057

Correlation Intractability vs. One-wayness

Tamer Mour

Abstract: Correlation intractability is an important cryptographic notion that is used for establishing soundness of Fiat-Shamir over public-coin protocols. In this work, we show that symmetric-key cryptography is neither sufficient nor essential for obtaining correlation intractability. Specifically, we prove a bidirectional fully black-box separation between one-way functions (OWFs) and correlation-intractable hash (CIH). In the first direction, we show that CIH for relations as simple as degree-3 polynomials cannot be based solely on OWFs. In the other direction, we show that there exists no fully black-box construction of OWF from CIH for all sparse relations. Consequently, we infer that computationally sound Fiat-Shamir over any specific constant-round proof system does not necessarily require one-way functions.

Category / Keywords: foundations / Correlation intractability, Fiat-Shamir, Black-Box Separations

Date: received 15 Jan 2021

Contact author: tamer mour at weizmann ac il

Available format(s): PDF | BibTeX Citation

Version: 20210118:082156 (All versions of this report)

Short URL: ia.cr/2021/057