TY - GEN
T1 - Average-case fine-grained hardness
AU - Ball, Marshall
AU - Rosen, Alon
AU - Sabin, Manuel
AU - Vasudevan, Prashant Nalini
N1 - Publisher Copyright:
© 2017 ACM.
PY - 2017/6/19
Y1 - 2017/6/19
N2 - We present functions that can be computed in some fixed 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 fine-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 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) heuris-tically falsifiable in a sense similar to that of (Naor, CRYPTO '03). We prove our hardness results in each case by showing finegrained 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 n2-o(1) time to compute on average, and that of APSP gives us a function that requires n3-o(1) time. Using the same techniques we also obtain a conditional average-case time hierarchy of functions.
AB - We present functions that can be computed in some fixed 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 fine-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 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) heuris-tically falsifiable in a sense similar to that of (Naor, CRYPTO '03). We prove our hardness results in each case by showing finegrained 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 n2-o(1) time to compute on average, and that of APSP gives us a function that requires n3-o(1) time. Using the same techniques we also obtain a conditional average-case time hierarchy of functions.
KW - Average-Case complexity
KW - Cryptography
KW - Fine-grained complexity
KW - Heuristic falsifiability
KW - Proofs of work
KW - Worst-case to average-case reduction
UR - http://www.scopus.com/inward/record.url?scp=85024396195&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85024396195&partnerID=8YFLogxK
U2 - 10.1145/3055399.3055466
DO - 10.1145/3055399.3055466
M3 - Conference contribution
AN - SCOPUS:85024396195
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 483
EP - 496
BT - STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
A2 - McKenzie, Pierre
A2 - King, Valerie
A2 - Hatami, Hamed
PB - Association for Computing Machinery
T2 - 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
Y2 - 19 June 2017 through 23 June 2017
ER -