Paper 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.

Note: The paper was withdrawn due to a flaw in the proof. We fix the flaw and obtain a slightly different result in ia.cr/2023/1365.

Metadata
Available format(s)
-- withdrawn --
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Correlation intractabilityFiat-ShamirBlack-Box Separations
Contact author(s)
tamer mour @ weizmann ac il
History
2023-09-06: withdrawn
2021-01-18: received
See all versions
Short URL
https://ia.cr/2021/057
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.