Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Access

Depth-Optimization of Quantum Cryptanalysis on Binary Elliptic Curves

Dedy Septono Catur Putranto, Rini Wisnu Wardhani, Harashta Tatimma Larasati, Janghyun Ji, Howon Kim

Published Jan 1, 2023• 18 citations
Publisher

Abstract

This paper presents quantum cryptanalysis for binary elliptic curves from a time-efficient implementation perspective (i.e., reducing the circuit depth), complementing the previous research that focuses on the space-efficiency perspective (i.e., reducing the circuit width). To achieve depth optimization, we propose an improvement to the existing circuit implementation of the Karatsuba multiplier and FLT-based inversion, then construct and analyze the resource in the Qiskit quantum computer simulator. The proposed multiplier architecture, which improves the quantum Karatsuba multiplier from the previous study, reduces the depth and yields a lower number of CNOT gates that bound to$O(n^{log_{2}(3)})$while maintaining a similar number of Toffoli gates and qubits. Furthermore, our improved FLT-based inversion reduces CNOT count and overall depth, with a tradeoff of higher qubit size. Finally, we employ the proposed multiplier and FLT-based inversion for performing quantum cryptanalysis of binary point addition as well as the complete Shor’s algorithm for the elliptic curve discrete logarithm problem (ECDLP). As a result, apart from depth reduction, we are also able to reduce up to 90% of the Toffoli gates required in a single-step point addition compared to prior work, leading to significant improvements and giving new insights on quantum cryptanalysis for a depth-optimized implementation.

DOI
10.1109/access.2023.3273601

Related papers

Depth Optimization of FLT-Based Quantum Inversion Circuit

Harashta Tatimma Larasati, Dedy Septono Catur Putranto, Rini Wisnu Wardhani +2 more

Works on quantum computing and cryptanalysis have increased significantly in the past few years. Various constructions of quantum arithmetic circuits as one of the primary elements in the field have also been proposed. However, there have only been a few studies on finite field inversion despite its essential use in realizing quantum algorithms, such as in Shor’s algorithm for Elliptic Curve Discrete Logarithm Problem (ECDLP). In this study, we propose to reduce the depth of the existing quantum Fermat’s Little Theorem (FLT)-based inversion circuit for the binary finite field. In particular, we propose to follow a complete waterfall approach to translate the Itoh-Tsujii’s variant of FLT to the corresponding quantum circuit and remove the inverse squaring operations employed in the previous work by Banegas et al., lowering the number of CNOT gates (i.e., CNOT count) as well as slightly reducing the$T$depth, which contributes to a reduced overall depth and gate count. Furthermore, we concretely verify our method and compare it with the previous work in Qiskit, a quantum computer simulation environment, by constructing both our method and the previous work from scratch and performing the resource analysis. Additionally, we propose employing the relative-phase Toffoli gate by Gidney as opposed to the standard Toffoli implementation, which yields a significantly lower$T$depth while further reducing the overall depth. Our approach can serve as an alternative for a time-efficient implementation.

IEEE Access•Jan 1, 2023•6 citations

A Highly Efficient ECPM Quantum Circuit for Binary Elliptic Curve Cryptanalysis

Rini Wisnu Wardhani, Dedy Septono Catur Putranto, Jaehan Cho +1 more

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 Access•Jan 1, 2024•5 citations

Concrete quantum cryptanalysis of binary elliptic curves via addition chain

Ren Taguchi, Atsushi Takayasu

Abstract Thus far, several papers reported concrete resource estimates of Shor’s quantum algorithm for solving the elliptic curve discrete logarithm problem. In this paper, we study quantum FLT-based inversion algorithms over binary elliptic curves. There are two major algorithms proposed by Banegas et al. and Putranto et al., where the former and latter algorithms achieve fewer numbers of qubits and smaller depths of circuits, respectively. We propose two quantum FLT-based inversion algorithms that essentially outperform previous FLT-based algorithms and compare the performance for NIST curves of the degreen. Specifically, for alln, our first algorithm achieves fewer qubits than Putranto et al.’s one without sacrificing the number of Toffoli gates and the depth of circuits, while our second algorithm achieves smaller depths of circuits without sacrificing the number of qubits and Toffoli gates. For example, when $$n = 571$$ n=571 , the number of qubits of our first algorithm is 74 % of that of Putranto et al.’s one, while the depth of our second algorithm is 83 % of that of Banegas et al.’s one. The improvements stem from the fact that FLT-based inversions can be performed with arbitrary sequences of addition chains for $$n - 1$$ n-1 although both Banegas et al. and Putranto et al. follow fixed sequences that were introduced by Itoh and Tsujii’s classical FLT-based inversion. In particular, we analyze how several properties of addition chains, which do not affect the computational resources of classical FLT-based inversions, affect the computational resources of quantum FLT-based inversions and find appropriate sequences.

