Quantum Information and Computation

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

RöttelerMartin, SteinwandtRainer

Published Jul 1, 2014• 0 citations

Abstract

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 ...

DOI: 10.5555/2638670.2638681

Related papers

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

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

Shor's discrete logarithm quantum algorithm for elliptic curves

ProosJohn, ZalkaChristof

Quantum Information and ComputationJul 1, 200326 citations

Concrete quantum cryptanalysis of binary elliptic curves

Gustavo Banegas, Daniel J. Bernstein, Iggy van Hoof +1 more

IACR Transactions on Cryptographic Hardware and Embedded SystemsDec 3, 202047 citations

Shor's discrete logarithm quantum algorithm for elliptic curves

John Proos, Christof Zalka

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

Optimized quantum implementation of elliptic curve arithmetic over binary fields

Phillip Kaye

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

Quantum Information and Computation

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

RöttelerMartin, SteinwandtRainer

Published Jul 1, 2014• 0 citations

Publisher

Abstract

DOI: 10.5555/2638670.2638681

Related papers

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

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

Shor's discrete logarithm quantum algorithm for elliptic curves

ProosJohn, ZalkaChristof

Quantum Information and ComputationJul 1, 200326 citations

Concrete quantum cryptanalysis of binary elliptic curves

Gustavo Banegas, Daniel J. Bernstein, Iggy van Hoof +1 more

This paper analyzes and optimizes quantum circuits for computing discrete logarithms on binary elliptic curves, including reversible circuits for fixed-base-point scalar multiplication and the full stack of relevant subroutines. The main optimization target is the size of the quantum computer, i.e., the number of logical qubits required, as this appears to be the main obstacle to implementing Shor’s polynomial-time discrete-logarithm algorithm. The secondary optimization target is the number of logical Toffoli gates. For an elliptic curve over a field of 2n elements, this paper reduces the number of qubits to 7n + ⌊log2(n)⌋ + 9. At the same time this paper reduces the number of Toffoli gates to 48n3 + 8nlog2(3)+1 + 352n2 log2(n) + 512n2 + O(nlog2(3)) with double-and-add scalar multiplication, and a logarithmic factor smaller with fixed-window scalar multiplication. The number of CNOT gates is also O(n3). Exact gate counts are given for various sizes of elliptic curves currently used for cryptography.This paper analyzes and optimizes quantum circuits for computing discrete logarithms on binary elliptic curves, including reversible circuits for fixed-base-point scalar multiplication and the full stack of relevant subroutines. The main optimization target is the size of the quantum computer, i.e., the number of logical qubits required, as this appears to be the main obstacle to implementing Shor’s polynomial-time discrete-logarithm algorithm. The secondary optimization target is the number of logical Toffoli gates. For an elliptic curve over a field of 2n elements, this paper reduces the number of qubits to 7n + ⌊log2(n)⌋ + 9. At the same time this paper reduces the number of Toffoli gates to 48n3 + 8nlog2(3)+1 + 352n2 log2(n) + 512n2 + O(nlog2(3)) with double-and-add scalar multiplication, and a logarithmic factor smaller with fixed-window scalar multiplication. The number of CNOT gates is also O(n3). Exact gate counts are given for various sizes of elliptic curves currently used for cryptography.

IACR Transactions on Cryptographic Hardware and Embedded SystemsDec 3, 202047 citations

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

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

{\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)$).