This paper provides a detailed analysis and estimation of the quantum resources required for depth-optimized elliptic curve point multiplication (ECPM), with a focus on qubits, Toffoli gates, CNOT gates, and circuit depth. The proposed ECPM quantum circuit, which is tailored for binary elliptic curve cryptanalysis using Shor’s algorithm, incorporates improved arithmetic operations into optimized point addition (PA) and point doubling (PD) processes. The quantum resources required for single-step and full-step ECPM implementations (comprising $2n$ PD +2 PA) were systematically evaluated to enable in-depth cryptanalysis of binary elliptic curve cryptography using Shor’s algorithm. The proposed approach offers a significant improvement in resource efficiency compared to circuits that rely solely on the existing PA, which typically require ( $2n+2$ )PA operations. The execution of a full iteration of quantum cryptanalysis using the Shor circuit was estimated to require $2n^{3}+ 2n(\log 3 + 1) + 32n^{2}\log n + 8n^{2} + O (n^{(\log 3 + 1)})$ Toffoli gates, approximately $2n + 7n\log _{6} n + 7$ qubits, and a circuit depth of approximately $7+n\log _{3}{9}$ . Comparisons with leading Toffoli gate-level analysis results validate our findings, which demonstrate reduced quantum resource usage. In addition, key findings related to techniques for solving discrete logarithm problems are summarized, drawing from influential previous studies and current advancements.This paper provides a detailed analysis and estimation of the quantum resources required for depth-optimized elliptic curve point multiplication (ECPM), with a focus on qubits, Toffoli gates, CNOT gates, and circuit depth. The proposed ECPM quantum circuit, which is tailored for binary elliptic curve cryptanalysis using Shor’s algorithm, incorporates improved arithmetic operations into optimized point addition (PA) and point doubling (PD) processes. The quantum resources required for single-step and full-step ECPM implementations (comprising$2n$PD +2 PA) were systematically evaluated to enable in-depth cryptanalysis of binary elliptic curve cryptography using Shor’s algorithm. The proposed approach offers a significant improvement in resource efficiency compared to circuits that rely solely on the existing PA, which typically require ($2n+2$)PA operations. The execution of a full iteration of quantum cryptanalysis using the Shor circuit was estimated to require$2n^{3}+ 2n(\log 3 + 1) + 32n^{2}\log n + 8n^{2} + O (n^{(\log 3 + 1)})$Toffoli gates, approximately$2n + 7n\log _{6} n + 7$qubits, and a circuit depth of approximately$7+n\log _{3}{9}$. Comparisons with leading Toffoli gate-level analysis results validate our findings, which demonstrate reduced quantum resource usage. In addition, key findings related to techniques for solving discrete logarithm problems are summarized, drawing from influential previous studies and current advancements.

IEEE AccessJan 1, 20245 citations

Improvements to quantum search, with applications to cryptanalysis

Ben Pring

Jan 1, 20190 citations

Quantum circuits for cryptanalysis

Brittanney Amento

Jan 1, 20160 citations

Resource-Constrained Quantum Implementation and Analysis of Mini-AES Cipher

Syed Shahmir, Ghulam Murtaza, Elmahdi Bentafat +4 more

Quantum search algorithms, such as Grover's algorithm, will soon pose a threat to current encryption standards as quantum computing advances toward practical implementation. These algorithms rely on quantum circuits that map cryptographic algorithms into appropriate Hilbert spaces, thus linking algorithmic inputs and outputs through quantum superposition. However, implementing and testing such circuits on existing quantum simulators, such as Qiskit, encounters significant memory and computational bottlenecks that limit research progress. To address these simulation constraints, we present a resource-optimized quantum circuit implementation of a complete two-round Mini-AES encryption algorithm. Our approach systematically converts the cipher's algebraic structure using algebraic normal form (ANF) equations, mapping XOR operations to CNOT gates and AND operations to Toffoli gates. To reduce memory overhead, we implement an ancilla-reuse strategy utilizing mid-circuit measurements and resets. Additionally, we introduce an automated procedure that generates Qiskitcompatible quantum circuits for arbitrary S-boxes and cryptographic primitives, streamlining the development of quantum cryptanalysis implementations. Our implementation achieves full encryption and decryption in a quantum circuit with modest gate requirements that can be achieved by the current or near-future state of the art quantum computers. In addition, we provide system utilization metrics to validate our resource-constrained implementation. This compact and pedagogically accessible implementation establishes a practical foundation for quantum cryptanalysis research and post-quantum cryptographic analysis.Quantum search algorithms, such as Grover's algorithm, will soon pose a threat to current encryption standards as quantum computing advances toward practical implementation. These algorithms rely on quantum circuits that map cryptographic algorithms into appropriate Hilbert spaces, thus linking algorithmic inputs and outputs through quantum superposition. However, implementing and testing such circuits on existing quantum simulators, such as Qiskit, encounters significant memory and computational bottlenecks that limit research progress. To address these simulation constraints, we present a resource-optimized quantum circuit implementation of a complete two-round Mini-AES encryption algorithm. Our approach systematically converts the cipher's algebraic structure using algebraic normal form (ANF) equations, mapping XOR operations to CNOT gates and AND operations to Toffoli gates. To reduce memory overhead, we implement an ancilla-reuse strategy utilizing mid-circuit measurements and resets. Additionally, we introduce an automated procedure that generates Qiskitcompatible quantum circuits for arbitrary S-boxes and cryptographic primitives, streamlining the development of quantum cryptanalysis implementations. Our implementation achieves full encryption and decryption in a quantum circuit with modest gate requirements that can be achieved by the current or near-future state of the art quantum computers. In addition, we provide system utilization metrics to validate our resource-constrained implementation. This compact and pedagogically accessible implementation establishes a practical foundation for quantum cryptanalysis research and post-quantum cryptographic analysis.

