Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finite field with hard discrete log for both groups

  1. Sep 1, 2015 #1
    If there a finite field where both group structures have hard discrete logs? Discrete log in the additive group means multiplicative inverse.
  2. jcsd
  3. Sep 1, 2015 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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?
  4. Sep 2, 2015 #3
    "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?
  5. Sep 8, 2015 #4
    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.
  6. Sep 9, 2015 #5
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Finite field with hard discrete log for both groups
  1. Finite Group (Replies: 2)

  2. Finite group (Replies: 3)

  3. Finite groups (Replies: 2)