Quantum Circuit Realization and Grover Cryptanalysis of the Hybrid ARX-SPN Cipher GFSPX

This paper presents a qubit-optimized quantum circuit implementation of the lightweight hybrid ARX-SPN cipher GFSPX and evaluates its post-quantum security through a parallelized Grover attack, revealing a total quantum cost of $1.12 \times 2^{159}$ gates that, while below NIST Level 1 thresholds, demonstrates superior resistance compared to other lightweight designs.

The Gist

Imagine you have a very special, lightweight digital lock (called GFSPX) designed to protect data on small devices like smart sensors or RFID tags. This lock is built to be fast and use very little energy, making it perfect for the "Internet of Things."

However, a new kind of "super-tool" called a Quantum Computer is emerging. Unlike regular computers that check keys one by one, a quantum computer can check many keys at once, potentially cracking these locks much faster. This paper asks a simple question: If a quantum computer tries to break this specific lock, how hard will it actually be?

Here is the breakdown of their findings using everyday analogies:

1. The Lock's Design: A Hybrid Engine

The GFSPX lock isn't built with just one type of mechanism. It's a hybrid, like a car that uses both a gas engine and an electric motor.

• The "Gas" Part (ARX): This uses simple math operations (Add, Rotate, XOR) that are very efficient but can be a bit slow at spreading changes through the data.
• The "Electric" Part (SPN): This uses a complex substitution network (like shuffling a deck of cards) that spreads changes very quickly.
• The Result: By combining them, the lock is fast and efficient. The authors built a digital blueprint of this lock specifically for a quantum computer to see exactly how it works inside.

2. The Quantum Blueprint: Building the Circuit

To test the lock, the researchers had to build a "quantum circuit." Think of this as building a miniature, reversible factory where every step can be undone perfectly (so no information is lost).

• The Challenge: Quantum computers are fragile. You can't just copy data around; you have to be very careful with the "qubits" (the quantum bits, like tiny spinning tops).
• The Solution: The researchers optimized the design to use the fewest possible qubits (209 of them). They used a clever trick called a "ripple-carry adder" for the math parts, which is like a very efficient assembly line that doesn't waste space.
• The Footprint: The final blueprint is compact, requiring a "factory floor" of 209 qubits and a specific number of steps (gates) to run one full encryption.

3. The Attack: The "Grover" Search

To break the lock, a quantum computer uses Grover's Algorithm.