arXiv:2503.06566International Conference on Quantum Communications, Networking, and Computing (QCNC)Apr 6, 20260 citations

Quantum Arithmetic Circuits in Public-Key Cryptography

Siyi Wang, Kyungbae Jang, Hyunji Kim +4 more

Quantum computing has advanced rapidly in recent decades, driven by developments across the technology stack, including quantum error-correcting codes and efficient quantum algorithms. Among these, quantum arithmetic circuits serve as fundamental building blocks for various promising algorithms. Despite their crucial role, the design of quantum arithmetic circuits faces challenges arising from the no-cloning theorem, qubit limitations, and circuit depth constraints, which significantly impact the efficiency of large-scale quantum computing. We provide an overview of quantum arithmetic circuits in the context of public-key cryptanalysis, with particular emphasis on optimization strategies such as measurement-based uncomputation and conditionally clean ancilla. We review state-of-the-art designs for essential arithmetic operations in public-key cryptanalysis such as addition, multiplication, and modular exponentiation. We also present an overview of the techniques used for fault-tolerant runtime and resource estimation in quantum cryptanalysis. In brief, this chapter emphasizes strategies for designing resource-efficient quantum arithmetic circuits, providing a basis for realistic evaluations of quantum cryptanalytic capabilities.Quantum computing has advanced rapidly in recent decades, driven by developments across the technology stack, including quantum error-correcting codes and efficient quantum algorithms. Among these, quantum arithmetic circuits serve as fundamental building blocks for various promising algorithms. Despite their crucial role, the design of quantum arithmetic circuits faces challenges arising from the no-cloning theorem, qubit limitations, and circuit depth constraints, which significantly impact the efficiency of large-scale quantum computing. We provide an overview of quantum arithmetic circuits in the context of public-key cryptanalysis, with particular emphasis on optimization strategies such as measurement-based uncomputation and conditionally clean ancilla. We review state-of-the-art designs for essential arithmetic operations in public-key cryptanalysis such as addition, multiplication, and modular exponentiation. We also present an overview of the techniques used for fault-tolerant runtime and resource estimation in quantum cryptanalysis. In brief, this chapter emphasizes strategies for designing resource-efficient quantum arithmetic circuits, providing a basis for realistic evaluations of quantum cryptanalytic capabilities.

quant-pharXiv:2607.11713Jul 14, 20260 citations

A practical-quantum differential attack on block ciphers

Tarun Yadav, Manoj Kumar, Amit Kumar +1 more

Abstract Differential attack is a basic cryptanalysis method for block ciphers that exploits the high probability relations between the input and output differences. The existing work in quantum differential cryptanalysis of block ciphers is focused on resource estimation to recover the last round subkeys on the basis of relations constructed using classical methods. To find such relations using quantum computing, we propose a method to search the high probability differential and impossible differential characteristics. The method explores all possible input and output difference pairs using superposition of qubits. The proposed method is used to design the quantum circuit to search the differential characteristics for a toy cipher smallGIFT. We execute the quantum circuit on a quantum simulator to get differential and impossible characteristics. These characteristics are validated with the characteristics obtained using branch-and-bound based method. The differential characteristic is used to mount quantum key recovery attack using Grover's search. We provide the estimation of quantum resources to search the differential characteristics of lightweight block cipher GIFT-64 on a quantum computer.Abstract Differential attack is a basic cryptanalysis method for block ciphers that exploits the high probability relations between the input and output differences. The existing work in quantum differential cryptanalysis of block ciphers is focused on resource estimation to recover the last round subkeys on the basis of relations constructed using classical methods. To find such relations using quantum computing, we propose a method to search the high probability differential and impossible differential characteristics. The method explores all possible input and output difference pairs using superposition of qubits. The proposed method is used to design the quantum circuit to search the differential characteristics for a toy cipher smallGIFT. We execute the quantum circuit on a quantum simulator to get differential and impossible characteristics. These characteristics are validated with the characteristics obtained using branch-and-bound based method. The differential characteristic is used to mount quantum key recovery attack using Grover's search. We provide the estimation of quantum resources to search the differential characteristics of lightweight block cipher GIFT-64 on a quantum computer.

Cryptography and CommunicationsJul 1, 202311 citations

2n

PD +2 PA) were systematically evaluated to enable in-depth cryptanalysis of binary elliptic curve cryptography using Shor’s algorithm. The proposed approach offers a significant improvement in resource efficiency compared to circuits that rely solely on the existing PA, which typically require (

2n+2

)PA operations. The execution of a full iteration of quantum cryptanalysis using the Shor circuit was estimated to require

2n^{3}+ 2n(\log 3 + 1) + 32n^{2}\log n + 8n^{2} + O (n^{(\log 3 + 1)})

Toffoli gates, approximately

2n + 7n\log _{6} n + 7

qubits, and a circuit depth of approximately

7+n\log _{3}{9}

. Comparisons with leading Toffoli gate-level analysis results validate our findings, which demonstrate reduced quantum resource usage. In addition, key findings related to techniques for solving discrete logarithm problems are summarized, drawing from influential previous studies and current advancements.