Hacker News new | ask | show | jobs
by baby 2552 days ago
They are equivalent according to this: https://crypto.stackexchange.com/questions/9385/reduction-of...
2 comments

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...

That for DLP modulo a composite, whereas Bitcoin uses DLP over elliptic curve groups.