Quantum Information Processing•Mar 25, 2024•2 citations

Reducing the Depth of Quantum FLT-Based Inversion Circuit

Harashta Tatimma Larasati, Dedy Septono Catur Putranto, Rini Wisnu Wardhani +1 more

Works on quantum computing and cryptanalysis has increased significantly in the past few years. Various constructions of quantum arithmetic circuits, as one of the essential components in the field, has also been proposed. However, there has only been a few studies on finite field inversion despite its essential use in realizing quantum algorithms, such as in Shor's algorithm for Elliptic Curve Discrete Logarith Problem (ECDLP). In this study, we propose to reduce the depth of the existing quantum Fermat's Little Theorem (FLT)-based inversion circuit for binary finite field. In particular, we propose follow a complete waterfall approach to translate the Itoh-Tsujii's variant of FLT to the corresponding quantum circuit and remove the inverse squaring operations employed in the previous work by Banegas et al., lowering the number of CNOT gates (CNOT count), which contributes to reduced overall depth and gate count. Furthermore, compare the cost by firstly constructing our method and previous work's in Qiskit quantum computer simulator and perform the resource analysis. Our approach can serve as an alternative for a time-efficient implementation.

arXiv:2204.08940•Apr 16, 2022•1 citation

Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation

Han Luo, Ziyi Yang, Ziruo Wang +2 more

Solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) is critical for evaluating the quantum security of widely deployed elliptic-curve cryptosystems. Consequently, minimizing the number of logical qubits required to execute this algorithm is a key object. In implementations of Shor's algorithm, the space complexity is largely dictated by the modular inversion operation during point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing method of Proos and Zalka and propose a space-efficient reversible modular inversion algorithm. We use length registers together with location-controlled arithmetic to store the intermediate variables in a compact form throughout the computation. We then optimize the stepwise update rules and give concrete circuit constructions for the resulting controlled arithmetic components. This leads to a modular inversion circuit that uses $3n + 4\lfloor \log_2 n \rfloor + O(1)$ logical qubits and $204n^2\log_2 n + O(n^2)$ Toffoli gates. By inserting this modular inversion component into the controlled affine point-addition circuit, we obtain a space-efficient algorithm for the ECDLP with $5n + 4\lfloor \log_2 n \rfloor + O(1)$ qubits and $O(n^3)$ Toffoli gates. In particular, for a 256-bit prime-field curve, our estimate reduces the logical-qubit count to 1333, compared with 2124 in the previous low-width implementation of Häner et al.

quant-pharXiv:2604.02311•Apr 3, 2026•0 citations

Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition

Han Luo, Ziyi Yang, Jingquan Luo +5 more

The Elliptic Curve Discrete Logarithm Problem (ECDLP) is a fundamental problem in cryptography, and reducing the resource requirements of quantum algorithms for solving ECDLP is an important goal. In this work, we present a space-efficient quantum algorithm for solving the ECDLP over prime fields, achieving an implementation with only $3n+6\lfloor \log_2 n \rfloor+O(1)$ logical qubits and $1056n^3/\log_2 n+O(n^2)$ Toffoli gates, where $n$ is the bit-length of the prime. For a 256-bit prime-field curve, our construction requires only 835 logical qubits, reducing the previous best estimates of 1098 and 1175 logical qubits by Chevignard et al. [EUROCRYPT 2026] and Babbush et al. [ArXiv Preprint 2026], respectively. The key to our improvement is a new space-efficient reversible modular inversion circuit, which addresses the dominant space bottleneck in affine-coordinate point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing technique of Proos and Zalka by introducing length registers and location-controlled arithmetic to compactly store and update intermediate variables. We further optimize the reversible update procedures and construct the corresponding controlled arithmetic circuits, resulting in a modular inversion circuit implemented by only $2n+6\lfloor \log_2 n \rfloor+O(1)$ logical qubits and $229n^2+O(n\log_2 n)$ Toffoli gates. This modular inversion circuit together with mid-circuit measurements and classical feed-forward operations provides a space-efficient controlled affine point-addition circuit and a complete implementation of Shor's algorithm for ECDLP.

