Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes
Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes
复制标题
对对称、公钥和基于散列的加密方案的量子密码分析进行基准测试
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
M. Mosca
中科院分区：
文献类型：
--
作者：
Vlad Gheorghiu;M. Mosca
量子算法可以打破基于因子分解和离散对数的密码学，并削弱对称密码学和哈希函数。为了估计这些攻击对现实世界的影响，除了跟踪容错量子计算机的发展之外，重要的是要估计实施这些量子攻击所需的资源。
对于攻击对称加密和哈希函数，一般的量子攻击远不如今天的公钥加密强大。因此，随着量子计算资源的增加，安全性将逐渐降低。目前，由于容错量子纠错的成本，存在大量的资源开销。我们使用量子容错中最先进的方法来估计这种开销。我们使用最先进的优化电路，尽管其实现的进一步改进也会减少实施这些攻击所需的资源。为了限制进一步电路优化的潜在影响，我们提供了成本估计，假设这些功能的实现成本很低。这些数字表明了基于我们今天所知道的（以及对量子硬件的各种假设）的各种对称方案和散列函数的有效比特强度，并确定了应该继续跟踪的各种潜在改进。作为一个例子，我们还研究了比特币的工作量证明系统的影响。
对于许多目前使用的非对称（公钥）密码体制的基础上RSA和椭圆曲线离散型，我们再次提供成本估计的基础上的密码分析，电路编译和量子容错理论的最新进展。例如，这些允许直接比较RSA和椭圆曲线密码术在固定经典位强度下的量子脆弱性。
Quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks.
For attacking symmetric cryptography and hash functions, generic quantum attacks are substantially less powerful than they are for today's public-key cryptography. So security will degrade gradually as quantum computing resources increase. At present, there is a substantial resource overhead due to the cost of fault-tolerant quantum error correction. We provide estimates of this overhead using state-of-the-art methods in quantum fault-tolerance. We use state-of-the-art optimized circuits, though further improvements in their implementation would also reduce the resources needed to implement these attacks. To bound the potential impact of further circuit optimizations we provide cost estimates assuming trivial-cost implementations of these functions. These figures indicate the effective bit-strength of the various symmetric schemes and hash functions based on what we know today (and with various assumptions on the quantum hardware), and frame the various potential improvements that should continue to be tracked. As an example, we also look at the implications for Bitcoin's proof-of-work system.
For many of the currently used asymmetric (public-key) cryptographic schemes based on RSA and elliptic curve discrete logarithms, we again provide cost estimates based on the latest advances in cryptanalysis, circuit compilation and quantum fault-tolerance theory. These allow, for example, a direct comparison of the quantum vulnerability of RSA and elliptic curve cryptography for a fixed classical bit strength.