Time-space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2
From MaRDI portal
Publication:1993901
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.
Recommendations
- Improvements to quantum search techniques for block-ciphers, with applications to AES
- An efficient quantum collision search algorithm and implications on symmetric cryptography
- Applying Grover's algorithm to AES: quantum resource estimates
- Quantum differential and linear cryptanalysis
- Low-communication parallel quantum multi-target preimage search
Cites work
- A logarithmic-depth quantum carry-lookahead adder
- An \(O(m^2)\)-depth quantum algorithm for the elliptic curve discrete logarithm problem over \(\mathrm{GF}(2^m)^\alpha\)
- An efficient quantum collision search algorithm and implications on symmetric cryptography
- Applying Grover's algorithm to AES: quantum resource estimates
- Asymptotically faster quantum algorithms to solve multivariate quadratic equations
- Both Toffoli and Controlled-NOT need little help to universal quantum computing
- Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3
- scientific article; zbMATH DE number 3692653 (Why is no real title available?)
- scientific article; zbMATH DE number 16479 (Why is no real title available?)
- scientific article; zbMATH DE number 2103524 (Why is no real title available?)
- On the robustness of bucket brigade quantum RAM
- Optimal synthesis of linear reversible circuits
- Parallel collision search with cryptanalytic applications
- Quantum circuits for \(\mathbb F_{2^n}\)-multiplication with subquadratic gate count
- Quantum computation and quantum information. 10th anniversary edition
- Quantum computational networks
- Quantum cryptanalysis of hash and claw-free functions
- Quantum multicollision-finding algorithm
- Quantum resource estimates for computing elliptic curve discrete logarithms
- Quantum reversible circuit of AES-128
- Quantum Walk Algorithm for Element Distinctness
- Solving binary \(\mathcal {MQ}\) with Grover's algorithm
- The Heisenberg representation of quantum computers
- Universal quantum computation with ideal Clifford gates and noisy ancillas
Cited in
(26)- Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3
- Low-communication parallel quantum multi-target preimage search
- Evaluation of Grover's algorithm toward quantum cryptanalysis on ChaCha
- \(T\)-\textit{depth} reduction method for efficient \textit{SHA}-256 quantum circuit construction
- Some efficient quantum circuit implementations of Camellia
- Quantum partial search algorithm with smaller oracles for multiple target items
- New quantum circuit implementations of SM4 and SM3
- Implementing Grover oracles for quantum key search on AES and LowMC
- Quantum search for scaled hash function preimages
- Implementation of efficient quantum search algorithms on NISQ computers
- Quantum circuit implementations of AES with fewer qubits
- Optimization of \(S\)-boxes GOST R 34.12-2015 ``Magma quantum circuits without ancilla qubits
- Quantum circuit implementation and resource analysis of LBlock and LiCi
- Optimized quantum implementation of AES
- MPMCT gate decomposition method reducing T-depth quickly in proportion to the number of work qubits
- Implementing Grover oracle for lightweight block ciphers under depth constraints
- Quantum resource estimation for FSR based symmetric ciphers and related Grover's attacks
- Quantum circuit implementations of SM4 block cipher based on different gate sets
- Further insights on constructing quantum circuits for Camellia block cipher
- Depth-measurement trade-off for quantum search on block ciphers
- Toffoli-depth reduction method preserving in-place quantum circuits and its application to SHA3-256
- Improved quantum circuits for AES: reducing the depth and the number of qubits
- Logarithmic-depth MCT gate implementation method on a given arbitrary number of clean ancillae
- Speeding up Grover's algorithm
- On recovering block cipher secret keys in the cold boot attack setting
- Improvements to quantum search techniques for block-ciphers, with applications to AES
This page was built for publication: Time-space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1993901)
