Analysis of the Xedni Calculus Attack.
The xedni calculus attack on the elliptic curve discrete logarithm problem (ECDLP) involves lifting points from the finite field{\Bbb F}_p to the rational numbers {\Bbb Q} and then constructing an elliptic curve over {\Bbb Q} that passes through them. If the lifted points are linearly dependent, then the ECDLP is solved. Our purpose is to analyze the practicality of this algorithm. We find that asymptotically the algorithm is virtually certain to fail, because of an absolute bound on the size of the coefficients of a relation satisfied by the lifted points. Moreover, even for smaller values of p experiments show that the odds against finding a suitable lifting are prohibitively high.
Introduction
At the Second Elliptic Curve Cryptography Workshop (University of Waterloo, September 14-16,
1998), Joseph Silverman announced a new attack on the elliptic curve discrete logarithm problem
(ECDLP) over a prime field F p . He called his method "xedni calculus" because it "stands index
calculus on its head." 1
Recall that the ECDLP is the problem, given two points on an elliptic curve over F p ,
of finding an integer w such that briefly, Silverman's idea was to take r random
At about the same time, some similar ideas were developed independently in Korea [4].
linear combinations of the two points (most likely 4, 5 or 6), and
then consider points P i with rational coordinates that reduce modulo p to these r points and
elliptic curves E over the rational number field Q that pass through all of the P i and reduce
mod p to the original curve over F p . If those "lifted" points P i are linearly dependent, then the
ECDLP is solved. The probability of dependence is almost certainly very low, but Silverman
had an idea of how to increase this probability, possibly by a dramatic amount. Namely, he
imposes on the P i and E a set of auxiliary conditions modulo l for several small primes l. These
conditions guarantee that the elliptic curves will have fewer-than-expected points modulo l, and
this presumably decreases the likelihood that the r Q-points P i will be independent. (More
details will be given in x3 below.)
Silverman's algorithm, which had been circulating in manuscript form for about two weeks
before the conference, created a stir for several reasons. In the first place, this was the first time in
about seven years that a serious attack had been proposed on an important class of elliptic curve
cryptosystems. In the second place, Silverman's approach involved some sophisticated ideas
of arithmetic algebraic geometry - most notably, the heuristics of the Birch-Swinnerton-Dyer
Conjecture - that had never before had any practical application. In the third place, because
of the subtlety of the mathematics being used, even people who had computational experience
with elliptic curves were completely baffled in their initial attempts to estimate the running time
of the xedni calculus. No one, for example, could say with absolute certainty that it would not
turn out to give a polynomial-time algorithm!
If it were practical, the xedni calculus would not only break elliptic curve cryptosystems
(ECC). As Koblitz showed, it can easily be modified to attack (1) the Digital Signature Standard
(i.e., the discrete logarithm problem in the multiplicative group of F p ), and (2) RSA (i.e., the
integer factorization problem). Thus, essentially all public-key cryptography that's in widespread
use in the real world was threatened.
Of course, most people, including Silverman himself, thought that it was highly unlikely
that the algorithm would turn out to be so efficient that it would render ECC, DSS, and RSA
insecure. However, it is not enough to have a "gut feeling" about such matters. One needs to find
solid mathematical arguments that enable one to evaluate the efficiency of the xedni calculus.
That is the purpose of this paper.

Acknowledgments

. The authors wish to thank the faculty and staff of the Centre for Applied
Cryptographic Research at the University of Waterloo for their help during the work reported
on in this paper. We are especially grateful to Prof. Alfred Menezes for his support and encouragement

