论文标题
菲亚特·夏米尔（Fiat-Shamir）的证明也缺乏证据
Fiat-Shamir for Proofs Lacks a Proof Even in the Presence of Shared Entanglement
论文作者
论文摘要
我们探索任意共享物理资源的加密功能。最通用的资源是在每个协议执行时访问新的纠缠量子状态。我们将其称为常见的参考量子状态（CRQ）模型，类似于众所周知的常见参考字符串（CRS）。 CRQ模型是CRS模型的自然概括，但似乎更强大：在两党设置中，CRQ有时可以通过在许多相互无偏见的基础中测量最大纠缠的状态来表现出与随机的Oracle相关的特性。我们将此概念形式化为一个弱的一次性随机Oracle（WoTro），在该$ m $ $ $位输出以在$ n $ bit Input进行调节时，我们只要求$ m $ bit的输出。 我们表明，当$ n-m \inΩ（\ lg n）$时，CRQS模型中WOTRO的任何协议都可以受到（低效率）对手的攻击。此外，我们的对手是有效的模拟，它排除了通过将完全黑盒减少到加密游戏假设来证明方案的计算安全性的可能性。另一方面，我们为哈希函数引入了一个非游戏量子假设，该假设暗示了CRQS模型中的WOTRO（CRQ仅由EPR对组成）。我们首先构建一个统计安全的WOTRO协议，其中$ M = n $，然后哈希输出。 Wotro的不可能带来以下后果。首先，我们显示了量子菲亚特 - 沙米尔变换的完全黑色盒子，从而扩大了Bitansky等人的不可能结果。 （TCC 2013）到CRQS模型。其次，我们显示了量子闪电（Zhandry，eurocrypt 2019）的完全黑色盒子的不可能结果，其中量子螺栓具有一个附加参数，而没有生成新螺栓就无法更改。我们的结果还适用于普通模型中的$ 2 $少女协议。
We explore the cryptographic power of arbitrary shared physical resources. The most general such resource is access to a fresh entangled quantum state at the outset of each protocol execution. We call this the Common Reference Quantum State (CRQS) model, in analogy to the well-known Common Reference String (CRS). The CRQS model is a natural generalization of the CRS model but appears to be more powerful: in the two-party setting, a CRQS can sometimes exhibit properties associated with a Random Oracle queried once by measuring a maximally entangled state in one of many mutually unbiased bases. We formalize this notion as a Weak One-Time Random Oracle (WOTRO), where we only ask of the $m$-bit output to have some randomness when conditioned on the $n$-bit input. We show that when $n-m\inω(\lg n)$, any protocol for WOTRO in the CRQS model can be attacked by an (inefficient) adversary. Moreover, our adversary is efficiently simulatable, which rules out the possibility of proving the computational security of a scheme by a fully black-box reduction to a cryptographic game assumption. On the other hand, we introduce a non-game quantum assumption for hash functions that implies WOTRO in the CRQS model (where the CRQS consists only of EPR pairs). We first build a statistically secure WOTRO protocol where $m=n$, then hash the output. The impossibility of WOTRO has the following consequences. First, we show the fully-black-box impossibility of a quantum Fiat-Shamir transform, extending the impossibility result of Bitansky et al. (TCC 2013) to the CRQS model. Second, we show a fully-black-box impossibility result for a strenghtened version of quantum lightning (Zhandry, Eurocrypt 2019) where quantum bolts have an additional parameter that cannot be changed without generating new bolts. Our results also apply to $2$-message protocols in the plain model.
