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
[ Cryptology ePrint archive ]