New Techniques for Proving Fine-Grained Average-Case Hardness
New Techniques for Proving Fine-Grained Average-Case Hardness
复制标题
证明细粒度平均表面硬度的新技术
DOI：
10.1109/focs46700.2020.00077
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Williams, Virginia Vassilevska
中科院分区：
文献类型：
--
作者：
Dalirrooyfard, Mina;Lincoln, Andrea;Williams, Virginia Vassilevska
最近细粒度密码学的出现强烈地推动了开发细粒度复杂性（FGC）的平均情况模拟。先前的工作[Goldreich-Rothblum 2018，Boix-Adserà et al. 2019，Ball et al. 2017]为自然分布上的某些代数和计数问题开发了最坏情况到平均情况的细粒度约简（WCtoACFG），并使用它们来获得有限的加密原语集。为了获得基于标准FGC假设的更强的密码原语，理想地，人们希望从FGC、正交向量（OV）、CNF-SAT、3SUM、所有对最短路径（APSP）和零k团的核心硬问题开发WCtoACFG约简。不幸的是，目前尚不清楚这些问题对于任何自然分布来说是否真的很困难。众所周知，例如OV可以快速求解非常自然的分布[Kane-Williams 2019]，在本文中，我们证明了即使平均计算OV对的数量也有一个快速算法。本文定义了新版本的OV，kSUM和零k团，这是最坏情况下和平均情况下细粒度硬假设FGC的核心假设。然后，我们使用这些作为细粒度硬度和其他问题的平均硬度的基础。新的问题以某种“因素化”的形式代表他们的投入。我们称它们为“因子化”-OV、“因子化”-zero-k-clique和“因子化”-3SUM。我们发现，因子k-OV和因子kSUM是等价的，是完整的一类问题定义的布尔函数。对于不同类型的问题，因子化的零k团也是完备的。我们的硬分解问题也足够简单，我们可以将它们简化为许多其他问题，例如编辑距离，k-LCS和Max-Flow的版本。我们进一步考虑计算因子化问题的变体，并为它们提供自然分布的WCtoACFG减少。通过FGC约简，我们可以从标准的最坏情况FGC假设中得到正则表达式匹配等研究充分的问题的平均情况硬度。为了获得我们的WCtoACFG约简，我们将[Boix-Adserà et al. 2019]的框架形式化，该框架用于给出用于计数k团的WCtoACFG约简。我们定义了一个明确的属性的问题，这样，如果一个问题的属性，可以使用的框架上的问题，以获得WCtoACFG自我减少。然后，我们使用的框架略有扩展Bolx-Adserà等人。的平均情况计数k-团的结果，平均情况的困难计数的任意子图模式的常数大小的部图。[LaVigne et al. '20]是基于用于决策问题零k团的平均情况硬度假设，并且用于构建这种方案的已知技术对于代数/计数问题而言是崩溃的。与此同时，到目前为止，WCtoACFG的削减只是因为计数问题。为了弥合这一差距，我们表明，对于一个自然分布，一个算法，检测到一个零k-团具有足够高的概率也意味着一个算法，可以计数零k-团具有高概率。这给了[LaVigne et al. 20]可以基于标准FGC假设。
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.
登录
查看更多内容
最大流问题和边标记图的 NP 完全变体
DOI：
--
发表时间：
2013
期刊：
影响因子：
--
作者：
Donatella Granata;Raffaele Cerulli;M. Scutellá;A. Raiconi
通讯作者：
A. Raiconi
强次二次时间中的动态时间扭曲：低距离状态和近似评估的算法
DOI：
--
发表时间：
2019
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
William Kuszmaul
通讯作者：
William Kuszmaul
关于算法和复杂性中的一些细粒度问题
DOI：
--
发表时间：
2019
期刊：
International Congress of Mathematicans
影响因子：
--
作者：
V. V. Williams
通讯作者：
V. V. Williams
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
M. Blum;Ryan Williams
通讯作者：
Ryan Williams
DOI：
--
发表时间：
2017
期刊：
Information Technology Convergence and Services
影响因子：
--
作者：
D. Kane;Richard Ryan Williams
通讯作者：
Richard Ryan Williams