• The Analogy: Imagine you have a giant library with $2^{128}$ (a number so huge it's hard to comprehend) books, and only one book has the correct key.
  • A regular computer is like a librarian who checks one book at a time. It would take forever.
  • A quantum computer is like a magical librarian who can check many books simultaneously. It finds the right book in roughly the square root of the time.
• The Trap: To make sure the quantum computer doesn't pick the wrong book (a "false positive"), the researchers made the computer check three different locks (using three different pairs of locked/unlocked messages) at the same time. If a key opens all three, it's definitely the right one.

4. The Verdict: Strong, But Not "Post-Quantum" Proof

The researchers calculated the total "cost" of this quantum attack.

• The Cost: They found that breaking the lock would require a massive amount of computing power, roughly equivalent to $1.12 \times 2^{159}$ operations.
• The Standard: The US National Institute of Standards and Technology (NIST) has set a "safety bar" for the future. To be considered truly safe against quantum computers (Level 1 security), a lock needs a cost of at least $2^{170}$.
• The Result: The GFSPX lock is below the safety bar. It is not safe enough for the strictest post-quantum standards.
  • However, the paper notes that compared to other lightweight locks, GFSPX is actually one of the hardest to break. It sits in a "sweet spot" where it is very efficient for small devices but still offers decent resistance against quantum attacks, even if it doesn't pass the highest security test.

5. The Takeaway

The paper concludes that while this hybrid lock is excellent for current, resource-constrained devices, the 128-bit key size is simply too small to survive a determined quantum attack in the future.

• The Trade-off: You can have a lock that is tiny and fast (good for today's sensors), or a lock that is massive and slow (good for future quantum safety), but this specific design tries to do both and falls slightly short on the "future safety" front.
• Future Advice: To make this design truly quantum-proof, the authors suggest either making the key longer (like 192 or 256 bits) or tweaking the math parts to make them even harder for quantum computers to process.

In short: GFSPX is a very clever, efficient lock that is tougher to crack than most of its peers, but it isn't quite strong enough to withstand the super-powerful quantum computers of the future without some upgrades.

Technical Summary

Technical Summary: Quantum Circuit Realization and Grover Cryptanalysis of the Hybrid ARX-SPN Cipher GFSPX

Problem Statement
The emergence of quantum computing fundamentally challenges the security of classical symmetric-key primitives. While Shor's algorithm threatens public-key cryptography, Grover's algorithm provides a quadratic speedup for unstructured search, effectively halving the security margin of symmetric-key constructions. Consequently, lightweight block ciphers (BCs), designed for resource-constrained environments like the Internet of Things (IoT) and RFID, require a rigorous re-evaluation of their post-quantum resilience. Specifically, there is a need to quantify the quantum resources required to mount a key-recovery attack on hybrid designs that combine Addition-Rotation-XOR (ARX) and Substitution-Permutation Network (SPN) paradigms.

Methodology
The authors present a comprehensive quantum circuit realization and Grover cryptanalysis of GFSPX, a lightweight block cipher featuring a 64-bit data block and a 128-bit secret key. GFSPX utilizes a 4-branch Generalized Feistel Structure (GFS) integrating two distinct functional blocks: an ARX-based function ($F_1$) for non-linearity and a 32-bit SPN structure ($F_2$) for rapid diffusion.

The methodology proceeds in three stages:

1. Quantum Circuit Realization: The classical structure of GFSPX is mapped into a reversible quantum circuit. The authors exploit the inherent reversibility of the Feistel network to minimize ancilla qubit usage.
   • $F_1$ (ARX): Implemented using a compact ripple-carry adder (RCA) based on the Cuccaro et al. architecture. This approach minimizes qubit overhead by omitting the final carry bit for modular addition and utilizing in-place majority (MAJ) and UnMajority-and-Add (UMA) gates.
   • $F_2$ (SPN): The S-box layer (based on PRESENT) is synthesized using a minimal set of CNOT and Toffoli gates without additional ancillae. The permutation layer (P-layer) is implemented via parallelizable SWAP gates to maintain low circuit depth.
   • Key Schedule: The 128-bit master key schedule is realized as a unitary evolution involving a 113-bit left cyclic rotation, S-box substitutions, and round counter XORs, optimized for in-place execution.
2. Resource Estimation: The quantum cost is calculated using standard decomposition metrics (NOT and CNOT cost = 1, Toffoli cost = 6). The analysis evaluates both a baseline cost (excluding SWAP routing overhead) and an upper bound (decomposing SWAPs into three CNOTs).
3. Grover Cryptanalysis: A parallelized Grover oracle ($U_f$) is constructed to evaluate the cipher against key-recovery attacks. To eliminate spurious matches in the 128-bit key space, the oracle utilizes three plaintext-ciphertext pairs ($r=3$). The attack complexity is estimated by scaling the oracle's resource metrics by the optimal number of Grover iterations ($\approx \frac{\pi}{4}2^{64}$).

Key Contributions

• Optimized Quantum Implementation: The paper provides a qubit-optimized quantum circuit for GFSPX, achieving a footprint of 209 qubits. The design achieves a baseline quantum cost of 32,498 gates with a circuit depth of 7,617.
• Hybrid Architecture Analysis: The study details the resource distribution of a hybrid ARX-SPN design, demonstrating that while the modular addition primitive dominates the total gate count, the parallelized permutation layers in the SPN component help maintain a competitive gate-to-depth ratio.
• Quantitative Security Assessment: The authors construct a Grover oracle using three plaintext-ciphertext pairs and calculate the total attack cost under NIST's MAXDEPTH framework. The analysis reveals a total quantum attack cost of approximately $1.12 \times 2^{159}$ gates for $r=3$.
• Comparative Benchmarking: The implementation is benchmarked against other lightweight ciphers (e.g., PRESENT, GIFT, SIMON, SPECK). GFSPX achieves the lowest cost-to-depth ratio (4.27) among the compared designs, indicating high parallel execution efficiency.

Results

• Resource Metrics: The full 20-round GFSPX circuit requires 209 qubits. The baseline cost is 32,498, rising to 47,789 when SWAP routing overhead is included. The circuit depth is 7,617.
• Attack Complexity: The total quantum cost for a key-recovery attack is estimated at $1.12 \times 2^{159}$ (for $r=3$).
• Security Classification: Under the NIST Post-Quantum Cryptography framework, the Level 1 security threshold (equivalent to AES-128) requires a total attack cost of at least $2^{170}$. The estimated cost for GFSPX ($2^{159}$) falls below this threshold.
• Design Trade-offs: While GFSPX demonstrates higher quantum attack resistance than many pure SPN designs (which cluster around $2^{152}$), it does not meet the strict Level 1 security criteria for a 128-bit key length. The hybrid design's cost is heavily influenced by the ARX component (modular addition), placing its security profile closer to ARX-based ciphers like SIMON and SPECK.

Significance
The paper claims that its findings provide critical insights into the balance between classical hardware efficiency and quantum resilience for next-generation cryptographic designs. The study highlights a fundamental trade-off: while hybrid ARX-SPN constructions offer robust classical performance and better quantum resistance than pure SPN designs, a 128-bit key length remains structurally insufficient to achieve NIST Level 1 security against advanced quantum adversaries. The authors suggest that future research should focus on extending key lengths (e.g., to 192 or 256 bits) or optimizing reversible modular-addition primitives to improve security margins. The methodology established in this work serves as a rigorous framework for evaluating other hybrid designs in resource-constrained environments.