quant-pharXiv:2607.13816•Jul 16, 2026•0 citations
This paper presents quantum cryptanalysis for binary elliptic curves from a time-efficient implementation perspective (i.e., reducing the circuit depth), complementing the previous research that focuses on the space-efficiency perspective (i.e., reducing the circuit width). To achieve depth optimization, we propose an improvement to the existing circuit implementation of the Karatsuba multiplier and FLT-based inversion, then construct and analyze the resource in the Qiskit quantum computer simulator. The proposed multiplier architecture, which improves the quantum Karatsuba multiplier from the previous study, reduces the depth and yields a lower number of CNOT gates that bound toO(nlog2(3))O(n^{log_{2}(3)})O(nlog2​(3))while maintaining a similar number of Toffoli gates and qubits. Furthermore, our improved FLT-based inversion reduces CNOT count and overall depth, with a tradeoff of higher qubit size. Finally, we employ the proposed multiplier and FLT-based inversion for performing quantum cryptanalysis of binary point addition as well as the complete Shor’s algorithm for the elliptic curve discrete logarithm problem (ECDLP). As a result, apart from depth reduction, we are also able to reduce up to 90% of the Toffoli gates required in a single-step point addition compared to prior work, leading to significant improvements and giving new insights on quantum cryptanalysis for a depth-optimized implementation.
Works on quantum computing and cryptanalysis have increased significantly in the past few years. Various constructions of quantum arithmetic circuits as one of the primary elements in the field have also been proposed. However, there have only been a few studies on finite field inversion despite its essential use in realizing quantum algorithms, such as in Shor’s algorithm for Elliptic Curve Discrete Logarithm Problem (ECDLP). In this study, we propose to reduce the depth of the existing quantum Fermat’s Little Theorem (FLT)-based inversion circuit for the binary finite field. In particular, we propose to follow a complete waterfall approach to translate the Itoh-Tsujii’s variant of FLT to the corresponding quantum circuit and remove the inverse squaring operations employed in the previous work by Banegas et al., lowering the number of CNOT gates (i.e., CNOT count) as well as slightly reducing theTTTdepth, which contributes to a reduced overall depth and gate count. Furthermore, we concretely verify our method and compare it with the previous work in Qiskit, a quantum computer simulation environment, by constructing both our method and the previous work from scratch and performing the resource analysis. Additionally, we propose employing the relative-phase Toffoli gate by Gidney as opposed to the standard Toffoli implementation, which yields a significantly lowerTTTdepth while further reducing the overall depth. Our approach can serve as an alternative for a time-efficient implementation.
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 (comprising2n2n2nPD +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+22n+22n+2)PA operations. The execution of a full iteration of quantum cryptanalysis using the Shor circuit was estimated to require2n3+2n(log⁡3+1)+32n2log⁡n+8n2+O(n(log⁡3+1))2n^{3}+ 2n(\log 3 + 1) + 32n^{2}\log n + 8n^{2} + O (n^{(\log 3 + 1)})2n3+2n(log3+1)+32n2logn+8n2+O(n(log3+1))Toffoli gates, approximately2n+7nlog⁡6n+72n + 7n\log _{6} n + 72n+7nlog6​n+7qubits, and a circuit depth of approximately7+nlog⁡397+n\log _{3}{9}7+nlog3​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.
Abstract Thus far, several papers reported concrete resource estimates of Shor’s quantum algorithm for solving the elliptic curve discrete logarithm problem. In this paper, we study quantum FLT-based inversion algorithms over binary elliptic curves. There are two major algorithms proposed by Banegas et al. and Putranto et al., where the former and latter algorithms achieve fewer numbers of qubits and smaller depths of circuits, respectively. We propose two quantum FLT-based inversion algorithms that essentially outperform previous FLT-based algorithms and compare the performance for NIST curves of the degreen. Specifically, for alln, our first algorithm achieves fewer qubits than Putranto et al.’s one without sacrificing the number of Toffoli gates and the depth of circuits, while our second algorithm achieves smaller depths of circuits without sacrificing the number of qubits and Toffoli gates. For example, when n=571n = 571n=571 n=571 , the number of qubits of our first algorithm is 74 % of that of Putranto et al.’s one, while the depth of our second algorithm is 83 % of that of Banegas et al.’s one. The improvements stem from the fact that FLT-based inversions can be performed with arbitrary sequences of addition chains for n−1n - 1n−1 n-1 although both Banegas et al. and Putranto et al. follow fixed sequences that were introduced by Itoh and Tsujii’s classical FLT-based inversion. In particular, we analyze how several properties of addition chains, which do not affect the computational resources of classical FLT-based inversions, affect the computational resources of quantum FLT-based inversions and find appropriate sequences.
Works on quantum computing and cryptanalysis has increased significantly in the past few years. Various constructions of quantum arithmetic circuits, as one of the essential components in the field, has also been proposed. However, there has only been a few studies on finite field inversion despite its essential use in realizing quantum algorithms, such as in Shor's algorithm for Elliptic Curve Discrete Logarith Problem (ECDLP). In this study, we propose to reduce the depth of the existing quantum Fermat's Little Theorem (FLT)-based inversion circuit for binary finite field. In particular, we propose follow a complete waterfall approach to translate the Itoh-Tsujii's variant of FLT to the corresponding quantum circuit and remove the inverse squaring operations employed in the previous work by Banegas et al., lowering the number of CNOT gates (CNOT count), which contributes to reduced overall depth and gate count. Furthermore, compare the cost by firstly constructing our method and previous work's in Qiskit quantum computer simulator and perform the resource analysis. Our approach can serve as an alternative for a time-efficient implementation.
Solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) is critical for evaluating the quantum security of widely deployed elliptic-curve cryptosystems. Consequently, minimizing the number of logical qubits required to execute this algorithm is a key object. In implementations of Shor's algorithm, the space complexity is largely dictated by the modular inversion operation during point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing method of Proos and Zalka and propose a space-efficient reversible modular inversion algorithm. We use length registers together with location-controlled arithmetic to store the intermediate variables in a compact form throughout the computation. We then optimize the stepwise update rules and give concrete circuit constructions for the resulting controlled arithmetic components. This leads to a modular inversion circuit that uses 3n+4⌊log⁡2n⌋+O(1)3n + 4\lfloor \log_2 n \rfloor + O(1)3n+4⌊log2​n⌋+O(1) logical qubits and 204n2log⁡2n+O(n2)204n^2\log_2 n + O(n^2)204n2log2​n+O(n2) Toffoli gates. By inserting this modular inversion component into the controlled affine point-addition circuit, we obtain a space-efficient algorithm for the ECDLP with 5n+4⌊log⁡2n⌋+O(1)5n + 4\lfloor \log_2 n \rfloor + O(1)5n+4⌊log2​n⌋+O(1) qubits and O(n3)O(n^3)O(n3) Toffoli gates. In particular, for a 256-bit prime-field curve, our estimate reduces the logical-qubit count to 1333, compared with 2124 in the previous low-width implementation of Häner et al.
The Elliptic Curve Discrete Logarithm Problem (ECDLP) is a fundamental problem in cryptography, and reducing the resource requirements of quantum algorithms for solving ECDLP is an important goal. In this work, we present a space-efficient quantum algorithm for solving the ECDLP over prime fields, achieving an implementation with only 3n+6⌊log⁡2n⌋+O(1)3n+6\lfloor \log_2 n \rfloor+O(1)3n+6⌊log2​n⌋+O(1) logical qubits and 1056n3/log⁡2n+O(n2)1056n^3/\log_2 n+O(n^2)1056n3/log2​n+O(n2) Toffoli gates, where nnn is the bit-length of the prime. For a 256-bit prime-field curve, our construction requires only 835 logical qubits, reducing the previous best estimates of 1098 and 1175 logical qubits by Chevignard et al. [EUROCRYPT 2026] and Babbush et al. [ArXiv Preprint 2026], respectively. The key to our improvement is a new space-efficient reversible modular inversion circuit, which addresses the dominant space bottleneck in affine-coordinate point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing technique of Proos and Zalka by introducing length registers and location-controlled arithmetic to compactly store and update intermediate variables. We further optimize the reversible update procedures and construct the corresponding controlled arithmetic circuits, resulting in a modular inversion circuit implemented by only 2n+6⌊log⁡2n⌋+O(1)2n+6\lfloor \log_2 n \rfloor+O(1)2n+6⌊log2​n⌋+O(1) logical qubits and 229n2+O(nlog⁡2n)229n^2+O(n\log_2 n)229n2+O(nlog2​n) Toffoli gates. This modular inversion circuit together with mid-circuit measurements and classical feed-forward operations provides a space-efficient controlled affine point-addition circuit and a complete implementation of Shor's algorithm for ECDLP.