论文标题
算法中的量子密码学
Quantum Cryptography in Algorithmica
论文作者
论文摘要
我们构造了一个经典的甲骨文，相对于$ \ mathsf {p} = \ mathsf {np} $而又有单拷贝安全pseudorandom量子状态。用Impagliazzo的五个世界的语言，这是“ Algorithmica”中的伪随机状态的构造，因此，即使单向函数不存在，也可以使用基于伪随机状态的量子加密量。结果，我们证明存在一个加密哈希函数的属性，该属性同时（1）足以构造伪andom态，（2）具有随机的Oracle，并且（3）独立于$ \ Mathsf {p} $ vs. $ \ sathsf {np {np {np {np {np {np {np} $。我们还引入了一个猜想，将我们的结果推广到多拷贝安全的伪随机状态。 我们基于Aaronson，Ingram和Kretschmer（CCC 2022）的最新建筑，相对于$ \ Mathsf {p} = \ Mathsf {np} $，但$ \ MATHSF {bqp} \ neq \ neq \ neq \ Mathsf {qcma} $，基于硬度的cipcip of the of the ock，我们的证明还引入了FORRAITATION DESSITUTDER的一个新的离散定义的变体，为此，我们证明了伪随机的$ \ Mathsf {ac^0} $电路。这种变体可能具有独立的兴趣。
We construct a classical oracle relative to which $\mathsf{P} = \mathsf{NP}$ yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo's five worlds, this is a construction of pseudorandom states in "Algorithmica," and hence shows that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist. As a consequence, we demonstrate that there exists a property of a cryptographic hash function that simultaneously (1) suffices to construct pseudorandom states, (2) holds for a random oracle, and (3) is independent of $\mathsf{P}$ vs. $\mathsf{NP}$ in the black-box setting. We also introduce a conjecture that would generalize our results to multi-copy secure pseudorandom states. We build on the recent construction by Aaronson, Ingram, and Kretschmer (CCC 2022) of an oracle relative to which $\mathsf{P} = \mathsf{NP}$ but $\mathsf{BQP} \neq \mathsf{QCMA}$, based on hardness of the OR $\circ$ Forrelation problem. Our proof also introduces a new discretely-defined variant of the Forrelation distribution, for which we prove pseudorandomness against $\mathsf{AC^0}$ circuits. This variant may be of independent interest.
