Average-Case Fine-Grained Hardness
Marshall Ball

Abstract:

We present functions that are hard to compute on average for algorithms running in some fixed polynomial time, assuming widely-conjectured worst-case hardness of certain problems from the study of fine-grained complexity (Orthogonal Vectors, 3SUM, etc). Examples of such functions are known from before (Goldmann et al., Inf. Process. Lett. 1994), but these have been canonical functions that have not found further use than as a proof of this concept, while our functions are closely related to well-studied problems and have considerable algebraic structure.

Based on the average-case hardness of our functions, we outline the construction of a Proof of Work scheme and discuss possible approaches to constructing fine-grained One-Way Functions. We also show how our reductions make conjectures regarding the worst-case hardness of the problems we reduce from (and consequently the Strong Exponential Time Hypothesis) heuristically falsifiable in a sense similar to that of (Naor, CRYPTO 2003).

We prove our hardness results in each case by showing fine-grained reductions from solving one of three problems ? namely, Orthogonal Vectors (OV), 3SUM, and All-Pairs Shortest Paths (APSP) ? in the worst case to computing our function correctly on a uniformly random input.

Based on joint work with Alon Rosen, Manuel Sabin, Prashant Vasudevan.