Paper 2023/945
One-Way Functions vs. TFNP: Simpler and Improved
, Czech Academy of Sciences, Charles University, Czech Academy of Sciences, Charles University, École Polytechnique Fédérale de Lausanne, École Polytechnique Fédérale de LausanneAbstract
Simon (1998) proved that it is impossible to construct collision-resistant hash functions from one-way functions using a black-box reduction. It is conjectured more generally that one-way functions do not imply, via a black-box reduction, the hardness of any total NP search problem (collision-resistant hash functions being just one such example). We make progress towards this conjecture by ruling out a large class of “single-query” reductions. In particular, we improve over the prior work of Hubáček et al. (2020) in two ways: our result is established via a novel simpler combinatorial technique and applies to a broader class of semi black-box reductions.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- black-box reductionsone-way functionsTFNP
- Contact author(s)
-
folwarczny @ math cas cz
mika goos @ epfl ch
hubacek @ iuuk mff cuni cz
gilbert maystre @ epfl ch
weiqiang yuan @ epfl ch - History
- 2023-06-19: approved
- 2023-06-16: received
- See all versions
- Short URL
- https://ia.cr/2023/945
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/945,
author = {Lukáš Folwarczný and Mika Göös and Pavel Hubáček and Gilbert Maystre and Weiqiang Yuan},
title = {One-Way Functions vs. TFNP: Simpler and Improved},
howpublished = {Cryptology ePrint Archive, Paper 2023/945},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/945}},
url = {https://eprint.iacr.org/2023/945}
}
