TY - GEN

T1 - Average-case fine-grained hardness

AU - Ball, Marshall

AU - Rosen, Alon

AU - Sabin, Manuel

AU - Vasudevan, Prashant Nalini

N1 - Funding Information:
We would like to thank Amir Abboud for suggesting a barrier to achieving low-degree polynomials for EDIT-DISTANCE (Section 2.2) and for pointing us to the Triangle-Collection problem in [7] and a polynomial for it, Shafi Goldwasser for pointing out [54] to us, Tim Roughgarden for clarifications on Remark 5, and Vinod Vaikuntanathan for comments relating to the material in Section 5.3 and Open Question 5. Thanks also to Andrej Bogdanov, Irit Dinur, Ramprasad Saptharishi, Eli-Ben Sasson, Amir Shpilka, and Amnon Ta-Shma for useful discussions. The bulk of this work was performed while the authors were at IDC Herzliya's FACT center and supported by NSF-BSF Cyber Security and Privacy grant #2014/632, ISF grant #1255/12, and by the ERC under the EU's Seventh Framework Programme (FP/2007-2013) ERC Grant Agreement #07952. Marshall Ball is supported in part by the Defense Advanced Research Project Agency (DARPA) and Army Research Office (ARO) under Contract #W911NF-15-C-0236, and NSF grants #CNS-1445424 and #CCF-1423306. Manuel Sabin is also supported by the National Science Foundation Graduate Research Fellowship under Grant #DGE-1106400. Prashant Nalini Vasudevan is also supported by the IBM Thomas J. Watson Research Center (Agreement #4915012803).
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 -