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

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Correlation intractabilityFiat-ShamirBlack-Box Separations
Contact author(s)
tamer mour @ weizmann ac il
History
Short URL
https://ia.cr/2021/057

CC BY

BibTeX

@misc{cryptoeprint:2021/057,
author = {Tamer Mour},
title = {Correlation Intractability vs. One-wayness},
howpublished = {Cryptology ePrint Archive, Paper 2021/057},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/057}},
url = {https://eprint.iacr.org/2021/057}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.