<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T04:15:15Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/24136" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/24136</identifier><datestamp>2026-08-31T17:19:31Z</datestamp><setSpec>com_10012_1</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author">Ibrahim, Anas</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2026-08-31T17:19:31Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2026-08-31</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2026-08-27</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/10012/24136</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="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.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject">TFNP</dim:field>
   <dim:field mdschema="dc" element="subject">One-Way Functions</dim:field>
   <dim:field mdschema="dc" element="subject">Black-Box Reductions</dim:field>
   <dim:field mdschema="dc" element="title">On the Black-Box Impossibility of Hardness in TFNP from One-Way Functions</dim:field>
   <dim:field mdschema="dc" element="type">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department">David R. Cheriton School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline">Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree">Master of Mathematics</dim:field>
   <dim:field mdschema="uws-etd" element="embargo" qualifier="terms">0</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Hajiabadi, Mohammad</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>