Welcome to the resource topic for 2023/945
Title:
One-Way Functions vs. TFNP: Simpler and Improved
Authors: Lukáš Folwarczný, Mika Göös, Pavel Hubáček, Gilbert Maystre, Weiqiang Yuan
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.
ePrint: https://eprint.iacr.org/2023/945
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .