Paper 2023/945

One-Way Functions vs. TFNP: Simpler and Improved

Lukáš Folwarczný, Czech Academy of Sciences, Charles University
Mika Göös, École Polytechnique Fédérale de Lausanne
Pavel Hubáček, Czech Academy of Sciences, Charles University
Gilbert Maystre, École Polytechnique Fédérale de Lausanne
Weiqiang Yuan, École Polytechnique Fédérale de Lausanne
Abstract

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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2023/945}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.