4
$\begingroup$

Let's assume you can factor integers in a very efficient manner. Would that endanger the security of e.g. elliptic curve cryptography, or is there no link between the two ? You can often read that Shor algorithm would break RSA and Elliptic Curve Cryptography, but I'm more precisely searching about the effect of breaking one system (maybe not using some quantum computations) over the other.

$\endgroup$
5
$\begingroup$

This is an interesting, but completely open question. The ability to compute discrete logs in specific well-chosen groups entails the ability to factor, but there is no other known formal relations.

Discrete logs algorithms over prime order fields and factorization algorithms have often worked hand in hand: the same algorithmic principles led to the best algorithms in both cases. But this says nothing about any formal reduction between them. Of course, in the quantum setting, since both can be solved in polynomial time, both formally reduce to each other, but in a void sense.

Last point: while there may be some relation between the hardness of discrete log over prime order fields and that of factorization (in the sense that there seems to be common algorithmic principles in our best attacks against them), the situation is very different for elliptic curve discrete logarithm. Actually, I do not think any cryptographer would believe that a polytime factoring algorithm could help breaking elliptic curve discrete logarithm (over well chosen curves). One way to see it is: we already have subexponential factorization algorithms, so "factoring polylog size numbers" can already be done in polynomial time. Yet, "solving elliptic curve discrete log over polylog size groups" (i.e., finding a subexponential ECDL algorithm) would be an absolutely incredible breakthrough (our best algorithms run in time $O(2^{n/2})$ for groups of size $\approx 2^n$).

$\endgroup$

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.