One-Way Functions vs. TFNP: Simpler and Improved

ePrint Report: One-Way Functions vs. TFNP: Simpler and Improved

Lukáš Folwarczný, Mika Göös, Pavel Hubáček, Gilbert Maystre, Weiqiang Yuan

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 …

box collision eprint report functions gilbert hash hash functions imply report