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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Correlation intractabilityFiat-ShamirBlack-Box Separations
- Contact author(s)
- tamer mour @ weizmann ac il
- History
- 2021-01-18: received
- Short URL
- https://ia.cr/2021/057
- License
-
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}
}
