[Cryptography] New attacks on discrete logs?

[Jerry Leichter]

On May 23, 2014, at 5:03 PM, Bear <bear at sonic.net> 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?
Ah, time for some fun math I haven't thought about in years.

A (commutative) group G is a bunch of elements with a binary operation . with the following properties:

If g, h, and j are in G, 
1. g.h is defined and is in G ("closure").

2. g.h = h.g ("commutativity")

3. (g.h).j = g.(h.j) ("associativity")

4. There is some element e in G such that e.g = g ("identity element")

5. There is an element g' such that g.g' = e ("inverse elements").

It's easy to show that e is unique (if there were another identity element f, then e.f = f but also e.f = f.e = e, so f = e).  Similarly, g' is also the uniquely defined "inverse of g".

Groups occur all over the place.  Addition of integers is a group with identity element 0 and the inverse of n is -n.  The same is true for the rational numbers, the real numbers, and the complex numbers; all of these are infinite.  The integers mod N are similarly a group, but a finite one.  The non-negative numbers are not a group under addition because they lack inverses.  The non-zero rationals (or reals or complex numbers) are groups under multiplication, with 1 as the identity element and g' given by 1/g; that doesn't work for the integers, because there are no multiplicative inverses.  The integers mod N, less 0, are groups under multiplication if and only if N is a prime.  (If N = nm, then n and m are members of the non-zero integers mod N, but their product is 0 mod N, which is not a non-zero integer mod N - so we don't have closure.)

The rationals, reals, and complex numbers are actually what are known as fields.  A field F is a set of elements with two operations, usually write as + and *.  It has the following properties:

1.  F is a group with the operation +.  The identity element for + is usually written as 0.

2.  F-{0} - i.e., the elements of F other than the identity element for addition - is a group with the operation *.  The identity for this group is usually written as 1.

3.  For any f, g, h in F, f*(g+h) = f*g + f*h.  ("distributivity")

Since 1 is in F-{0}, it's certainly true that 1 != 0.

In order to make multiplication apply to all of F, we define f*0 = 0*f = 0.  It's easy to see that this definition is consistent with distributivity.  Note that 0 can't have an inverse:  0*f = 0 but 0 != 1.

The rationals, reals, complex numbers, and the integers mod a prime are all fields.

Suppose f and g are in F and f*g = 0.  Then either f or g is itself 0, since the non-zero elements were a group under multiplication.

Now, take some element f in F and start adding it to itself:  f, f+f, f+f+f, etc.  Does this sequence ever contain 0?  Suppose it does.  In fact, suppose n is the smallest number of additions you need so that {f+f...+f} n times is 0.  Now suppose n = ab, where a, b > 1.  You can subdivide the additions into groups of size a, repeated b times:  {f+f...+f} n times is {{f+f...+f} a times + ... +} b times.  {f+f...+f} a times is some other element g, and this is just saying that {g+g+...+g} b times is 0; and b < n.  So we can find elements with smaller and smaller "number of repetitions to get to 0" - until that number of repetitions is a prime number.

So:  If there is any element f which if added up n times produces 0, there is some element g which if added up p (a prime) times is also zero.

But if g+g...+g = 0 (p times on the left, g non-zero of course) then also

(1/g) * (g+g...+g) = (1/g) * 0 = 0

Distribute on the left and you get:

(((1/g) * g)+...) = 0

or

1+1...+1 p times = 0.

But now you can multiply this equation by *any* element f in the field, showing that if you add f up p times, you always get 0.

Finally, can there be two distinct primes p and q such that adding up 1 either p *or* q times gives you 0?  The answer is no.  Suppose there was more than one such prime.  Let p be the *smallest* one, and let q be a different one.  We have:

1+1+...1 q times = 0

But then

((1+1...) p times) + ((1+1...) q-p times) = 0

The first of these terms is 0 already, so:

((1+1...) q-p times) = 0

Repeat this, pulling off groups of p 1's.  Since p and q are primes, you can't possibly end up with no 1's - but you do eventually end up with q mod p < p 1's.  But that can't be - p was by hypothesis the *smallest* prime that gave you 0.  (q mod p might not be prime, but as we saw early that some prime divisor of it would also give 0, and that would have to be a prime < p - and there isn't one, by hypothesis.)

So:  If a field has any element f that if added to itself n times produces 0, then there is a *unique* prime p such that if you add *any* element of F to itself p times, you get 0.  This prime p is called the characteristic of the field.

It may well be that you *never* get 0 if you add an element to itself over and over.  In that case, the field is said to have characteristic 0.  (It would perhaps make more sense to say they have infinite characteristic, but the convention is to use 0.)

The rationals, reals, and complex number fields all have characteristic 0.  The integers mod a prime p have characteristic p.

It's not hard to see that any finite field must have a non-zero characteristic, and only a bit harder to see that a finite field with characteristic p must have p^n elements.  There are infinite fields with non-zero characteristic but they aren't familiar kinds of objects (and of course in finite computing we always have to restrict ourselves to finite objects).

Fields with characteristic 0 "feel like the rationals and reals and complexes". All such fields share certain "natural" properties that fields with non-0 characteristic don't.  For many properties, have a large characteristic means "being closer to having that property".  So results showing that certain problems that appear to be hard in characteristic 0 are likely also hard in large characteristic fields, but not in small characteristic fields, are expected.  (That doesn't mean they are easy to prove, or that this is a universal "meta-property" - it's just a heuristic.)
                                                        -- Jerry