# Finite field with hard discrete log for both groups

1. Sep 1, 2015

### Dragonfall

If there a finite field where both group structures have hard discrete logs? Discrete log in the additive group means multiplicative inverse.

2. Sep 1, 2015

### andrewkirk

A discrete log is a property of two elements of a group, say a and b, that holds when there is a natural number k such that ak=b. I don't think it means anything to say that a whole group has a discrete log. What were you trying to say? And what is the role of the word 'hard' in the question?

3. Sep 2, 2015

### Dragonfall

"Hard" in the cryptographic "We tried and we failed therefore" sense. I don't mean a whole group has a discrete log. I mean that there is no known way of computing discrete logs for that group efficiently.

Take an additive group that has a hard discrete log, for example a suitable elliptic curve group over a finite field. Is it possible to define a multiplicative structure on those elements such that

1) the multiplicative group has a hard discrete log
2) a distributive law holds

So that it's a field with two hard discrete logs?

4. Sep 8, 2015

### Citan Uzuki

If you just want the field to exist, certainly. If you want the multiplication on the field to be efficiently computable, probably not. Suppose that G is a group with a hard discrete logarithm. Note that for a discrete log to be well-defined over G, G must be cyclic. The only cyclic groups which can be the additive group of a finite field are those of prime order. Now, if G has prime order p, there are exactly p-1 multiplicative structures on G which will turn it into a field. Each is defined by picking a nonzero element g in G to be the multiplicative identity, and then defining (ag)*(bg) = (ab)g. Notice that computing the multiplication on G is precisely to solve the computational Diffie-Hellman problem for G. Thus, the only to have what you ask for while still keeping the multiplication on G efficiently computable would be to find a group for which discrete logarithms are hard, but Diffie-Hellman is easy. It can be shown that under certain relatively mild number-theoretic assumptions that these two problems are actually equivalent (see Maurer, Ueli M. (1994), Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms). So you probably can't get what you want here.

5. Sep 9, 2015

Damn