3 ms·

It's also a long time since I looked at this, but I recall pretty clearly, that factoring is "easier" than DLP. "Easier" as in factoring is reducible [1] to th

It's also a long time since I looked at this, but I recall pretty clearly, that factoring is "easier" than DLP. "Easier" as in factoring is reducible [1] to the DLP. I.e. if you could do DLP in polynomial time, then also factoring becomes polynomial (thanks to Shor's Algorithm [2]). The reverse, however, is not currently known to be true AFAICS: having an oracle that computes the DLP does not help you to speed up factoring (at least not in a way that makes it polynomial). [1] https://en.wikipedia.org/wiki/Reduction_(complexity) https://en.wikipedia.org/wiki/Reduction_(complexity) [2] https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm (EDIT: typo)

baby 7y ago
They are equivalent according to this: https://crypto.stackexchange.com/questions/9385/reduction-of-integer-factorization-to-discrete-logarithm-problem https://crypto.stackexchange.com/questions/9385/reduction-of...
- Ar-Curunir 7y ago
  That for DLP modulo a composite, whereas Bitcoin uses DLP over elliptic curve groups.
- dvdkhlng 7y ago
  I think you are mistaken, they are not equivalent in any way that would be meaningful to assessing cryptographic strength. The stack-exchange questions that you link to refers to [1] "Discrete Logarithms and Factoring". Section 1 "Introduction" already states many facts that imply that DLP is hard, even if you can factor: * fastest known method for DLP is O(exp(c sqrt(log n log log n))) * 1. 3c) "if we can factor in polynomial time, then to quickly solve a^x ≡ b mod n, all we need are solutions modulo the prime divisors of n" Note that "solutions modulo the prime divisors of n" are still instances of the DLP with super-polynomial complexity, and in cryptographic applications N is usually a prime number anyway (DHE, ElGamal crypto-system), so 1 3c) does not actually apply. See also the paper's section 6 final remarks "Conversely, one can ask for a fast algorithm for prime-modulus problems, assuming all needed factorizations. Both of these questions remain unanswered". [1] https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186.pdf https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186...
phkahler 7y ago
>> I.e. if you could do DLP in polynomial time, then also factoring becomes polynomial That is what I remembered. You don't need Shor's Algorithm though. DLP would help finding roots, in particular if the log of a number is even, you can compute the square root of the original number which is useful for finding quadratic congruences (the goal of the quadratic sieve). The reverse (factoring enables DLP) does not appear to be true.

baby 7y ago

They are equivalent according to this: https://crypto.stackexchange.com/questions/9385/reduction-of-integer-factorization-to-discrete-logarithm-problem https://crypto.stackexchange.com/questions/9385/reduction-of...

Ar-Curunir 7y ago
That for DLP modulo a composite, whereas Bitcoin uses DLP over elliptic curve groups.
dvdkhlng 7y ago
I think you are mistaken, they are not equivalent in any way that would be meaningful to assessing cryptographic strength. The stack-exchange questions that you link to refers to [1] "Discrete Logarithms and Factoring". Section 1 "Introduction" already states many facts that imply that DLP is hard, even if you can factor: * fastest known method for DLP is O(exp(c sqrt(log n log log n))) * 1. 3c) "if we can factor in polynomial time, then to quickly solve a^x ≡ b mod n, all we need are solutions modulo the prime divisors of n" Note that "solutions modulo the prime divisors of n" are still instances of the DLP with super-polynomial complexity, and in cryptographic applications N is usually a prime number anyway (DHE, ElGamal crypto-system), so 1 3c) does not actually apply. See also the paper's section 6 final remarks "Conversely, one can ask for a fast algorithm for prime-modulus problems, assuming all needed factorizations. Both of these questions remain unanswered". [1] https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186.pdf https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186...

phkahler 7y ago

>> I.e. if you could do DLP in polynomial time, then also factoring becomes polynomial That is what I remembered. You don't need Shor's Algorithm though. DLP would help finding roots, in particular if the log of a number is even, you can compute the square root of the original number which is useful for finding quadratic congruences (the goal of the quadratic sieve). The reverse (factoring enables DLP) does not appear to be true.