Quantum Information and Computation

Shor's discrete logarithm quantum algorithm for elliptic curves

ProosJohn, ZalkaChristof

Published Jul 1, 2003• 26 citations

Publisher

Abstract

DOI: 10.5555/2011528.2011531

Related papers

Shor's discrete logarithm quantum algorithm for elliptic curves

John Proos, Christof Zalka

arXiv:quant-ph/0301141Quantum Information and ComputationJul 1, 2003340 citations

A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log2 n)

RöttelerMartin, SteinwandtRainer

Improving over an earlier construction by Kaye and Zalka [1], in [2] Maslov et al. describe an implementation of Shor's algorithm, which can solve the discrete logarithm problem on ordinary binary ...

Quantum Information and ComputationJul 1, 20140 citations

A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2n)

Martin Rötteler, Rainer Steinwandt

Quantum Information and ComputationJul 1, 20149 citations

Optimized quantum implementation of elliptic curve arithmetic over binary fields

Phillip Kaye

arXiv:quant-ph/0407095Quantum Information and ComputationSep 1, 200527 citations

A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2 n)

Martin Roetteler, Rainer Steinwandt

Improving over an earlier construction by Kaye and Zalka, Maslov et al. describe an implementation of Shor's algorithm which can solve the discrete logarithm problem on binary elliptic curves in quadratic depth O(n^2). In this paper we show that discrete logarithms on such curves can be found with a quantum circuit of depth O(log^2 n). As technical tools we introduce quantum circuits for GF(2^n) multiplication in depth O(log n) and for GF(2^n) inversion in depth O(log^2 n).

arXiv:1306.1161Jun 5, 20130 citations

Quantum Cryptanalysis Landscape of Shor’s Algorithm for Elliptic Curve Discrete Logarithm Problem

Harashta Tatimma Larasati, Howon Kim

Lecture notes in computer scienceJan 1, 202118 citations

Quantum Information and Computation

Shor's discrete logarithm quantum algorithm for elliptic curves

ProosJohn, ZalkaChristof

Published Jul 1, 2003• 26 citations

Publisher

Abstract

DOI: 10.5555/2011528.2011531

Related papers

Shor's discrete logarithm quantum algorithm for elliptic curves

John Proos, Christof Zalka

We show in some detail how to implement Shor's efficient quantum algorithm for discrete logarithms for the particular case of elliptic curve groups. It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits. In this paper we only consider elliptic curves over GF(p) and not yet the equally important ones over GF(2^n) or other finite fields. The main technical difficulty is to implement Euclid's gcd algorithm to compute multiplicative inverses modulo p. As the runtime of Euclid's algorithm depends on the input, one difficulty encountered is the ``quantum halting problem''.We show in some detail how to implement Shor's efficient quantum algorithm for discrete logarithms for the particular case of elliptic curve groups. It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits. In this paper we only consider elliptic curves over GF(p) and not yet the equally important ones over GF(2^n) or other finite fields. The main technical difficulty is to implement Euclid's gcd algorithm to compute multiplicative inverses modulo p. As the runtime of Euclid's algorithm depends on the input, one difficulty encountered is the ``quantum halting problem''.

arXiv:quant-ph/0301141Quantum Information and ComputationJul 1, 2003340 citations

A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log2 n)

RöttelerMartin, SteinwandtRainer

Quantum Information and ComputationJul 1, 20140 citations

A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2n)

Martin Rötteler, Rainer Steinwandt

Improving over an earlier construction by Kaye and Zalka \cite{KaZa04}, in \cite{MMCP09b} Maslov et al. describe an implementation of Shor's algorithm, which can solve the discrete logarithm problem on ordinary binary elliptic curves in quadratic depth $\bigO(n^2)$. In this paper we show that discrete logarithms on such curves can be found with a quantum circuit of depth $\bigO(\log^2n)$. As technical tools we introduce quantum circuits for ${\mathbb F}_{2^n}$ -multiplication in depth $\bigO(\log n)$ and for ${\mathbb F}_{2^n}$ -inversion in depth $\bigO(\log^2 n)$.Improving over an earlier construction by Kaye and Zalka \cite{KaZa04}, in \cite{MMCP09b} Maslov et al. describe an implementation of Shor's algorithm, which can solve the discrete logarithm problem on ordinary binary elliptic curves in quadratic depth $\bigO(n^2)$. In this paper we show that discrete logarithms on such curves can be found with a quantum circuit of depth $\bigO(\log^2n)$. As technical tools we introduce quantum circuits for ${\mathbb F}_{2^n}$-multiplication in depth $\bigO(\log n)$ and for ${\mathbb F}_{2^n}$-inversion in depth $\bigO(\log^2 n)$.

