1
$\begingroup$

I am trying to look into a relation between the following three problems which are widely used to build public crypto systems:

  • Integer Discrete log
  • Elliptic Curve Discrete log
  • Integer Factorization

Can any of these problems be reduced to another such that an efficient solution to one of them yields an efficient solution to the another?

$\endgroup$
2
  • 1
    $\begingroup$ Not a full answer, but if you are asking because of the recent Defcon talk that claimed recent advances in the discrete log problem might break RSA, it was full of it. The advances were for groups of small characteristic which don't even apply to the groups we use for the discrete log problem, let alone RSA. $\endgroup$ Aug 17, 2013 at 2:35
  • $\begingroup$ Yeah but their broader point about needing to begin the migration to other primitives is valid, imo. Why gamble on factoring and discrete log in prime fields when we can just as easily use elliptic curves? $\endgroup$
    – pg1989
    Aug 17, 2013 at 3:04

1 Answer 1

2
$\begingroup$

Actually, there are two known reductions among these three problems:

  • If you can solve discrete logs in $Z^*_n$ for composite $n$, you can use that to efficiently factor $n$

  • If you can solve discrete logs in $GF(p^k)$, you can compute discrete logs in an Elliptic Curve over $GF(p)$. That's because there is a known mapping of Elliptic Curves over $GF(p)$ into $GF(p^k)$ (for an integer $k$ that depends on the curve) that preserves the group operation; hence you can solve discrete logs over an Elliptic Curves by mapping the generator and the target into $GF(p^k)$, and solving the discrete log there. Now, for curves used in practice, $k$ is large enough that, with the current discrete log algorithms, this method is actually slower than just using a generic discrete log algorithm in the elliptic curve.

Of course, neither of the above reductions would apply to the recently discovered algorithms for doing discrete logs over small characteristic fields; for the former, we're not talking about a field at all ($Z^*_n$ is a ring, not a field), and for prime elliptic curves (which is what we use in practice), $GF(p^k)$ has a very large characteristic.

$\endgroup$
3
  • $\begingroup$ OP: Accept this answer, I was mistaken. Deleting my response. $\endgroup$
    – pg1989
    Aug 17, 2013 at 5:47
  • $\begingroup$ Thanks a lot, I tried to find a paper or sort of notes on such mapping between GF(p^k) and GF(p), but could not find any. Could you provide me with a reference. $\endgroup$
    – Faith
    Aug 18, 2013 at 23:54
  • $\begingroup$ @Faith: the mapping is known as 'Weil Descent'; I can't find any good references for the mapping itself; I do see a number of papers talking how it can be used to attack DH problems in various specific Elliptic Curves, such as lab.iisec.ac.jp/~arita/pdf/acrypFinal.pdf $\endgroup$
    – poncho
    Oct 7, 2013 at 21:20

Your Answer

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

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