6
$\begingroup$

According to my understanding there are some pretty solid seeming roadblocks to carrying out an index calculus on an elliptic curve over a finite field. The general strategy is to take points over $E(\mathbb{F}_p)$, lift them to points over $E(\mathbb{Q})$, and then hope that the curve over $\mathbb{Q}$ has high rank. The two major obstructions seem to be

  1. It is very hard to find elliptic curves over $\mathbb{Q}$ with high ranks, and

  2. It is highly unlikely to find a reasonable factor basis - that is, a collection of points on the curve with a bounded height.

This approach assumes that we lift the problem to one over the rationals $\mathbb{Q}$. I was wondering if anyone has any idea whether such an algorithm could be carried out by lifting the curve to an elliptic surface, i.e. an elliptic curve over the function field $\mathbb{F}_p(T)$ of some curve? At the very least we seem to know more about how the ranks of these things behave better than in the number field case.

I am not sure what I am asking even makes sense, so an explanation of its nonsense is welcome as well.

|improve this question
$\endgroup$
  • 1
    $\begingroup$ It is unlikely field of rational numbers is relevant in cryptography. "Lifting" sounds like reducing original problem of solving discrete logarithm for elliptic curve points to another problem in multiplicative group in some extension field. $\endgroup$ – Vadym Fedyukovych Nov 12 '16 at 9:51
  • 1
    $\begingroup$ @Vadym: Think at the number field sieve. $\endgroup$ – user27950 Nov 14 '16 at 6:45
  • $\begingroup$ Lifting in this sense is not lifting to an extension field, it is taking the problem to another field having the original base as a quotient in order to somehow take advantage of unique factorization in some ring of integers. $\endgroup$ – rondo9 Nov 14 '16 at 10:24
  • $\begingroup$ Probably related mathoverflow.net/questions/61055/… $\endgroup$ – Vadym Fedyukovych Nov 14 '16 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.