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?

$\endgroup$
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$

$\endgroup$
  • $\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 Jul 9 '15 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 Jul 9 '15 at 13:41
  • $\begingroup$ This is true. Due to the random self reducibility you can trade off time and success probability. $\endgroup$ – Yehuda Lindell Jul 9 '15 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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