论文标题
来自陷阱门排列的量子性证明
Proofs of Quantumness from Trapdoor Permutations
论文作者
论文摘要
假设爱丽丝只能执行经典的概率多项式时间计算，而BOB可以进行量子多项式时间计算。爱丽丝（Alice）和鲍勃（Bob）仅通过古典频道进行交流，最后鲍勃获得了一个状态$ | x_0 \ rangle+| x_1 \ rangle $，带有一些弦字符串$ x_0 $和$ x_1 $。爱丽丝是否可以知道$ \ {x_0，x_1 \} $，但鲍勃不能？在某些复杂性假设下，这种任务称为{\ it远程状态准备}确实是可能的，并且是许多量子加密原始词的基础，例如量子性证明，（经典）盲人量子计算，（经典）量子计算的验证和量子货币。实现远程状态准备工作的一种典型技术是使用2-1陷阱碰撞的哈希功能：爱丽丝向鲍勃发送了2比1诱捕的抗碰撞哈希功能$ f $，而鲍勃将其评估并在上位置并测量图像。鲍勃的后计量状态为$ | x_0 \ rangle+| x_1 \ rangle $，其中$ f（x_0）= f（x_1）= y $。使用陷阱门，爱丽丝可以学习$ \ {x_0，x_1 \} $，但由于碰撞电阻，Bob无法。可以利用这种爱丽丝的优势来实现上面列出的量子密码原始图。似乎在这里抵抗碰撞至关重要。 In this paper, surprisingly, we show that the collision resistance is not necessary for a restricted case: we show that (non-verifiable) remote state preparations of $|x_0\rangle+|x_1\rangle$ secure against {\it classical} probabilistic polynomial-time Bob can be constructed from classically-secure (full-domain) trapdoor permutations.陷阱门排列不太可能暗示碰撞阻力，因为已知不可能从抗碰撞的哈希函数到诱捕的哈希函数的黑盒减少。作为结果的应用，我们构建了经典（全域）陷阱门排列的量子性证明。
Assume that Alice can do only classical probabilistic polynomial-time computing while Bob can do quantum polynomial-time computing. Alice and Bob communicate over only classical channels, and finally Bob gets a state $|x_0\rangle+|x_1\rangle$ with some bit strings $x_0$ and $x_1$. Is it possible that Alice can know $\{x_0,x_1\}$ but Bob cannot? Such a task, called {\it remote state preparations}, is indeed possible under some complexity assumptions, and is bases of many quantum cryptographic primitives such as proofs of quantumness, (classical-client) blind quantum computing, (classical) verifications of quantum computing, and quantum money. A typical technique to realize remote state preparations is to use 2-to-1 trapdoor collision resistant hash functions: Alice sends a 2-to-1 trapdoor collision resistant hash function $f$ to Bob, and Bob evaluates it on superposition and measures the image. Bob's post-measurement state is $|x_0\rangle+|x_1\rangle$, where $f(x_0)=f(x_1)=y$. With the trapdoor, Alice can learn $\{x_0,x_1\}$, but due to the collision resistance, Bob cannot. This Alice's advantage can be leveraged to realize the quantum cryptographic primitives listed above. It seems that the collision resistance is essential here. In this paper, surprisingly, we show that the collision resistance is not necessary for a restricted case: we show that (non-verifiable) remote state preparations of $|x_0\rangle+|x_1\rangle$ secure against {\it classical} probabilistic polynomial-time Bob can be constructed from classically-secure (full-domain) trapdoor permutations. Trapdoor permutations are not likely to imply the collision resistance, because black-box reductions from collision-resistant hash functions to trapdoor permutations are known to be impossible. As an application of our result, we construct proofs of quantumness from classically-secure (full-domain) trapdoor permutations.
