Quantum Key-Recovery Attacks on FBC Algorithm

• URL: http://arxiv.org/abs/2508.00448v1
• Date: Fri, 01 Aug 2025 09:08:53 GMT
• Title: Quantum Key-Recovery Attacks on FBC Algorithm
• Authors: Yan-Ying Zhu, Bin-Bin Cai, Fei Gao, Song Lin,
• Abstract summary: 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.
• Score: 2.2002244657481826
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: With the advancement of quantum computing, symmetric cryptography faces new challenges from quantum attacks. These attacks are typically classified into two models: Q1 (classical queries) and Q2 (quantum superposition queries). In this context, we present a comprehensive security analysis of the FBC algorithm considering quantum adversaries with different query capabilities. In the Q2 model, we first design 4-round polynomial-time quantum distinguishers for FBC-F and FBC-KF structures, and then perform $r(r>6)$-round quantum key-recovery attacks. Our attacks require $O(2^{(2n(r-6)+3n)/2})$ quantum queries, reducing the time complexity by a factor of $2^{4.5n}$ compared with quantum brute-force search, where $n$ denotes the subkey length. Moreover, we give a new 6-round polynomial-time quantum distinguisher for FBC-FK structure. Based on this, we construct an $r(r>6)$-round quantum key-recovery attack with complexity $O(2^{n(r-6)})$. Considering an adversary with classical queries and quantum computing capabilities, we demonstrate low-data quantum key-recovery attacks on FBC-KF/FK structures in the Q1 model. These attacks require only a constant number of plaintext-ciphertext pairs, then use the Grover algorithm to search the intermediate states, thereby recovering all keys in $O(2^{n/2})$ time.

Related papers

• Quantum Security Analysis of the Key-Alternating Ciphers [2.5383384004287937]
  We study the quantum security of key-alternating ciphers (KAC)<n>We give the first nontrivial quantum key-recovery attack on multi-round KAC in the $Q1$ model.
  arXiv  Detail & Related papers  (2024-12-06T13:23:29Z)
• On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
  lattice-based cryptography is one of the main candidates of post-quantum cryptography.<n> cryptographic security against quantum attackers is based on lattice problems like the shortest vector problem (SVP)<n>Asymptotic quantum speedups for solving SVP are known and rely on Grover's search.
  arXiv  Detail & Related papers  (2024-10-17T16:54:41Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Evaluating Ground State Energies of Chemical Systems with Low-Depth Quantum Circuits and High Accuracy [6.81054341190257]
  We develop an enhanced Variational Quantum Eigensolver (VQE) ansatz based on the Qubit Coupled Cluster (QCC) approach. We evaluate our enhanced QCC ansatz on two distinct quantum hardware, IBM Kolkata and Quantinuum H1-1.
  arXiv  Detail & Related papers  (2024-02-21T17:45:03Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• Quantum All-Subkeys-Recovery Attacks on 6-round Feistel-2* Structure Based on Multi-Equations Quantum Claw Finding [3.845166861382186]
  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.
  arXiv  Detail & Related papers  (2023-09-24T04:40:48Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• 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.