Offline Dedicated Quantum Attacks on Block Ciphers Based on Two Parallel Permutation-Based Pseudorandom Functions

• URL: http://arxiv.org/abs/2510.14475v2
• Date: Thu, 23 Oct 2025 07:19:02 GMT
• Title: Offline Dedicated Quantum Attacks on Block Ciphers Based on Two Parallel Permutation-Based Pseudorandom Functions
• Authors: Xiao-Fan Zhen, Zhen-Qiang Li, Jia-Cheng Fan, Su-Juan Qin, Fei Gao,
• Abstract summary: Shi it et al. introduced the dedicated quantum attack on XOR-type function.<n>We propose an offline quantum attack on block ciphers based on TPP-PRFs.<n>Compared to previous results, our offline attack exhibits significantly reduced query complexity.
• Score: 3.9213113404194666
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum cryptanalysis is essential for evaluating the security of cryptographic systems against the threat of quantum computing. Recently, Shi {\it et al.} introduced the dedicated quantum attack on XOR-type function that greatly reduces the required resources (including circuit depth, width, and the number of gates) compared to the parallel Grover-meets-Simon algorithm. Here, our contribution is in two aspects. On the one hand, we discover new cryptographic structures amenable to this attack: PolyMAC and block ciphers based on two parallel permutation-based pseudorandom functions (TPP-PRFs), including XopEM, SoEM22, SUMPIP, and DS-SoEM, partially answering Shi {\it et al.}'s open question. On the other hand, for block ciphers based on TPP-PRFs, we break the obstacle that this attack rely on online query by constructing decoupled XOR-type function, then propose an offline quantum attack on them that retains the tunable truncation parameter, $t$, a positive integer. Compared to previous results, our offline attack exhibits significantly reduced query complexity. Specifically, we reduce the number of queries to the encryption oracle from $\tilde O(2^{(n+t)/2})$ to $ O(2^{t})$ with the same time complexity in the quantum query model, and enable its implementation in the classical query model, optimizing both the classical query complexity and time complexity from $\tilde O(2^{2n/3})$ to $\tilde O(2^{(2n-t)/3})$.

Related papers

• Quantum Meet-in-the-Middle Attacks on Key-Length Extension Constructions [3.767827267403057]
  Key-length extension (KLE) techniques provide a general approach to enhancing the security of block ciphers by using longer keys.<n>This paper presents several quantum meet-in-the-middle (MITM) attacks against two specific KLE constructions.
  arXiv  Detail & Related papers  (2025-11-12T14:03:20Z)
• 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)
• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  Quantum computers will be able to break modern cryptographic systems using Shor's Algorithm.<n>We first examine the McEliece cryptosystem, a code-based scheme believed to be secure against quantum attacks.<n>We then explore NTRU, a lattice-based system grounded in the difficulty of solving the Shortest Vector Problem.
  arXiv  Detail & Related papers  (2025-05-06T03:42:38Z)
• Security of Key-Alternating Ciphers: Quantum Lower Bounds and Quantum Walk Attacks [5.221158079775365]
  We study the quantum security of key-alternating ciphers (KAC)<n>We prove security of the $t$-round KAC against a non-adaptive adversary in both the Q1 and Q2 models.<n>We give the first non-trivial quantum key-recovery algorithm for $t$-round KAC in the Q1 model.
  arXiv  Detail & Related papers  (2024-12-06T13:23:29Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  We introduce a new toolkit for analyzing cloning games.<n>This framework allows us to analyze a new cloning game based on binary phase states.<n>We show that the binary phase variantally optimal bound offers quantitative insights into information scrambling in idealized models of black holes.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms.<n>Intrepid permutations have so far remained a fundamental open problem.<n>We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• 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)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
  arXiv  Detail & Related papers  (2022-05-07T03:15:15Z)
• Beyond quadratic speedups in quantum attacks on symmetric schemes [30.01567358439495]
  We report the first quantum key-recovery attack on a symmetric block cipher design, using classical queries only. Our attack shows that the structure of some symmetric constructions can be exploited to overcome this limit.
  arXiv  Detail & Related papers  (2021-10-06T15:10:31Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• 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.