Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
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. –  imichaelmiers Aug 17 '13 at 2:35
    
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? –  pg1989 Aug 17 '13 at 3:04
add comment

1 Answer 1

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.

share|improve this answer
    
OP: Accept this answer, I was mistaken. Deleting my response. –  pg1989 Aug 17 '13 at 5:47
    
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. –  Faith Aug 18 '13 at 23:54
    
@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 –  poncho Oct 7 '13 at 21:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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