Publications
- The Tate Pairing via Elliptic Nets
- [ IACR eprint 2006/392 | pdf | ps ]
We derive a new algorithm for computing the Tate
pairing on an elliptic curve over a finite field. The algorithm uses a
generalisation of elliptic divisibility sequences known as elliptic
nets, which are maps from Z^n to a ring that satisfy a certain
recurrence relation. We explain how an elliptic net is associated to an
elliptic curve and reflects its group structure. Then we give a formula
for the Tate pairing in terms of values of the net. Using the
recurrence relation we can calculate these values in linear time.
Computing
the Tate pairing is the bottleneck to efficient pairing-based
cryptography. The new algorithm has time complexity comparable to
Miller's algorithm, and is likely to yield to further optimisation.
Preprints
- The Elliptic Curve Discrete Logarithm Problem and Equivalent Hard Problems for Elliptic Divisibility Sequences
- [ IACR eprint 2008/099 |
- arXiv: 0803.0728v1 | pdf | ps ]
We define three hard problems in terms of the theory of elliptic
divisibility sequences (EDS Association, EDS Residue and EDS
Discrete Log), each of which is solvable in sub-exponential time if and
only if the elliptic curve discrete logarithm problem is solvable in
sub-exponential time. We also relate the problem of EDS
Association to the Tate pairing and the MOV, Frey-Ruck and Shipsey EDS
attacks on the elliptic curve discrete logarithm problem in the cases
where these apply.
- Elliptic
Nets and Elliptic Curves
- [ arXiv:
0710.1316v2
| pdf
| ps ]
Submitted 2008.
Elliptic divisibility sequences are integer recurrence
sequences, each of
which is associated to an elliptic curve over the rationals together
with a
rational point on that curve. In this paper we present a
higher-dimensional
analogue over arbitrary base fields. Suppose E is an elliptic curve
over a
field K, and P_1, ..., P_n are points on E defined over K. To this
information
we associate an n-dimensional array of values of K satisfying a
complicated
nonlinear recurrence relation. Arrays satisfying this relation are
called
elliptic nets. All elliptic nets arise from elliptic curves in this
manner. In
this paper we describe properties of elliptic nets, and in particular
we prove
an explicit bijection between the set of elliptic nets and the set of
elliptic
curves with specified points.
- Classification of General PSH-Algebras
- [ not available ]
With Peter Hoffman and Chris Wooff, accepted pending revisions to Communicaions in Algebra in 2003; currently in digital limbo.
