New Techniques for Proving Fine-Grained Average-Case Hardness

The recent emergence of fine-grained cryptography strongly motivates developing an average-case analogue of Fine-Grained Complexity (FGC). Prior work [Goldreich-Rothblum 2018, Boix-Adserà et al. 2019, Ball et al. 2017] developed worst-case to average-case fine-grained reductions (WCtoACFG) for certain algebraic and counting problems over natural distributions and used them to obtain a limited set of cryptographic primitives. To obtain stronger cryptographic primitives based on standard FGC assumptions, ideally, one would like to develop WCtoACFG reductions from the core hard problems of FGC, Orthogonal Vectors (OV), CNF-SAT, 3SUM, All-Pairs Shortest Paths (APSP) and zero- k clique. Unfortunately, it is unclear whether these problems actually are hard for any natural distribution. It is known, that e.g. OV can be solved quickly for very natural distributions [Kane-Williams 2019], and in this paper we show that even counting the number of OV pairs on average has a fast algorithm. This paper defines new versions of OV, kSUM and zero- k-clique that are both worst-case and average-case fine-grained hard assuming the core hypotheses of FGC. We then use these as a basis for fine-grained hardness and average-case hardness of other problems. The new problems represent their inputs in a certain “factored” form. We call them “factored”-OV, “factored”-zero- k-clique and “factored”-3SUM. We show that factored- k-OV and factored kSUM are equivalent and are complete for a class of problems defined over Boolean functions. Factored zero- k-clique is also complete, for a different class of problems. Our hard factored problems are also simple enough that we can reduce them to many other problems, e.g. to edit distance, k-LCS and versions of Max-Flow. We further consider counting variants of the factored problems and give WCtoACFG reductions for them for a natural distribution. Through FGC reductions we then get average-case hardness for well-studied problems like regular expression matching from standard worst-case FGC assumptions. To obtain our WCtoACFG reductions, we formalize the framework of [Boix-Adserà et al. 2019] that was used to give a WCtoACFG reduction for counting k-cliques. We define an explicit property of problems such that if a problem has that property one can use the framework on the problem to get a WCtoACFG self reduction. We then use the framework to slightly extend Bolx-Adserà et al.'s average-case counting k-cliques result to average-case hardness for counting arbitrary subgraph patterns of constant size in -partite graphs. The fine-grained public-key encryption scheme of [LaVigne et al.'20] is based on an average-case hardness hypothesis for the decision problem, zero- k-clique, and the known techniques for building such schemes break down for algebraic/counting problems. Meanwhile, the WCtoACFG reductions so far have only been for counting problems. To bridge this gap, we show that for a natural distribution, an algorithm that detects a zero- k-clique with high enough probability also implies an algorithm that can count zero- k-cliques with high probability. This gives hope that the FGC cryptoscheme of [LaVigne et al.'20] can be based on standard FGC assumptions.