Quantum All-Subkeys-Recovery Attacks on 6-round Feistel-2* Structure Based on Multi-Equations Quantum Claw Finding

• URL: http://arxiv.org/abs/2309.13548v1
• Date: Sun, 24 Sep 2023 04:40:48 GMT
• Title: Quantum All-Subkeys-Recovery Attacks on 6-round Feistel-2* Structure Based on Multi-Equations Quantum Claw Finding
• Authors: Wenjie Liu, Mengting Wang and Zixian Li
• Abstract summary: We propose a quantum all-subkeys-recovery (ASR) attack based on multi-equations quantum claw-finding. It only requires 3 plain-ciphertext pairs to quickly crack the 6-round Feistel-2* structure.
• Score: 3.845166861382186
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Exploiting quantum mechanisms, quantum attacks have the potential ability to break the cipher structure. Recently, Ito et al. proposed a quantum attack on Feistel-2* structure (Ito et al.'s attack) based onthe Q2 model. However, it is not realistic since the quantum oracle needs to be accessed by the adversary, and the data complexityis high. To solve this problem, a quantum all-subkeys-recovery (ASR) attack based on multi-equations quantum claw-finding is proposed, which takes a more realistic model, the Q1 model, as the scenario, and only requires 3 plain-ciphertext pairs to quickly crack the 6-round Feistel-2* structure. First, we proposed a multi-equations quantum claw-finding algorithm to solve the claw problem of finding multiple equations. In addition, Grover's algorithm is used to speedup the rest subkeys recovery. Compared with Ito et al.'s attack, the data complexity of our attack is reduced from O(2^n) to O(1), while the time complexity and memory complexity are also significantly reduced.

Related papers

• Quantum Key-Recovery Attacks on FBC Algorithm [2.2002244657481826]
  We present a comprehensive security analysis of the FBC quantum adversaries with different query capabilities.<n>Considering an adversary with classical queries and quantum computing capabilities, we demonstrate low-data quantum key-recovery attacks on FBC-KF/FK structures.
  arXiv  Detail & Related papers  (2025-08-01T09:08:53Z)
• Quantum Security Analysis of the Key-Alternating Ciphers [2.5383384004287937]
  We study the security of key-alternating ciphers (KAC), a generalization of Even-Mansour ciphers over multiple rounds. We introduce the first nontrivial quantum key-recovery attack on multi-round KAC in a model where the adversary has quantum access to only one of the public permutations.
  arXiv  Detail & Related papers  (2024-12-06T13:23:29Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Quantum Query Lower Bounds for Key Recovery Attacks on the Even-Mansour Cipher [0.0]
  Even-Mansour (EM) cipher is one of the famous constructions for a block cipher. Kuwakado and Morii demonstrated that a quantum adversary can recover its $n$-bit secret keys only with $O(n)$ nonadaptive quantum queries.
  arXiv  Detail & Related papers  (2023-08-21T02:01:30Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
  arXiv  Detail & Related papers  (2023-01-05T11:05:22Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• The NISQ Complexity of Collision Finding [2.9405711598281536]
  A fundamental primitive in modern cryptography, collision-resistant hashing ensures there is no efficient way to find inputs that produce the same hash value. Quantum adversaries now require full-scale computers equipped with the power of NISQ. In this paper, we investigate three different models for NISQ algorithms achieve tight bounds for all of them.
  arXiv  Detail & Related papers  (2022-11-23T13:55:28Z)
• Quantum communication complexity of linear regression [0.05076419064097732]
  We show that quantum computers have provable and exponential speedups in terms of communication for some fundamental linear algebra problems. We propose an efficient quantum protocol for quantum singular value transformation.
  arXiv  Detail & Related papers  (2022-10-04T13:27:01Z)
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
  Unitary evolution under a time dependent Hamiltonian is a key component of simulation on quantum hardware. We present an algorithm that compresses the Trotter steps into a single block of quantum gates. This results in a fixed depth time evolution for certain classes of Hamiltonians.
  arXiv  Detail & Related papers  (2021-08-06T19:38:01Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Quantum Key Recovery Attack on SIMON Block Cipher [11.112331561801605]
  We study quantum key recovery attack on SIMON block cipher using Quantum Amplitude Amplification algorithm in Q1 model. We take the quantum attack on 19-round SIMON32/64 for an example and design the quantum circuit of the key recovery process.
  arXiv  Detail & Related papers  (2020-12-12T02:15:47Z)
• Quantum Attacks without Superposition Queries: the Offline Simon's Algorithm [7.819565615098435]
  We introduce a new quantum algorithm which uses Simon's subroutines in a novel way. We obtain improved quantum-time/classical-data tradeoffs with respect to the current literature. We improve some previous superposition attacks by reducing the data complexity.
  arXiv  Detail & Related papers  (2020-02-27T21:05:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.