On Basing One-way Permutations on NP-hard Problems under Quantum Reductions
On Basing One-way Permutations on NP-hard Problems under Quantum Reductions
复制标题
DOI：
10.22331/q-2020-08-27-312
复制
发表时间：
2018-04
期刊：
影响因子：
6.4
通讯作者：
Nai-Hui Chia;Sean Hallgren;F. Song
中科院分区：
文献类型：
--
作者：
Nai-Hui Chia;Sean Hallgren;F. Song
复杂性理论的一个基本追求是将最坏情况的问题简化为平均情况的问题。存在诸如PSPACE之类的复杂性类，它们允许从最坏情况到平均情况的简化。然而，对于许多其他类，如NP，到目前为止的证据通常是否定的，在这个意义上，这种减少的存在将导致多项式层次（PH）的崩溃。基于密码原语，例如，逆单向置换在NP完全性上的平均情况困难性是一个特别有趣的例子。由于有证据表明，从NP难问题到打破这些原语的经典约简导致PH崩溃，因此似乎不太可能将密码原语建立在NP难问题上。然而，这些结果并不排除量子约化存在的可能性。在这项工作中，我们开始研究这些问题的量子类似物。除了形式化量子约化的基本概念和通过分离的例子展示量子约化的能力之外，我们的主要结果表明，如果NP完全问题使用某些类型的量子约化为逆单向排列，则NP完全问题是QIP（2）。
A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to average-case reductions. However, for many other classes such as NP, the evidence so far is typically negative, in the sense that the existence of such reductions would cause collapses of the polynomial hierarchy(PH). Basing cryptographic primitives, e.g., the average-case hardness of inverting one-way permutations, on NP-completeness is a particularly intriguing instance. As there is evidence showing that classical reductions from NP-hard problems to breaking these primitives result in PH collapses, it seems unlikely to base cryptographic primitives on NP-hard problems. Nevertheless, these results do not rule out the possibilities of the existence of quantum reductions. In this work, we initiate a study of the quantum analogues of these questions. Aside from formalizing basic notions of quantum reductions and demonstrating powers of quantum reductions by examples of separations, our main result shows that if NP-complete problems reduce to inverting one-way permutations using certain types of quantum reductions, thencoNP⊆QIP(2).