# Why is a non-existence proof for ECC discrete log extremely unlikely?

The question is somehow academic, but hopefully not esoteric:

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?

• 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. Nov 16, 2016 at 15:57
• We can't even rule out a $O(n^2)$ algorithm for SAT. Nov 16, 2016 at 16:58
• 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$.
– tylo
Nov 16, 2016 at 17:45

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