Time-Space Complexity of Quantum Search Algorithms in Symmetric Cryptanalysis
This work addresses the need for more accurate complexity analysis in quantum cryptanalysis for security parameter reassessment, though it is incremental as it builds on existing quantum search methods.
The authors tackled the problem of hidden overhead in quantum search algorithms for cryptanalysis by developing a framework to estimate time-space complexity, accounting for cryptographic function characteristics and parallelization, and applied it to reassess the security strengths of AES and SHA-2, showing concrete trade-offs in depth and qubit requirements.
Performance of cryptanalytic quantum search algorithms is mainly inferred from query complexity 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-offs curves in terms of depth and qubit. 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.