# On the average-case hardness of total search problems

Kamath Hosdurg C. 2020. On the average-case hardness of total search problems. Institute of Science and Technology Austria.

Download

*Thesis*|

*PhD*|

*Published*|

*English*

Supervisor

Department

Series Title

ISTA Thesis

Abstract

A search problem lies in the complexity class FNP if a solution to the given instance of the problem can be verified efficiently. The complexity class TFNP consists of all search problems in FNP that are total in the sense that a solution is guaranteed to exist. TFNP contains a host of interesting problems from fields such as algorithmic game theory, computational topology, number theory and combinatorics. Since TFNP is a semantic class, it is unlikely to have a complete problem. Instead, one studies its syntactic subclasses which are defined based on the combinatorial principle used to argue totality. Of particular interest is the subclass PPAD, which contains important problems
like computing Nash equilibrium for bimatrix games and computational counterparts of several fixed-point theorems as complete. In the thesis, we undertake the study of averagecase hardness of TFNP, and in particular its subclass PPAD.
Almost nothing was known about average-case hardness of PPAD before a series of recent results showed how to achieve it using a cryptographic primitive called program obfuscation.
However, it is currently not known how to construct program obfuscation from standard cryptographic assumptions. Therefore, it is desirable to relax the assumption under which average-case hardness of PPAD can be shown. In the thesis we take a step in this direction. First, we show that assuming the (average-case) hardness of a numbertheoretic
problem related to factoring of integers, which we call Iterated-Squaring, PPAD is hard-on-average in the random-oracle model. Then we strengthen this result to show that the average-case hardness of PPAD reduces to the (adaptive) soundness of the Fiat-Shamir Transform, a well-known technique used to compile a public-coin interactive protocol into a non-interactive one. As a corollary, we obtain average-case hardness for PPAD in the random-oracle model assuming the worst-case hardness of #SAT. Moreover, the above results can all be strengthened to obtain average-case hardness for the class CLS ⊆ PPAD.
Our main technical contribution is constructing incrementally-verifiable procedures for computing Iterated-Squaring and #SAT. By incrementally-verifiable, we mean that every intermediate state of the computation includes a proof of its correctness, and the proof can be updated and verified in polynomial time. Previous constructions of such procedures relied on strong, non-standard assumptions. Instead, we introduce a technique called recursive proof-merging to obtain the same from weaker assumptions.

Publishing Year

Date Published

2020-05-25

Page

126

ISSN

IST-REx-ID

### Cite this

Kamath Hosdurg C. On the average-case hardness of total search problems. 2020. doi:10.15479/AT:ISTA:7896

Kamath Hosdurg, C. (2020).

*On the average-case hardness of total search problems*. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7896Kamath Hosdurg, Chethan. “On the Average-Case Hardness of Total Search Problems.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7896.

C. Kamath Hosdurg, “On the average-case hardness of total search problems,” Institute of Science and Technology Austria, 2020.

Kamath Hosdurg, Chethan.

*On the Average-Case Hardness of Total Search Problems*. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7896.**All files available under the following license(s):**

**Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):**

**Main File(s)**

File Name

2020_Thesis_Kamath.pdf
1.62 MB

Access Level

Open Access

Date Uploaded

2020-05-26

MD5 Checksum

b39e2e1c376f5819b823fb7077491c64

**Source File**

File Name

Thesis_Kamath.zip
15.30 MB

Access Level

Closed Access

Date Uploaded

2020-05-26

MD5 Checksum

8b26ba729c1a85ac6bea775f5d73cdc7

**Material in ISTA:**

**Part of this Dissertation**