1
$\begingroup$

Given a field $\mathbb{F}_{2^n}$, are there any choices of primitive element $g$ that make the discrete logarithm easier for that generator? That is, are there any degenerate cases?

For example, if I choose a small generator like $g = x$ in $\mathbb{F}_{2^{256}}$, can I quickly find $n$ such that $g^n = a$ for a given $a$? Or is this equally difficult for any $g$ picked in any $\mathbb{F}_{2^n}$ over any irreducible polynomial?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

It is equally difficult (within a factor of 2) for any irreducible polynomial.

Suppose $g$ was your 'cheap' irreducible polynomial, that is, one for which, given $g^n$, you can rederive $n$ quickly. Then, given an arbitrary pair $h, h^x$, you can quickly find $a, b$, such that $h = g^a$ and $h^x = g^b$, and then immediately deduce that $x = a^{-1}b$

Improve this answer
$\endgroup$
3
  • $\begingroup$ Note that a full reduction would work as follows (and as you'll see it's not really a factor of 2). Assume that there exists a generator $g$ for which it's possible to find a discrete log of a random element with probability $\epsilon$. Then, given $h,h^x$ for a random $x$, you can compute $h^r$ for a random $r$ that you choose, and find $ar$ and $b$ such that $h^r=g^{ab}$ and $h^x=g^b$. Since you know $r$ you can deduce $a$ and then as you showed $x=a^{-1}b$. The probability of success is $\epsilon^2$ since you need to succeed on two independent instances of the discrete log problem. $\endgroup$
    – Yehuda Lindell
    Commented Jul 9, 2015 at 6:25
  • $\begingroup$ @YehudaLindell: actually, if the mechanism succeeds with probability $\epsilon$, then a randomized procedure can solve an arbitrary DL for generator $g$ with an expected $1/\epsilon$ random tries. Then, using that, you can then solve an arbitrary DL for generator $h$ with an expected $2/\epsilon$ random tries (by first applying the base random procedure to $h$ and then applying it to $h^x$) $\endgroup$
    – poncho
    Commented Jul 9, 2015 at 13:41
  • $\begingroup$ This is true. Due to the random self reducibility you can trade off time and success probability. $\endgroup$
    – Yehuda Lindell
    Commented Jul 9, 2015 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.