One-way functions vs. TFNP: Simpler and improved

0582267 - MÚ 2025 RIV DE eng C - Conference Paper (international conference)
Folwarczný, Lukáš - Göös, M. - Hubáček, Pavel - Maystre, G. - Yuan, W.
One-way functions vs. TFNP: Simpler and improved.
15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2024 - (Guruswami, V.), č. článku 50. Leibniz International Proceedings in Informatics (LIPIcs), 287. ISBN 978-3-95977-309-6.
[15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Berkeley (US), 30.01.2024-02.02.2024]
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : TFNP * one-way functions * Oracle * Black-Box
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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.
Permanent Link: https://hdl.handle.net/11104/0350366