论文标题
关于量子加密所需的计算硬度
On the computational hardness needed for quantum cryptography
论文作者
论文摘要
在经典的计算模型中，可以很好地确定，单向函数（OWF）对于计算加密术而言是最小的：对于几乎所有在计算无限的对手方面都无法实现的加密应用至关重要。然而，在量子环境中，OWF似乎并不是必不可少的（Kretschmer 2021； Ananth等人，Morimae和Yamakawa 2022），并且是否存在这样的最小原始性的问题仍然开放。 我们认为EFI对 - 有效地采样，统计学上很远，但在计算上无法区分（混合）量子状态。在Yan（2022）的工作的基础上，它显示了EFI对和统计承诺方案之间的等价性，我们表明EFI对对于大量的量子元素应用是必需的。具体而言，我们从最小化版本的承诺方案，遗忘转移和一般安全的多方计算以及$ \ Mathsf {qczk} $证明基本上来自任何非主语言的证据中构建了EFI对。我们还为所有EFI对构建了所有$ \ Mathsf {QIP} $的量子计算零知识（$ \ MATHSF {QCZK} $）。 这表明，对于大部分量子加密，EFI对起着与OWF在经典环境中扮演的角色相似的作用：它们很容易描述，必不可少的，并且还可以用作表现出原始人之间等效性的关键。
In the classical model of computation, it is well established that one-way functions (OWF) are minimal for computational cryptography: They are essential for almost any cryptographic application that cannot be realized with respect to computationally unbounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether such a minimal primitive exists remains open. We consider EFI pairs -- efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states. Building on the work of Yan (2022), which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary for a large class of quantum-cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from $\mathsf{QCZK}$ proofs from essentially any non-trivial language. We also construct quantum computational zero knowledge ($\mathsf{QCZK}$) proofs for all of $\mathsf{QIP}$ from any EFI pair. This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.
