Back to search

University of Waterloo

On the Black-Box Impossibility of Hardness in TFNP from One-Way Functions

Abstract

dc:description.abstract

The complexity class TFNP contains all NP search problems for which a solution is guaranteed to exist for every instance. A proof of totality is needed for every problem in TFNP, so syntactic subclasses (such as PLS, PPA, PPAD, PPP, and PWPP) categorize many problems in TFNP according to the argument needed for totality. Although these subclasses contain many natural complete problems, the status of whether all of TFNP can be solved efficiently remains unknown, especially noting that TFNP is unlikely to have a complete problem. Furthermore, it has been shown that hardness of TFNP cannot be based on P ̸= NP unless NP = coNP. A major line of work has sought to base TFNP hardness on cryptographic assumptions. Existing positive results obtain hardness for subclasses of TFNP from cryptographic primitives such as one-way permutations, collision-resistant hashing, indistinguishability obfuscation, factoring, and various others. However, the status of basing the hardness on a general assumption such as the existence of one-way functions remains unsuccessful. There have been several attempts at providing evidence for this difficulty through blackbox impossibility. Existing barriers rule out either restricted constructions of TFNP problems or restricted classes of reductions. In particular, [RSS16] rules out constructions whose instances have a bounded number of solutions, while [HKKS20, FGH+23] establish impossibility results for reductions satisfying various non-adaptivity and obliviousness restrictions. In this work, we prove a semi-black-box impossibility result under a restriction on the construction: the construction can only query the one-way function once. Subject to this restriction, we allow the reduction to make polynomially many adaptive queries to the solver, as well as adaptive queries to the one-way function.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ibrahim, Anas

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/24136

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ibrahim, Anas. On the Black-Box Impossibility of Hardness in TFNP from One-Way Functions. University of Waterloo, 2026. https://hdl.handle.net/10012/24136