Background
2.1 The Hasse-Weil L-Function
Let E be an elliptic curve defined over the field Q of rational numbers, and let N l
denote the number of points on the reduction of E modulo l. 2 For each l we have the associated
whose value at
polynomial is the numerator of the zeta-function of E mod l. By Hasse's Theorem, ff l is a
complex number of absolute value
l.
The Hasse-Weil L-function of the curve E is defined by analogy with the Riemann zeta-
function
primes l1\Gammal \Gammas : Namely, we take L(E; s) to be the product over l of the following
"Euler
It is easy to verify that the infinite product converges for Re(s) ? 3=2 (just as the Euler product
for the Riemann zeta-function converges for Re(s) ? 1). By the "critical value" we mean the
value of L(E; s) at Just as one has to analytically continue the Riemann zeta-function
a distance 1/2 to the left in order to reach the "critical line," similarly one has to analytically
continue L(E; s) a distance 1/2 to the left in order to reach the critical value.
However, analytic continuation of L(E; s) is not nearly so simple as in the case of i(s); and,
in fact, it has been proven only in the case when E is "modular" in the following sense. If we
expand the Euler product, we can write L(E; s) in the form
P a n \Delta n \Gammas . 3 We now introduce a
new complex variable z, and in each term we replace n \Gammas by e 2-inz . The result is a Fourier series
P a n e 2-inz that converges in the complex upper half-plane. We say that E is "modular" if this
Fourier series is a modular form, that is, if it satisfies a simple transformation rule when z is
replaced by (az d) for any integer matrix
c d
of determinant 1 with c j 0 (mod
is the "conductor" of the curve E; it is closely related to the curve's discriminant
D. 4 In order to know unconditionally that analytic continuation is possible and the critical value
L(E; 1) is defined, we need the curve E to be modular.
We're assuming that E has ``good reduction'' at l, i.e., that l does not divide the denominators of the
coefficients or the discriminant D of the curve. For brevity, we shall not discuss the modifications needed for the
"bad" primes l.
l is prime, then an is our earlier a l ; for composite n it is not hard to express an in terms of a l for
ljn.
In particular, N jD, and both N and D have the same prime divisors.
2.2 The Taniyama Conjecture
The Taniyama Conjecture is the assertion that all elliptic curves E over Q are modular. One
reason for its importance is that it guarantees that the Hasse-Weil L-function of E can be
analytically continued, and its behavior near can be studied.
It is for a different reason that most people have heard of this conjecture, namely, its connection
to Fermat's Last Theorem. In 1985 Gerhard Frey suggested that if A p +B were
a counterexample to Fermat's Last Theorem, then the elliptic curve
would have a very surprising property. Its discriminant would be
so every prime factor in this discriminant would occur to a very large power. Frey thought that
it would then have to violate the Taniyama Conjecture. K. Ribet was able to prove that Frey's
hunch was correct [24]; then, working intensively for many years, A. Wiles (partly in joint work
with R. Taylor) [37, 36] proved that no such curve can violate the Taniyama Conjecture, and
hence there can be no counterexample to Fermat's Last Theorem.
Wiles proved the Taniyama Conjecture for a broad class of curves - the "semi-stable" ones,
i.e., the ones whose conductor N is squarefree - but not for all curves. What he proved was
enough for Fermat's Last Theorem. But for a small class of curves that are not semi-stable it
is still a conjecture rather than a theorem that the Hasse-Weil L-function can be analytically
continued.
2.3 The Conjecture of Birch and Swinnerton-Dyer
As before, let E be an elliptic curve defined over Q, and let N l denote the number of mod-l
points. As l increases, suppose that we want to get an idea of whether or not N l tends to be
toward the right end of the Hasse interval [l
l], that is, whether or not
there tend to be more-than-average points on the curve. We might expect that if our original
curve over Q has infinitely many points - that is, if its rank r is positive - then these rational
points would be a plentiful source of mod-l points, and N l would tend to be large; whereas if
would straddle both sides of l This is the intuitive idea of the (weak)
Birch-Swinnerton-Dyer Conjecture [1, 2, 3].
To measure the relative size of N l and l as l varies, let us form the product
l
l
l
. Because
1, we can write this as
Y
l
l
Y
which is formally equal to the value at of the Euler product for L(E; s). We say "formally,"
because that product diverges, and the critical value is found by analytic continuation, not by
evaluating an infinite product.
Nevertheless, let us suppose that it makes sense to talk about this infinite product as if
it converged. One might expect that it would converge to zero if N l has a tendency to be
significantly larger than l, and would converge to a nonzero value if N l is equally likely to
be above or below l. And, indeed, the Birch-Swinnerton-Dyer Conjecture states that L(E; s)
vanishes at only if the rank r of the group of E over Q is greater than zero, and
that, moreover, its order of vanishing at is equal to r. The conjecture further says that
the leading coefficient in the Taylor expansion at can be expressed in terms of certain
number-theoretic invariants of E. Starting in 1977, a series of important partial results have
been proved in support of this fundamental conjecture (see [5, 6, 25]), but in its most general
form it remains a very difficult unsolved problem.
2.4 Heights
Let E be an elliptic curve (in Weierstrass form) over the field Q of rational numbers. Let
be a rational point on E (not the point at infinity). The logarithmic height of P is
defined by the formula h(P is written as a fraction in lowest
terms. The logarithmic height is closely related to the point's size in the computer-science sense
(i.e., its bit-length). 5
It can be shown that, if P is a point of infinite order, then h(nP ) grows quadratically with
n. That is, if you write out a list of the multiples of P , one on each line, the lengths of the lines
will increase proportionally to n 2 and so form a parabola. (For a picture of this in the case of
the elliptic curve Y and the point page 143 of [11].)
The logarithmic height, which has a roughly quadratic behavior, can be modified (this was
done by N'eron [23] and later simplified by Tate) in such a way that the resulting canonical
logarithmic height -
h(P ) is precisely a quadratic form. Namely, define
h(nP
The values of - h(P ) and 1
are close to one another - in fact, it can be shown (see p. 229 of
[29]) that their difference is bounded by a constant depending only on E - but it is the function
- h rather than h that has the nicer properties.
Suppose that the group E(Q) has rank r, i.e., the quotient group E(Q)=E(Q) tors is isomorphic
5 It would not make much difference if, instead, the logarithmic height were defined as log max(jaj; jbj; jcj; jdj),
lowest terms, or even as log 2
jabcdj, which really is (essentially) the number of bits needed to
to Z r . Let r be a set of generators. The formula
defines a positive definite inner product on the r-dimensional real vector space V obtained from
E(Q)=E(Q) tors by formally allowing the P i to have real (rather than just integer) coefficients.
This vector space can also be defined using the tensor product notation:
E(Q)\Omega R. Note
that E(Q)=E(Q) tors is a full lattice in V .
The regulator of E is defined as follows:
It is the square of the volume of a fundamental parallelepiped of the lattice E(Q)=E(Q) tors with
respect to our inner product. The real number R is an important constant attached to the
elliptic curve. In the Birch-Swinnerton-Dyer Conjecture, it appears as one of the factors in the
first non-zero Taylor coefficient of the expansion of L(E; s) at
3 Summary of the Algorithm
3.1 Simplified Version
We want to find an integer w such that
Working in projective coordinates, we choose two points e
P and e
Q with integer coordinates
whose residues modulo p are our points choose an elliptic curve E(Q)
that passes through e
P and e
Q and that reduces modulo p to the curve E(F p ).
Now suppose that e
P and e
turn out to be dependent in E(Q), that is,
e
e
in which case n 1 and n 2 can easily be found. If that happens, working modulo p we get
modulo the order of P in E(F p ); from this we can easily find w.
However, in general the probability that e
P and e
are dependent is very, very small. Silver-
man's idea is to increase this probability by imposing some conditions of the following type:
l
- that is, the reduction modulo l of E(Q) has relatively few points for all primes l,
(where
This idea was suggested by J. F. Mestre's success in obtaining curves of higher than expected
rank by imposing conditions in the opposite direction, i.e.,
l:
Both strategies (for obtaining either higher-than-expected or lower-than-expected rank) are based
on the heuristic argument for the conjecture of Birch and Swinnerton-Dyer (see x2.3), which says
that the rank of E(Q) is equal to the order of vanishing of L(E; s) at s = 1. Mestre's method
is to force the first several terms in the formal infinite product for L(E; 1) to be as small as
possible, whereas Silverman wants them to be as large as possible.
3.2 The Algorithm
We now describe the steps in the xedni algorithm [33].
Step 1. Choose an integer r with 2 - r - 9 (most likely 4 - r - 6), and integers L 0 - 7 and
Y
l prime; L 0 -l-L 1
l:
Also, decide whether you will be working with elliptic curves in general cubic form or in Weierstrass
form. In the first case, for any r-tuple of projective points
denote the (r \Theta 10)-matrix whose i-th row is
Then the r points lie on a given cubic curve with coefficients u only if the
column-vector u is in the kernel of the matrix B(P If, on the other hand, the elliptic
curve is given in the Weierstrass form 6
a
then we take B(P to be the (r \Theta 7)-matrix whose i-th row is
In this case the r points lie on the curve if and only if the vector (a 0 a 1 a 3 \Gamma a 0
is in the kernel of B(P
6 Since it is customary to write a i for the coefficients of the general Weierstrass equation, we shall also adhere
to this notation and hope that it does not lead to confusion with the use of a l (l prime) to denote l
which is also customary. Also note that usually one takes a however, we
want integer rather than rational coefficients, so it is useful to introduce a 0 and a 0
Step 2. For each ljM , choose r points P l;i in the projective plane over F l such that the matrix
r. Let PM;i denote a point modulo M that reduces to P l;i modulo l for
each ljM ; such a point can be found by the Chinese Remainder Theorem. If r - 4 and you're
working with the general form of a cubic (rather than Weierstrass form), for convenience and
slightly greater efficiency choose the first four points to be (1; 0; 0), (0;
Also choose a mod-M coefficient vector using Weierstrass form,
(a
that is in the kernel of the B-matrix for each ljM .
Choose the coefficient vector so that for each ljM the resulting cubic curve is an elliptic curve
(i.e., the discriminant is nonzero) with the fewest possible F l -points:
which is the smallest integer in the Hasse interval. This equality is called the "reverse-Mestre
condition" at l.
Remark 1. In some circumstances it might be better to allow a weaker reverse-Mestre condition,
and instead require only that
2.
Remark 2. Note that the condition that B have rank r implies that the P l;i must be distinct
points, and hence N must be chosen large enough so that this
inequality does not contradict the (weak) reverse-Mestre condition. For example, if
then one can choose L
Remark 3. When constructing the P l;i and coefficient vectors for the different small primes l,
some care has to be taken so as not to inadvertently cause the lifted points in Step 6 below to
automatically be independent. In cases when N l and N l 0 have a common factor - , there has to
be a certain compatibility between the images of the P l;i in the quotient group E(F l )=-E(F l )
and the images of P l 0 ;i in E(F l 0 )=-E(F l 0 ).
To illustrate in a simple situation, let us take suppose that N
in accordance with the reverse-Mestre conditions. Suppose that P
where a and b are integers modulo 7 and 21, respectively. (Here we are supposing that P 13;1 is not
the point at infinity, and P 31;1 is not a point of order 3.) Unless a j b (mod 7), the lifted points
are forced to be independent. To see this, suppose that we had a nontrival relation
of the form n 1 our lifted curve will almost certainly have no torsion points
(in particular, no points of order 7), we may suppose that 7 does not divide both n 1 and n 2 . If
we reduce this relation modulo 13 and 31, we obtain (n 1 +n 2 a)P
Hence and so a j b (mod 7).
Remark 4. The reason for requiring that the B-matrix have rank r for each ljM is that this is
precisely the condition that is needed in order to ensure that one can find coefficients for an
elliptic curve over Q that both passes through the lifted points and reduces modulo the primes
l and p to the curves E(F l ) (for ljM) and E(F p ) that we already have (see Step 7 below). This
is proved in Appendix B of [33]. Here we shall motivate the rank-r condition for the B-matrix
by giving an example in a simpler setting.
Suppose that r = 2, and we're working with straight lines in the projective plane, rather than
elliptic curves, so that the B-matrix is just
. Let l = 3. Suppose that we have
ignored the rank-r condition and over F 3 have chosen points P
and the straight line Suppose that we have lifted the points to Q as follows:
\Gamma1). We now want to find a lifted line (1
that reduces to and that passes through P 1 and P 2 . A simple calculation
shows that this is impossible.
Step 3. Let be the points in the discrete log problem; that is,
unknown integer w. Choose r random integer linear combinations of the two points
Our entire purpose in the algorithm is to find a linear dependency among the
If we succeed, then we immediately obtain the following congruence modulo the order of the
From this we can almost certainly solve for w (recall that in cryptographic applications the order
of P is usually a large prime).
Step 4. If r - 4, and if you want to look for a lifted elliptic curve in general cubic form (so that
have more coefficients to work with), then make a linear change of variables in the projective
plane over F p so that the first four points become
1). In that case we let u p;i , denote the coefficients of the resulting
equation for E(F p ).
Step 5. Use the Chinese Remainder Theorem to find coefficients u 0
modulo Mp that reduce
to u p;i modulo p and to uM;i modulo M , (Do the analogous thing with the a i
coefficients if you are working in Weierstrass form.)
Step 6. Lift the r points to the projective plane over the rational numbers. That is, for
choose points P coordinates that reduce to P p;i modulo
p and to PM;i modulo M . If r - 4 and you are working with the general form of a cubic, then
take the first four points to be
Step 7. Using the r points P i from Step 6, form the matrix B(P Find an integer
vector
(or an analogous vector of
a i 's if you've been working with curves in Weierstrass form). The rank-r condition on the mod-l
B-matrices ensure that we can do this. Try to find u so that the u i are as small as possible.
Step 8. If you've been working with the general equation of a cubic, make a linear change of
variables to bring it into Weierstrass form.
Steps 9-10 (optional). Modify the solution u in Step 7 by adding or subtracting vectors of the
form Mpv, where the vectors v are chosen from a basis of solutions to
coordinates. Choose a new solution u such that the discriminant of the curve with coefficients
small as possible. (Go through the analogous procedure with the a i if you've
been working with curves in Weierstrass form).
Also, let L be a constant of order about 200. For each curve compute the sum
l-L; l
a l
log l
l
If this sum is smaller than a pre-determined quantity (that is arrived at experimentally), discard
the curve and start over again with Step 2 or Step 3. Otherwise, continue to Step 11.
is based on an analytic formula for the rank of a modular curve that was proved by
Mestre [20]. (Notice that his formula can be used because of the Taniyama Conjecture, which
says that all elliptic curves over Q are modular.) In Mestre's formula the above sum appears as
a crucial term. Heuristically, it is plausible that the more negative this sum is, the more likely
the curve is to have large rank. Since we want smaller-than-expected rank, we might want to
throw out curves for which the sum is highly negative.
Step 11. Finally, test the points for dependence. There are at least two efficient methods of
doing this (see [33]). If they are independent, return to Step 2 or Step 3. If they are dependent,
it is not hard to find the coefficients of a relation. As explained in Step 3, it is then very easy to
find the discrete logarithm x. This completes the description of the algorithm.
4 Asymptotic Failure of the Algorithm
The purpose of this section is to prove
Theorem 4.1. Under certain plausible assumptions (see the lemma below), there exists an absolute
constant C 0 such that the probability of success of the xedni algorithm in finding a discrete
logarithm on an elliptic curve over F p is less than C 0 =p.
Unfortunately, C 0 is rather large, so this result does not immediately resolve the question of
practicality of the algorithm. We address that question in the next section.
Recall the notion of the canonical logarithmic height - h(P ) (see x2.4). Given an elliptic curve
having infinitely many rational points, let m denote the minimum of - h(P ) for all non-
torsion points P 2 E(Q). Let D denote the discriminant of E. Then a conjecture of Lang (see
p. 92 of [12] or p. 233 of [29]) states that there exists a positive absolute constant C 3 such that
log jDj. This conjecture was proved for a large class of curves in [27, 8], but it has not
yet been proved unconditionally for all curves over Q.
Lemma 4.1. Assume that log jDj - C 1 for the lifted curves in the xedni algo-
rithm, where D is the discriminant of the lifted curve, P i are the lifted points, -
h is the canonical
logarithmic height, and C 1 is a positive absolute constant. 7 Then, under Lang's conjecture, if the
lifted points are dependent, then they satisfy a nontrivial relation with coefficients bounded from
above by an absolute constant C 2 .
Proof. Following [34], we estimate the number of points of E(Q) - more precisely, the number of
points in the subgroup E 0 spanned by the lifted points whose canonical logarithmic
height is bounded by a constant B. Suppose that the P i are dependent, and let r
the rank of E 0 . Let T 0 denote the number of torsion points in E 0 . (In practice, almost certainly
and by a famous theorem of Mazur [16] always
0\Omega R, and let
R 0 denote the regulator of E 0 , i.e., R
r 0 are a basis for
tors . Finally, we define
To estimate N(B), one uses standard results from the geometry of numbers. According to
Theorem 7.4 of Chapter 5 of [13],
is the volume of the r 0 -dimensional unit ball:
7 Roughly speaking, this condition says that the discriminant of the lifted curve is greater than the C 1 -th power
of the maximum absolute value of the numerators and denominators of the coordinates of the lifted points, for
some absolute constant C 1 ? 0. This is a reasonable assumption, since the discriminant is a polynomial function
of the coefficients of the curve, and the coefficients tend to grow proportionally to a power of the integer projective
coordinates of the points through which the curve must pass.
It follows from Corollary 7.8 of Chapter 5 of [13] that
where, as before, m denotes the smallest positive value of - h on E(Q) (actually, we could replace
m by the smallest positive value of - h on E 0 ). If we combine these relations and denote
we obtain
Now let M denote the maximum of - h(P i
- h is a metric, the height of
any integer linear combination of the P i with coefficients n i bounded by 1
will be
chosen later) is bounded as follows:
If we substitute
2 M in our inequality for N(B), we find that the number of points
that
i.e., the number of points that satisfy the above inequality for the height, is
less than
But the number of linear combinations
very close to C r
2 . If
then there must be two different linear combinations that are equal, and so the points P i satisfy
a nontrivial linear relation with coefficients bounded by C 2 .
We now use the assumptions in the lemma. By Lang's conjecture, m - C 3 log jDj. Since we
also assumed that log jDj - C 1 M for some positive absolute constant C 1 , we have
Dividing the previous inequality through by C r 0
2 , and using the fact that r 0 - r \Gamma 1, we find that
it suffices to have
and there are only finitely many possibilities for r, namely, 2 - r - 9, this is an
absolute constant. The lemma is proved.
We now show how the theorem follows from the lemma. The point is that any relation among
the lifted points P i can be reduced modulo p to get a relation with the same coefficients among
the original r points P p;i that were constructed at random in Step 3. However, it is extremely
unlikely that r random points on E(F p ) will satisfy a linear relation with coefficients less than a
constant bound. In fact, using a pigeon-hole argument, one can show that the smallest value of
that is likely to occur for the coefficients in a relation is of order O(p 1=r ). If the points
P p;i in Step 3 do not satisfy a relation with coefficients less than the bound in the lemma, then no
amount of work with Mestre conditions is going to enable one to lift them to dependent points.
To make the argument more precise, consider the map from r-tuples of integers less than
absolute value to E(F p ) given by (n . The image is
a set of - (2C 2 ) r randomly distributed points. The probability that the image contains 0 is
approximately This proves the theorem with
Unfortunately, the certain failure of the algorithm for large primes p does not rule out its
practicality for p of an "intermediate" size, such as After examining about 10000 curves,
Silverman [27] was able to bound the constant C 3 in Lang's conjecture as follows: C 3
That circumstance alone contributes a factor of at least 2000 (r\Gamma1)=2 to the constant C 2 in the
lemma, and at least 2000 r(r\Gamma1)=2 to the constant C 0 in Theorem 4.1. In any case, it is now clear
that Silverman was correct to choose r ? 2. If r were equal to 2 (as in the "simplified version"
in x3.1), then C 2 could be chosen much smaller, and our theorem would apply to p of more
moderate size.
This situation is very unusual. We know, subject to various reasonable conjectures, that
for sufficiently large p the xedni algorithm must be repeated at least O(p) times (with different
choices of r points in Step 3) in order to find a discrete logarithm. In other words, asymptotically
it is far slower than square-root attacks. However, because of the constants involved, this result
does not necessarily imply that the algorithm is inefficient for p in the range that arises in
practical cryptography.
4.1 Estimate of the Constant in Theorem 4.1
In order to get a very rough estimate for the constant C 0 in Theorem 4.1, we shall make the
following assumptions:
ffl The constant C 3 in Lang's conjecture is no less than 1=10 of the upper bound in [27], i.e.,
ffl For one uses the Weierstrass form of the equation of the elliptic curve with
8 On the other hand, it is known (see [8, 27]) that in order to get a very small value of C 3 , it is necessary
that the discriminant D be divisible by many primes to fairly high powers. However, from the way they are
constructed, the xedni curves tend to have discriminants that are square-free or almost square-free.
7 variable coefficients. We suppose that the ratio of length of the coefficients to length of the
coordinates of the r points is given by a formula derived from Siegel's Lemma, as in Appendix
J of [33], namely, 1 r). We further suppose that the length of the discriminant is 12
times the length of the coefficients.
ffl For one uses the general equation of a cubic, which has 10 variable coefficients.
We suppose that the ratio of lengths of coefficients to coordinates is now 1


Appendix

J of [33]). In accordance with computations of Silverman (see Appendix C of [33]), we
also assume that the length of the discriminant is 110 times the length of the coefficients.
ffl The curves over Q have no nontrivial torsion points, as one expects to happen in the vast
majority of cases.
We now use the bound in the proof of Theorem 4.1:
are determined according to the four assumptions above, i.e.,
respectively. Here is the result:
r very rough value for C 0
We conclude that for Theorem 4.1 rules out the use of the algorithm with r - 5,
but not necessarily with 9. Nevertheless, in our experimental work, where the primes
were much smaller, we took in order to investigate the probability of dependence, the
effect of reverse-Mestre conditions, and other issues.
Note that when 50 we can expect to be working with elliptic curves over Q whose
discriminants have at least 10000 decimal digits when 9. This
obviously casts doubt on the feasibility of the computations in the algorithm. We shall explore
the practicality question in more detail in the next section.
Remark 5. Our estimate for C 1 might be too high, because sometimes one can obtain smaller
coefficients and discriminants using lattice-basis reduction and other methods. On the other
hand, the value we are using for C 3 is almost certainly too low; so it is reasonable to hope that
our value for the product C 1 C 3 is about right.
5 Empirical Analysis in the Practical Range
To get a practical estimate of the probability of success of the xedni algorithm, we did several
experiments, including an implementation of the algorithm itself. All experiments were carried
out using the computer algebra systems LiDIA [14] and SIMATH [38]. We began with a couple of
preliminary computations. The purpose of this was to obtain some insight into which parameters
have an impact on the probability of dependence. Our strategy and the size of parameters were
chosen with the aim of producing a significant number of dependencies. We tried to keep the size
of the curve coefficients, and hence the size of the discriminant, as small as possible. We worked
with points through which the curve was made to pass, and we did not impose
any reverse-Mestre conditions. The data obtained through these experiments already suggested
that most likely the xedni algorithm has a negligible probability of success. However, to be more
confident of this statement, we implemented the algorithm. It turned out that the probability
of success was small even for 8-bit primes.
5.1 A First Approach
5.1.1 The experiment
For each value curves were generated as follows. First, r affine points
randomly selected with integers jx i j and jy i j bounded by 40 when
4, such that the points had pairwise distinct x-coordinates and
none of them was the point at infinity. The points were discarded if any three of the r points
were collinear. Note that if three points P , Q and R are collinear and E is an elliptic
curve passing through these points, then P independently of E. Second,
the five coefficients a i of a curve in standard Weierstrass form (with a
were selected so that the curve passed through the r points and the coefficients were small. If
there was no solution with integer coefficients, the points were discarded. Third, the curve (and
points) were discarded if the curve had the same j-invariant as an earlier curve. Fourth, the
same was done if any of the r points were torsion points or if the curve had nontrivial 2-torsion.
Finally, in the cases the discriminant was greater than 2 80 , that case was also dis-
carded. The reason for this was that in preliminary experiments we were unable to find a single
case of dependency with discriminant greater than 2 72 , and we wanted to avoid a lot of fruitless
computation.
In all cases we computed the discriminant and the number of mod-l points for 7 - l - 97. A
2-descent (see [33], Appendix D) was used to check dependence. When the points were dependent,
the dependency relation with smallest coefficients was determined.
w.dep.pts.
#dep:
total#
R 3 R 4 R 5
50 3079 133 0.043 4493.75 250.22 13.93

Table

1: 4: Probability of dependence
5.1.2 Results
Among the 200000 examples considered for each 4, we found 2895, 21165 and 10698
dependent cases, respectively. For each value of each bit-length of the discriminant
D, the proportion of dependent cases (i.e., the probability of dependence) was tabulated and
compared with various fractional powers of the discriminant. The data suggest that when
the probability of dependence is bounded, respectively, by 5jDj \Gamma1=4 , 66jDj \Gamma1=4 , 322jDj \Gamma1=4 .
Some explicit results for are given in Table 1. Here column A is the bit-length of the
discriminant; to keep the table small, we restrict ourselves to listing the data for discriminants
of bit-length 5k, k - 1, and for the largest discriminants. Column B is the number of example
curves having discriminant of bit-length A. Column C is the number of these curves for which the
four points are dependent. The fourth column is the proportion C=B of dependencies. The last
three columns show the values of R 5. Thus, R e is approximately
equal to the e-th root of the discriminant times the fraction of examples where the points were
The average value of
a l log l
l for respectively, \Gamma4:401, \Gamma6:163, \Gamma8:108
for all curves and \Gamma2:227, \Gamma4:336, \Gamma6:597 for the dependent cases. In other words, very roughly
it was equal on average to \Gamma2(rank of curve).
We also looked at the reverse-Mestre conditions for 7 - l - 97. Of the 22 values of l, no
curve satisfied more than 3 reverse-Mestre conditions. The dependent cases had significantly
more likelihood than the independent cases of satisfying these conditions - but still not a large
probability. When 4, for example, 17 out of the 10698 dependent cases (about 0:16%) satisfied
2 or 3 reverse-Mestre conditions, whereas only 156 out of the 189302 independent cases (about
0:08%) did. In both cases, this proportion was far less than one expects for a random curve.
The reason is that, since the curves were constructed to pass through r points, they generally
had higher rank, and hence in most cases more mod-l points, than an average curve. We also
compiled statistics on the number of 'reverse-Mestre+1' and `reverse-Mestre+2' conditions (i.e.,
N l is l
l] +1 or l
the results were similar to what we found
for the pure reverse-Mestre conditions. For example, when 4, out of the 10698 dependent
cases there were 83 cases when 2 or 3 reverse-Mestre +1 conditions held (none with ? 3), and
there were 148 cases when 2 or 3 reverse-Mestre +2 conditions held (none with ? 3). Out of the
independent cases there were 703 cases with 2 or 3 reverse-Mestre +1 conditions (none
with ? 3) and 1555 with 2 or 3 reverse-Mestre +2 conditions (2 with ? 3).
Most remarkably, the coefficients in the dependency relations were very small. When
over 98% of the coefficients were 4 or less in absolute value, and no coefficient was greater than
8. When 99:75% of the coefficients were 3 or less in absolute value, and no coefficient
was greater than 13. When r = 4, over 99% of the coefficients were 2 or less in absolute value,
and no coefficient was greater than 8. This is much less than the theoretical bound C 2 derived
in the previous section.
5.2 A Second Approach
While doing experiments similar to those described above, we found an interesting effect when
we tried to mix our bounds on the coordinates. Namely, at one point (with we tried to
add to our sample 100000 examples for which the absolute values of the coordinates of the 3
points were between 31 and 50 (rather than between 0 and 30). The large proportion of cases
that led to large discriminants were discarded, leaving only the examples with smaller-than-
average discriminants. In that situation there was a significant increase in the probability of
dependence (roughly by a factor of 4) for fixed bit-length of the discriminant. This suggests
that the probability depends not only on the size of the discriminant, but also on how this size
relates to the logarithmic heights - h(P i ) of the lifted points. In particular, the probability of
dependence seems to be significantly greater for curves whose discriminants are much smaller
than the median.
In a second series of experiments we took advantage of this phenomenon. Here we also were
interested in the distribution of the discriminants of curves forced to go through r random points
whose coordinates were chosen to lie within certain ranges.
5.2.1 The Experiment
In this series of experiments we worked with whose coordinates x
so that
where
Initially, we planned to take but we ended up working with
For each such value of k,
100000 curves were generated in the way described above. Besides the modified bounds on
the coefficients, the only difference was that we used the homogeneous Weierstrass form with 7
coefficients, computed an LLL-reduced basis ~v of the kernel of the matrix B(P
and then chose a solution vector ~u from the set fe 1 such that the
discriminant of the corresponding curve is minimal. For each k, out of the 100000 curves only
the 1000 with smallest discriminant were examined for dependency. Thus, about 8 million curves
were generated, and 1% of them were examined for dependency. For each k, we also looked at
the distribution of the 100000 discriminants.
5.2.2 Results
The distribution of the bit-length of the discriminant was very similar for different ranges of k.
It was not exactly a normal distribution - in particular, the mode was a few bits larger than
the median, which was a few bits larger than the mean. The ratio of the standard deviation to
the mean was 0:22 for all k - 11 and between 0:25 and 0:23 for 1 - k - 10. As a function
of k, the median was very close to 23 log 30. The largest bit-length of discriminant for the
bottom 1% was consistently 48% or 49% of the median bit-length, i.e., about 11:5 log
For example, for the smallest 1% of the curves had discriminants of bit-length between
22 and 92, while for the range was 24 to 81 bits, and for 3000 the range was 63 to
bits.
In general, there was a much greater probability of dependence than in the previous exper-
iment. For example, for the probability of dependence was about 30% for
discriminants of - 40 bits, it was about 5% for discriminants in the 60-bit range, and it dropped
off gradually to about 1% for discriminants of ? 90 bits. For the larger values of k, where most
of the smallest 1% of discriminants had more than 100 bits, we also found many dependent
cases. For example, for there were 35 dependent cases among the 998 curves with
discriminants of ? 100 bits, the largest of which was for a 151-bit discriminant. This contrasts
dramatically with the earlier data, when the coordinates of the P i were much smaller and the
discriminants of ? bits came from the middle and high range of discriminants; in that case we
did not find a single dependency among the vast number of cases of discriminant ? 2 72 . More-
over, the probability of dependence was no longer bounded by const \Delta jDj \Gamma1=4 . Hence, having
1000 1000
3000 1000 36 1 143 -

Table

2: The coefficients of the dependency relations
smaller than expected discriminant helps force the points to be dependent.
However, when we examined the sizes of the coefficients in the dependency relations, we
realized that it was the very small size of these coefficients, rather than the small probability
of dependence for large jDj, that would be the most serious obstacle to the xedni calculus.
These coefficients tended to be as small or smaller than in the previous experiment. Moreover,
the chance of finding a dependency coefficient other than 1; \Gamma1; 0 drops significantly as the
discriminant grows. For example, for k ? 32 we encountered no coefficients of absolute value
greater than 3. In Table 2 we give the distribution of the dependency coefficients. The first
column is the range of k-values; the second column is the number of curves examined (i.e., 1000
times the number of k-values in the range); the third column is the number of dependent cases.
The i-th column after the double line is the number of dependency coefficients of absolute value
(thus, the sum of all of these columns is equal to 4 times the third column).
Out of the 27 dependent cases for relations were of the form P 1
For out of 41 relations were of this form, and for was the case for 31 out
of 36 relations. Note that the probability of getting this relation is simply the probability that,
when one passes a curve through the four points, it also passes through the point of intersection
of a line through two of the points with the line through the other two. Although there is a
significant chance of this happening even when k is large, this type of relation with coefficients
\Sigma1 is not useful for solving the ECDLP, where the coefficients will be large.
We also wanted to see if the data could have been affected by the particular way we generated
the points (especially, the narrow range of jx i j and the fact that jy i j was so close to jx i j 3=2 ). So
we returned to a range roughly similar to
In each case we generated
100000 examples and examined the bottom 1%. This time the discriminants were much larger
than before (up to 162 bits in the first case and up to 125 bits in the second case), presumably
because LLL had been able to find much smaller coefficients when jx very close to jy
Out of 1000 curves there were, respectively, 14 and 50 dependencies, of which ten and eight were
of the form Once again there were no coefficients other than 1; \Gamma1; 0.
5.3 Preliminary Conclusions
our experiments showed the following. First, the probability of dependence drops off
with increasing bit-length of the discriminant, but this drop-off depends on more than just the
bit-length. Another factor is the ratio of the actual size of the discriminant to the expected size.
Second, reverse-Mestre conditions are more likely to be satisfied in the dependent cases
than in the independent cases. What is the probability of dependence given that reverse-Mestre
conditions hold for a few small primes? Such data cannot be extracted from our experiments.
For example, in the first experiment (with 200000 curves) and in the second experiment (with
10000 curves of relatively small discriminant and we checked for reverse-Mestre
conditions and reverse-Mestre +1 conditions for l = 7, 11 and 13. We found that in none of the
cases, dependent or independent, were any two such conditions satisfied simultaneously.
Third, the small sizes of the dependency coefficients seemed to cast doubt on the practicality
of the xedni algorithm. At this point we did not yet have data reflecting the situation of
ECDLP, where we deal with points whose smallest relation is necessarily fairly large. What is
the probability that are dependent, given that we know a priori that any relation they
satisfy must have moderately large coefficients?
5.4 Experiments with the Xedni Algorithm
To answer the questions raised above, we implemented the xedni algorithm. The size of the
parameters was chosen so that we had a reasonable chance of finding some dependent cases.
For different experiments, which can be classified as
follows: (A) no reverse-Mestre conditions imposed; (B) reverse-Mestre conditions imposed for
two small primes whose product M is of approximately the same size as p; (C) instead of p work
with conditions imposed but with p 0 taken to be of the same
magnitude as the product Mp in (B).
In the context of an actual ECDLP, this means that both Experiments A and B would be used
to solve the same ECDLP but with different strategies. That is, the reverse-Mestre conditions
in Experiment B would presumably contribute to a greater likelihood of dependency, but at the
expense of much larger discriminants (which would work against dependency). Experiment C, on
the other hand, would be used to solve an unrelated instance of ECDLP, but the discriminants
in Experiment C are of similar size to those in Experiment B. Comparing Experiments A and C
with Experiment B, we should be able to judge whether the reverse-Mestre conditions are helpful
enough to compensate for the larger discriminants.
Let us describe Experiment B with in detail. We chose a 28. Then the
curve points. We chose as a generator for
E(F p ). Next, we chose and we chose PM;i , 4, to be the four points
on the mod-M curve y 8. Note that
the numbers of points mod 7 and 11 are, respectively, 5 and 6. In each case the B-matrix has
rank 4; and since the numbers of points for different l are relatively prime there is no worry
about incompatibility and forced independence. Using the Chinese Remainder Theorem, we
then compute a; b with \Gamma77p=2 ! a; b ! 77p=2 to be congruent to a and congruent to
77. Hence a = 1541 and the steps are repeated 100000
times.
1. For any vector n 2 FN 4 define knk 2 to be
, where the coordinates n i of n are taken in
the interval \GammaN=2
is chosen so that -
orthogonal to -. This means that we do not allow the P i to satisfy a relation with all
coefficients 0; 1; \Gamma1.
2. For each use the Chinese Remainder Theorem to choose to be congruent
to the coordinates of P p;i mod p and to those of PM;i mod 77. Now choose
in projective coordinates by finding a short vector in the lattice generated by the columns
of the matrix 0
subject to the condition that Z i is not divisible by 7, 11, or p.
3. Solve for small integers u i such that the curve E(Q) with equation
4, and has minimal discriminant. Here we use
the techniques described in Steps 7 and 9 and Appendix B of [33], including the Havas-
Majewski-Matthews Hermite normal form algorithm [7].
4. Finally, check whether the P i are dependent. In case of dependency, compute the dependency
relation with smallest coefficients.
Experiment A differs from Experiment B only in that 1. For the corresponding
Experiment C, we chose 946). The curve
dependent cases
bits 131 bits 73 bits 317 23 bits 91 bits 61 bits
bits 273 bits 182 bits 3 140 bits 151 bits 144 bits
bits 257 bits 148 bits 153 59 bits 170 bits 114 bits

Table

3: Experiments A, B, C (100000 examples of
For Experiments A and B with chose a 2. Then the
curve points. We chose We
worked with chose PM;1 and PM;2 to be the two points (5; \Sigma2) on the
mod-M curve y 14. The number of points is 3 both mod 3 and mod 5. The
fact that P guarantees that we do not force the lifted points to be
independent. Chinese Remaindering gives coefficients \Gamma119, 121 and 104. Hence, in Experiment
A we work with the curve y while in Experiment B we work with the
curve 255. For Experiment C we chose
20). The curve y points. Note
that since we work with only two points, the vectors n and - of Step 1 above are vectors in FN 2 .
The only conditions imposed on P p;i are that they are not the point at infinity and
5.4.1 Results
Among the 6 series of 100000 executions of Steps only in 3 series did we obtain any
dependencies. This was in Experiment A with and in Experiment B with
are shown in Table 3.
The data show that, given an instance of the ECDLP - i.e., a fixed value of p - we are
more likely to produce dependent cases if we do not impose reverse-Mestre conditions. When
deps.

Table

4: Experiments A: coefficients
we work with discriminants of approximately the same size - i.e., with variable p but fixed size
of Mp - the different outcomes of Experiment B when Experiment C when
might be interpreted as evidence that imposing reverse-Mestre conditions has a
significant impact. However, the three relations in Experiment B are all of the form P
Notice that once one of the two points mod p is chosen, there are N \Gamma 3 possibilities
for the other one, and the probability that the two points satisfy a dependency with coefficients
in Experiment C. (Note that in
Experiment B the coefficients n 1 , n 2 must satisfy the congruence
that is why the numerator above N \Gamma 3 is 2 rather than 4 in
Experiment B.) Our experience has been that it is much more likely that a relation of the form
can be lifted than that a relation with larger coefficients can be lifted. Thus,
the greater likelihood of dependency in Experiment B than in Experiment C might have little or
nothing to do with the reverse-Mestre conditions. 9
Looking at the relations in the Experiments A, we find that the great majority have coefficients
\Sigma2. The sizes of the coefficients are shown in Table 4. As in Table 2, the i-th
column after the double line shows the number of dependency coefficients of absolute value
We see that the coefficients are very small.
Furthermore, 301 out of the 317 relations for were of the form P
. Out of the remaining 16 relations, only 6 have both coefficients larger than 1. For
out of the 153 relations were of the form P were of the form P
and 9 were of the form P . Out of the remaining 14 relations, six have two
coefficients larger than one.
9 There is a reason unrelated to the heuristics of the Birch-Swinnerton-Dyer Conjecture why, among the
conditions that one might impose modulo l, ljM , the reverse-Mestre conditions are the ones that are most likely
to produce dependencies. Note that the mod-l conditions lead to congruences that the dependency coefficients
must satisfy. These congruences are likely to be more restrictive if N l = #E(F l ) is larger. For example, we saw
that the reverse-Mestre conditions in Experiment B led only to the constraint that
has a small nontrivial solution \Gamma2. Suppose that we had instead chosen our mod-l curves and points
so that N are "average" rather than reverse-Mestre values) and P
Then any dependency coefficients must satisfy 7). One can check that
the smallest (in the sense of knk) nonzero solution to these congruences is \Gamma4. It is far, far harder
to find dependencies with both than it is to find dependencies with
6 Conclusion
Xedni calculus is impractical for p in the range used in elliptic curve cryptography. In the first
place, the basic properties of the canonical logarithmic height, along with a pigeon-hole argument,
show that the coefficients in a dependency relation among the lifted points are bounded by an
absolute constant. This implies an asymptotic running time of at least O(p). In a sense, xedni
fails asymptotically for much the same reason that index calculus is infeasible (see [21, 34]). In
the second place, even if liftings exist with dependency among the points, the probability of
finding such a lifting decreases as the discriminant grows, and it becomes very low by the time p
reaches the practical range. In the third place, empirical data show that the theoretical bounds
on the size of the dependency coefficients are far too generous compared to what happens in
practice; and for high discriminants it is virtually impossible to find dependencies where the
coefficients cannot be taken to be of trivial size (usually \Sigma1). Finally, although, in the absense
of other considerations, the reverse-Mestre conditions do increase the likelihood of dependency,
they also cause the discriminant to increase substantially, and so most likely the net effect is to
do more harm than good.



--R

Notes on elliptic curves I and II

Diophantine equations with special reference to elliptic curves
Analogue of the index calculus for elliptic discrete logarithm
On the conjecture of Birch and Swinnerton-Dyer
On the Birch and Swinnerton-Dyer conjecture
Extended GCD and Hermite normal form algorithms via lattice basis reduction
The canonical height and integral points on elliptic curves

Introduction to Elliptic Curves and Modular Forms
Algebraic Aspects of Cryptography
Diophantine Analysis
Fundamental of Diophantine Geometry
LiDIA Group
Specializations of finitely generated subgroups of abelian varieties
Modular curves and the Eisenstein ideal
Elliptic Curve Public Key Cryptosystems
Handbook of Applied Cryptography
Construction d'une courbe elliptique de rang - 12
Formules explicites et minoration de conducteurs de vari'et'es alg'ebriques
Use of elliptic curves in cryptography
Propri'et'es arithm'etiques et g'eom'etriques attach'es

On modular representations of Gal(Q

Nonsingular plane cubic curves
Lower bound for the canonical height on elliptic curves
Divisibility of the specialization map for families of elliptic curves
The Arithmetic of Elliptic Curves
Computing heights on elliptic curves
Advanced Topics in the Arithmetic of Elliptic Curves
Computing canonical heights with little (or no) factorization
The xedni calculus and the elliptic curve discrete logarithm problem
Elliptic curve discrete logarithms and the index calculus
Rational Points on Elliptic Curves

Annals of Math.
SIMATH Manual
--TR
Nonsingular plane cubic curves over finite fields
Computing canonical heights with little (or no) factorization
Algebraic aspects of cryptography
The Xedni Calculus and the Elliptic Curve Discrete Logarithm Problem
Handbook of Applied Cryptography
Use of Elliptic Curves in Cryptography
Elliptic Curve Discrete Logarithms and the Index Calculus

--CTR
Joseph H. Silverman, The Xedni Calculus and the Elliptic Curve Discrete LogarithmProblem, Designs, Codes and Cryptography, v.20 n.1, p.5-40, April 2000
Neal Koblitz , Alfred Menezes , Scott Vanstone, The State of Elliptic Curve Cryptography, Designs, Codes and Cryptography, v.19 n.2-3, p.173-193, March 2000
Andrew Odlyzko, Discrete Logarithms: The Past and the Future, Designs, Codes and Cryptography, v.19 n.2-3, p.129-145, March 2000
xedni calculus;discrete logarithm;elliptic curve