One-way functions vs. TFNP: Simpler and improved
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F24%3A00582267" target="_blank" >RIV/67985840:_____/24:00582267 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.4230/LIPIcs.ITCS.2024.50" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.ITCS.2024.50</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.ITCS.2024.50" target="_blank" >10.4230/LIPIcs.ITCS.2024.50</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
One-way functions vs. TFNP: Simpler and improved
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
One-way functions vs. TFNP: Simpler and improved
Popis výsledku anglicky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GX19-27871X" target="_blank" >GX19-27871X: Efektivní aproximační algoritmy a obvodová složitost</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2024
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
ISBN
978-3-95977-309-6
ISSN
—
e-ISSN
—
Počet stran výsledku
14
Strana od-do
50
Název nakladatele
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
Místo vydání
Dagstuhl
Místo konání akce
Berkeley
Datum konání akce
30. 1. 2024
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
001300389400050