1
$\begingroup$

The question is somehow academic, but hopefully not esoteric:

From https://www.certicom.com/pdfs/cert_ecc_challenge.pdf

Whether or not there exists a subexponential-time algorithm for the ECDLP is an important unsettled question, and one of great relevance to the security of ECC. It is extremely unlikely that anyone will ever be able to prove that no subexponential-time algorithm exists for the ECDLP. (Analogously, it is extremely unlikely that anyone will ever be able to prove that no polynomial-time(efficient) algorithm exists for the integer factorization and discrete logarithm problems.)

If somebody indeed should find a proof for non existence of a subexponential algorithm one day, can be anything say about how "complex" such proof must necessarily be? Can we exclude, that a proof is very simple and just nobody discovered it until now? On what facts is the statement above based?

On the other hand, can something be said about how likely it is to find a proper algorithm? Could such be very simple and it was just not discovered yet? Or is there something in math that excludes such simple algorithm by putting together the things we already know?

$\endgroup$
  • 3
    $\begingroup$ We have no unconditional proofs for the security of pretty much any computationally secure crypto. We don't even have a proof for $P \neq NP$ yet. $\endgroup$ – CodesInChaos Nov 16 '16 at 15:57
  • $\begingroup$ We can't even rule out a $O(n^2)$ algorithm for SAT. $\endgroup$ – Mikero Nov 16 '16 at 16:58
  • $\begingroup$ Such a proof would actually imply $P \neq NP$. So finding a proof for this is at least as hard as proving $P \neq NP$. $\endgroup$ – tylo Nov 16 '16 at 17:45
2
$\begingroup$

Of course, "very unlikely" does not mean here that "the probability to find a proof someday is very small", this would make no sense. This informal statement usually means the following: the considered problem is (or can be reduced to) a long standing open problem, which was studied by many researchers. As a consequence, any problem A which has been studied for a very long time somehow became a "unlikeliness hypothesis": if solving a problem B can be reduced to solving A, then B is "as unlikely to be solved" as A is. In the case you mention, as ECDLP was intensively studied, finding a subexponential algorithm for ECDLP is itself a kind of "unlikeliness hypothesis". I do not know whether a subexponential algorithm for ECDLP would solve other long-standing open problems.

Regarding your question "On the other hand, can something be said about how likely it is to find a proper algorithm? Could such be very simple and it was just not discovered yet?", there is an additional remark that might be worth mentioning. Although we cannot prove formally than solving a problem is unlikely, we CAN prove formally that it is not "simple". Here, "simple" means "using methods that belong to a class of known proof methods".

There has been a large body of work that focused on the following task: take,say, ten important articles that proved interesting result. Extract some common features of the proof technique they relied on. Formalize the concept of proving something using a proof with those features - you get a class of proofs C. Then, prove that it is infeasible to solve the problem using a proof from the class C. In other word: if we want to solve it, we need radically new kinds of proofs. This was used to show, for example, that the question "does $P = NP$" cannot be solved using classes of proofs called "relativization proofs", and even proofs from the larger class of "algebraization proofs". Therefore, we have a quite formal way of saying that "solving the $P = NP$ problem is not simple".

Note that this last remark is quite generic, but I do not know whether it applies to the particular case of ECDLP - I do not know about proofs that a class of known methods cannot be used to have a subexponential algorithm. Yet, it gives an idea on how one would attempt to show that it is hard to come up with a subexponential algorithm for ECDLP:

  • design a restricted class of algorithms, if possible a useful one that captures interesting existing algorithms
  • prove that no algorithm of this natural class can solve ECDLP in subexponential time

There are proofs, for example, that algorithms that treat the underlying group as a generic group (with black box access to the group operations) cannot break the problem in subsexponential time. But this is a far too restricted class of adversaries; I do not know whether larger and less restrictive classes of adversaries have been studied, but I would bet that some have been.

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