论文标题
三个量子货币计划的密码分析
Cryptanalysis of Three Quantum Money Schemes
论文作者
论文摘要
我们调查了三个公钥量子货币计划背后的安全假设。 Aaronson和Christiano提出了一个基于矢量空间的隐藏子空间$ \ mathbb {f} _2^n $在2012年的计划。佩纳等人在2015年猜想该方案所基于的严重问题可以在Quasi-Polynomial时间中解决。我们通过为潜在问题提供多项式时间量子算法来确认这种猜想。我们的算法基于隐藏子空间中随机点的Zariski切线空间。 Zhandry在2017年提出了一种基于多元哈希功能的方案。我们给出了一种多项式时间量子算法，用于克隆货币状态，概率很高。我们的算法使用该方案的验证电路来产生给定序列号的钞票。 凯恩（Kane），谢里夫（Sharif）和西尔弗堡（Silverberg）在2021年提出了一个基于四元代数的计划。计划中的基本硬问题是克隆一个量子状态，该量子状态代表了一组Hecke运营商的特征向量。我们将多项式时间量子从这个硬问题减少到线性代数问题。后一个问题更容易理解，我们希望我们的减少能为该计划的未来加密货币打开新的途径。
We investigate the security assumptions behind three public-key quantum money schemes. Aaronson and Christiano proposed a scheme based on hidden subspaces of the vector space $\mathbb{F}_2^n$ in 2012. It was conjectured by Pena et al in 2015 that the hard problem underlying the scheme can be solved in quasi-polynomial time. We confirm this conjecture by giving a polynomial time quantum algorithm for the underlying problem. Our algorithm is based on computing the Zariski tangent space of a random point in the hidden subspace. Zhandry proposed a scheme based on multivariate hash functions in 2017. We give a polynomial time quantum algorithm for cloning a money state with high probability. Our algorithm uses the verification circuit of the scheme to produce a banknote from a given serial number. Kane, Sharif and Silverberg proposed a scheme based on quaternion algebras in 2021. The underlying hard problem in their scheme is cloning a quantum state that represents an eigenvector of a set of Hecke operators. We give a polynomial time quantum reduction from this hard problem to a linear algebra problem. The latter problem is much easier to understand, and we hope that our reduction opens new avenues to future cryptanalyses of this scheme.
