Time–space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2
Time–space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2
复制标题
DOI：
10.1007/s11128-018-2107-3
复制
发表时间：
2018-05
影响因子：
2.5
通讯作者：
Panjin Kim;Daewan Han;Kyung Chul Jeong
中科院分区：
文献类型：
--
作者：
Panjin Kim;Daewan Han;Kyung Chul Jeong
密码分析量子搜索算法的性能主要是从查询复杂度推断出来的，查询复杂度隐藏了由实现引起的开销。为了揭示去除隐藏因素的定量复杂性分析，我们提供了一个估计时空复杂性的框架，仔细考虑目标密码函数的特性。考虑了处理器和电路的并行化方法，得到了深度和量子比特的时空折衷曲线。该方法指导如何按照效率对不同的电路设计进行排序。该框架适用于代表性的密码系统NIST称为安全参数的指导方针，重新评估AES和SHA-2的安全强度。
Performance of cryptanalytic quantum search algorithms is mainly inferred fromquerycomplexity which hides overhead induced by an implementation. To shed light on quantitative complexity analysis removing hidden factors, we provide a framework for estimating time–space complexity, with carefully accounting for characteristics of target cryptographic functions. Processor and circuit parallelization methods are taken into account, resulting in the time–space trade-off curves in terms ofdepthandqubit. The method guides how to rank different circuit designs in order of their efficiency. The framework is applied to representative cryptosystems NIST referred to as a guideline for security parameters, reassessing the security strengths of AES and SHA-2.