Quantum Information and ComputationJul 1, 20149 citations

Optimized quantum implementation of elliptic curve arithmetic over binary fields

Phillip Kaye

Shor's quantum algorithm for discrete logarithms applied to elliptic curve groups forms the basis of a ``quantum attack'' of elliptic curve cryptosystems. To implement this algorithm on a quantum computer requires the efficient implementation of the elliptic curve group operation. Such an implementation requires we be able to compute inverses in the underlying field. In \cite{PZ03}, Proos and Zalka show how to implement the extended Euclidean algorithm to compute inverses in the prime field $\GF(p)$. They employ a number of optimizations to achieve a running time of $O(n^2)$ , and a space-requirement of $O(n)$ qubits, where $n$ is the number of bits in the binary representation of $p$ (there are some trade-offs that they make, sacrificing a few extra qubits to reduce running-time). In practice, elliptic curve cryptosystems often use curves over the binary field $\GF(2^m)$. In this paper, I show how to implement the extended Euclidean algorithm for polynomials to compute inverses in $\GF(2^m)$. Working under the assumption that qubits will be an `expensive' resource in realistic implementations, I optimize specifically to reduce the qubit space requirement, while keeping the running-time polynomial. The implementation here differs from that in $\cite{PZ03}$ for $\GF(p)$, and we are able to take advantage of some properties of the binary field $\GF(2^m)$. I also optimize the overall qubit space requirement for computing the group operation for elliptic curves over $\GF(2^m)$ by decomposing the group operation to make it ``piecewise reversible'' (similar to what is done in \cite{PZ03} for curves over $\GF(p)$).Shor's quantum algorithm for discrete logarithms applied to elliptic curve groups forms the basis of a ``quantum attack'' of elliptic curve cryptosystems. To implement this algorithm on a quantum computer requires the efficient implementation of the elliptic curve group operation. Such an implementation requires we be able to compute inverses in the underlying field. In \cite{PZ03}, Proos and Zalka show how to implement the extended Euclidean algorithm to compute inverses in the prime field $\GF(p)$. They employ a number of optimizations to achieve a running time of $O(n^2)$, and a space-requirement of $O(n)$ qubits, where $n$ is the number of bits in the binary representation of $p$ (there are some trade-offs that they make, sacrificing a few extra qubits to reduce running-time). In practice, elliptic curve cryptosystems often use curves over the binary field $\GF(2^m)$. In this paper, I show how to implement the extended Euclidean algorithm for polynomials to compute inverses in $\GF(2^m)$. Working under the assumption that qubits will be an `expensive' resource in realistic implementations, I optimize specifically to reduce the qubit space requirement, while keeping the running-time polynomial. The implementation here differs from that in $\cite{PZ03}$ for $\GF(p)$, and we are able to take advantage of some properties of the binary field $\GF(2^m)$. I also optimize the overall qubit space requirement for computing the group operation for elliptic curves over $\GF(2^m)$ by decomposing the group operation to make it ``piecewise reversible'' (similar to what is done in \cite{PZ03} for curves over $\GF(p)$).

arXiv:quant-ph/0407095Quantum Information and ComputationSep 1, 200527 citations

A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2 n)

Martin Roetteler, Rainer Steinwandt

arXiv:1306.1161Jun 5, 20130 citations

Quantum Cryptanalysis Landscape of Shor’s Algorithm for Elliptic Curve Discrete Logarithm Problem

Harashta Tatimma Larasati, Howon Kim

Lecture notes in computer scienceJan 1, 202118 citations

{\mathbb F}_{2^n}

-multiplication in depth $\bigO(\log n)$ and for

{\mathbb F}_{2^n}

-inversion in depth $\bigO(\log^2 n)$.

O(n^2)

, and a space-requirement of

O(n)

qubits, where

n

is the number of bits in the binary representation of

p

(there are some trade-offs that they make, sacrificing a few extra qubits to reduce running-time). In practice, elliptic curve cryptosystems often use curves over the binary field $\GF(2^m)$. In this paper, I show how to implement the extended Euclidean algorithm for polynomials to compute inverses in $\GF(2^m)$. Working under the assumption that qubits will be an `expensive' resource in realistic implementations, I optimize specifically to reduce the qubit space requirement, while keeping the running-time polynomial. The implementation here differs from that in $\cite{PZ03}$ for $\GF(p)$, and we are able to take advantage of some properties of the binary field $\GF(2^m)$. I also optimize the overall qubit space requirement for computing the group operation for elliptic curves over $\GF(2^m)$ by decomposing the group operation to make it ``piecewise reversible'' (similar to what is done in \cite{PZ03} for curves over $\GF(p)$).