We present functions that can be computed in some xed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of ne-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., IPL '94), but these have been canonical functions that have not found further use, while our functions are closely related to well-studied problems and have considerable algebraic structure. Based on the average-case hardness and structural properties of our functions, we outline the construction of a Proof of Work scheme and discuss possible approaches to constructing ne-grained OneWay 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 falsi able in a sense similar to that of (Naor, CRYPTO '03). We prove our hardness results in each case by showing negrained 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. The conjectured hardness of OV and 3SUM then gives us functions that require n 2−o (1) time to compute on average, and that of APSP gives us a function that requires n 3−o (1) time. Using the same techniques we also obtain a conditional average-case time hierarchy of functions.
Recently, REF used the polynomial random self-reducibility result in the fine-grained setting in order to construct polynomials that are hard to evaluate on most inputs, assuming fine-grained hardness conjectures for problems such as 3-SUM, Orthogonal-Vectors, and/or All-Pairs-Shortest-Paths.
Average-case fine-grained hardness
STOC 2017
Mathematics Computer Science Materials Science