How hard is Discrete Logarithm, really? (Joux's Algorithm)

[R.D. Silverman]

Originally Posted by CRGreathouse

It looks like it is practical, yes:
http://arxiv.org/abs/1402.3668

Nice work. However, I have to fetch and read the full paper.

Superficially the summary says:

" Menezes, Oliveira and Rodr\'iguez-Henr\'iquez analysed the concrete security of the DLP, as it arises from pairings on (the Jacobians of) various genus one and two supersingular curves in the literature"

so this appears to work for the Weil [presumably?] pairing on
elliptic curves as well as over ordinary finite fields.

It is unclear to me (or maybe I am having brain damage) whether this
carries over to the general ECDL problem with fields of small characteristic.


I'd also like to see some data on Joux's result applied to ordinary large
FF of small characteristic.

[R.D. Silverman]

Originally Posted by R.D. Silverman

Nice work. However, I have to fetch and read the full paper.

Superficially the summary says:

" Menezes, Oliveira and Rodr\'iguez-Henr\'iquez analysed the concrete security of the DLP, as it arises from pairings on (the Jacobians of) various genus one and two supersingular curves in the literature"

so this appears to work for the Weil [presumably?] pairing on
elliptic curves as well as over ordinary finite fields.

It is unclear to me (or maybe I am having brain damage) whether this
carries over to the general ECDL problem with fields of small characteristic.


I'd also like to see some data on Joux's result applied to ordinary large
FF of small characteristic.

Note that these results arise from pairing on an EC which means that the
extension degree is composite. Has anyone heard of similar results for
the DL over GF(2^p) for prime p?

Note that the result does not have a large impact on practical crypto;
Pairing based methods are very sparsely used [if at all; I don't know of
any serious implementations]. Note that the Weil pairings arise in
Boneh's identity based keys. If anyone knows where this is being used
I would love to hear about it.

[Ken_g6]

Originally Posted by R.D. Silverman

Are you too lazy to read it yourself?

I went to this HAL site to look for it, but I don't speak a lick of French, so I didn't bother. Thanks, Phil, for finding it. I'm glad the paper's not in French.

Originally Posted by CRGreathouse

It looks like it is practical, yes:
http://arxiv.org/abs/1402.3668

So, if I understand this correctly - and I probably don't even have the terminology right - it's only practical for a cyclic group of order ~128 bits or larger? I was hoping for 40-64 bit fields for something like srsieve.

[R.D. Silverman]

Originally Posted by Ken_g6

So, if I understand this correctly - and I probably don't even have the terminology right - it's only practical for a cyclic group of order ~128 bits or larger?

False. Where did you get this idea?

I was hoping for 40-64 bit fields for something like srsieve.

ANY method, even purely exponential ones will solve 40-60 bit fields
in very short order. Try Shanks' or Pollard's methods.

Stop relying on black boxes (srsieve) and learn some math!

[CRGreathouse]

Originally Posted by R.D. Silverman

I'd also like to see some data on Joux's result applied to ordinary large
FF of small characteristic.

Agreed. But it's a bit early to expect anything -- I'm surprised even this paper was out so soon.

[R.D. Silverman]

Originally Posted by CRGreathouse

Agreed. But it's a bit early to expect anything -- I'm surprised even this paper was out so soon.

It appears that the Eurocrypt 2014 paper by Razvan Barbulescu1, Pierrick Gaudry1, Antoine Joux and Emmanuel Thomé answers my questions....

Ordinary discrete logs over small characteristic fields must be considered broken.

[R.D. Silverman]

Originally Posted by R.D. Silverman

It appears that the Eurocrypt 2014 paper by Razvan Barbulescu1, Pierrick Gaudry1, Antoine Joux and Emmanuel Thomé answers my questions....

Ordinary discrete logs over small characteristic fields must be considered broken.

Additional questions include:

Can one adapt the DL over K = GF(2^n) to factoring #K (== 2^n-1)?

[Batalov]

Do you suspect that this is related to the famous reservation?

[Ken_g6]

Originally Posted by R.D. Silverman

False. Where did you get this idea?



ANY method, even purely exponential ones will solve 40-60 bit fields
in very short order. Try Shanks' or Pollard's methods.

Stop relying on black boxes (srsieve) and learn some math!

By "practical" I meant "faster than srsieve's BSGS on a CPU". "Very short order" is relative.

I have looked at Pollard's method for a potential GPU sieve, because of its low memory usage. But apparently its runtime can fluctuate wildly, meaning it's not a fully straightforward port. (Which doesn't mean it can't be done; just I don't feel like devoting the time to do it.)

I found the algorithm in the paper, but it's not clear enough to me for me to write code from it yet.

[R.D. Silverman]

Originally Posted by Batalov

Do you suspect that this is related to the famous reservation?

It is something that I am investigating personally. (in my less than copious free time)

Note, however, that I am not nearly as talented (by far!) as Joux, Kleinjung et.al. as a
research mathematician.

[R.D. Silverman]

Originally Posted by R.D. Silverman

It is something that I am investigating personally. (in my less than copious free time)

Note, however, that I am not nearly as talented (by far!) as Joux, Kleinjung et.al. as a
research mathematician.

BTW, an initial answer appears to be YES, it can be done. (seemingly)

Consider solving, e.g. 3^x = 1 over GF(2^n). If x is even, there is a
chance of finding a non-trivial sqrt(1) mod 2^n-1, hence splitting 2^n-1.


Whether/how it is applicable to prime n is still unclear to me.