|
| related topics |
| {qubit, qubits, gate} |
| {algorithm, log, probability} |
| {time, systems, information} |
| {group, space, representation} |
| {force, casimir, field} |
| {let, theorem, proof} |
| {equation, function, exp} |
| {key, protocol, security} |
|
Optimized quantum implementation of elliptic curve arithmetic over
binary fields
Phillip Kaye, Christof Zalka
abstract: 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 [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 (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, we 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, we optimize specifically to reduce the
qubit space requirement, while keeping the running-time polynomial. Our
implementation here differs from that in [PZ03] for GF(p), and we are able to
take advantage of some properties of the binary field GF(2^m). We 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 [PZ03] for curves over
GF(p)).
- oai_identifier:
- oai:arXiv.org:quant-ph/0407095
- categories:
- quant-ph
- comments:
- 23 pages, 9 figures
- arxiv_id:
- quant-ph/0407095
- created:
- 2004-07-13
Full article ▸
|
|
| related documents |
| 0410001v3 |
| 9808027v1 |
| 0304061v5 |
| 0303175v1 |
| 9805070v1 |
| 0304054v2 |
| 0311069v1 |
| 0104085v1 |
| 0408081v5 |
| 0610105v1 |
| 0506062v2 |
| 0511041v1 |
| 0504197v1 |
| 0411058v1 |
| 0505122v2 |
| 0512058v3 |
| 0702212v1 |
| 0207157v1 |
| 0510161v1 |
| 0610214v3 |
| 0601183v1 |
| 0003137v2 |
| 0506006v1 |
| 0008015v2 |
| 0505009v4 |
|