Time-Space Complexity of Quantum Search Algorithms in Symmetric Cryptanalysis

Abstract

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.

References in corpus (19)

• Quantum Mechanics helps in searching for a needle in a haystack
• Elementary gates for quantum computation
• Surface codes: Towards practical large-scale quantum computation
• Efficient classical simulation of slightly entangled quantum computations
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Quantum Amplitude Amplification and Estimation
• A Quantum Random Walk Search Algorithm
• Tight bounds on quantum searching
• Spatial search by quantum walk
• Grover's quantum searching algorithm is optimal
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Magic state distillation with low overhead
• Quantum Algorithm for the Collision Problem
• Fixed-point quantum search with an optimal number of queries
• Quantum computation with realistic magic state factories
• Multilevel distillation of magic states for quantum computing
• On the robustness of bucket brigade quantum RAM
• A Depth-Optimal Canonical Form for Single-qubit Quantum Circuits

Cited by in corpus (9)

• Depth optimization of quantum search algorithms beyond Grover's algorithm
• A Co-Design Framework of Neural Networks and Quantum Circuits Towards Quantum Advantage
• Implementation of efficient quantum search algorithms on NISQ computers
• A quantum circuit design of AES
• Quantum search on noisy intermediate-scale quantum devices
• Deploying hybrid quantum-secured infrastructure for applications: When quantum and post-quantum can work together
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition
• Asymptotic bounds on quantum partial search algorithm and its applications to parallel search
• Resource Constraint Estimation of In-Quantum Implementated Mini-AES