[Cryptography] New attacks on discrete logs?

[Alec Edgington]

On 23/05/14 22:03, Bear wrote:
> On Thu, 2014-05-22 at 11:14 +0200, Hanno Böck wrote:
> 
>> Okay, to clear this up:
>> There's been an algorithm improvement on discrete logs in so-called
>> finite fields with small characteristics. However, it's not that "new",
>> it's from early 2013, it just has been presented at the eurocrypt
>> conference recently.
> 
> Would anyone like to clarify what exactly they mean by 
> "small" and "large" characteristic here?  Please?

Since we're talking about asymptotic complexity, 'small' and 'medium'
don't refer to actual sizes. Say the finite field is of order N = p^k;
we're looking at the behaviour of the algorithmic complexity as N tends
to infinity. If k is tending to infinity while p stays fixed (e.g. p = 2
or 3), it's the 'small-characteristic' case. If p is tending to infinity
while k stays fixed (e.g. k = 1 or 2) it's the 'large-characteristic'
case. If both p and k are tending to infinity, it's the
'medium-characteristic' case. The medium-characteristic case covers a
lot of different situations, and the details of the 'optimal' relation
between p and k will vary depending on the algorithm.

Alec