Computational Indistinguishability Between Quantum States and Its Cryptographic Application
Computational Indistinguishability Between Quantum States and Its Cryptographic Application
复制标题
DOI：
10.1007/s00145-011-9103-4
复制
发表时间：
2012-07-01
影响因子：
3
通讯作者：
Yamakami, Tomoyuki
中科院分区：
文献类型：
--
作者：
Kawachi, Akinori;Koshiba, Takeshi;Yamakami, Tomoyuki
我们引入了区分两个特定量子态的计算问题作为一个新的密码问题来设计一个对任何多项式时间量子对手都是“安全的”的量子密码方案。我们的问题，QSCD(Ff)，是区分有限次对称群上具有隐藏置换的两类随机陪集态。这自然地推广了计算密码学中常用的两个概率分布之间的区分问题。作为我们的主要贡献，我们证明了QSCD(Ff)具有三个重要的密码学性质：(I)QSCD(Ff)有陷门；(Ii)QSCD(Ff)的平均情况下的硬度与其最坏情况下的硬度重合；(Iii)在最坏情况下，QSCD(Ff)的计算难度至少与图自同构问题相同。这些密码学性质使我们能够构造一个量子公钥密码系统，它很可能抵抗多项式时间量子对手的任何选择的明文攻击。我们进一步讨论了QSCD(Ff)的推广，称为QSCD(Cyc)，并介绍了一种依赖于QSCD(Cyc)相似密码学性质的多比特加密方案。
We introduce a computational problem of distinguishing between two specific quantum states as a new cryptographic problem to design a quantum cryptographic scheme that is "secure" against any polynomial-time quantum adversary. Our problem, QSCD(ff), is to distinguish between two types of random coset states with a hidden permutation over the symmetric group of finite degree. This naturally generalizes the commonly-used distinction problem between two probability distributions in computational cryptography. As our major contribution, we show that QSCD(ff) has three properties of cryptographic interest: (i) QSCD(ff) has a trapdoor; (ii) the average-case hardness of QSCD(ff) coincides with its worst-case hardness; and (iii) QSCD(ff) is computationally at least as hard as the graph automorphism problem in the worst case. These cryptographic properties enable us to construct a quantum public-key cryptosystem which is likely to withstand any chosen plaintext attack of a polynomial-time quantum adversary. We further discuss a generalization of QSCD(ff), called QSCD(cyc), and introduce a multi-bit encryption scheme that relies on similar cryptographic properties of QSCD(cyc).