can it be proven that something is "difficult" (prime factoring for example)

Question

I understand that the current state of the art suggests that factoring into primes is a difficult problem. I also understand that a large part of public key cryptography seems to be based on that supposition.

However, is there any proof that factoring into primes is a "difficult" problem? Can we mathematically prove that something is "difficult"?

Is current state of the art cryptography based solely on a conjecture?

• thanks to Ricky Demer for pointing out I should be writing factoring into primes rather than factoring of primes (whoops!!!)

Answer 1

However, is there any proof that factoring of primes is a "difficult" problem?

No. $\:$ In fact, factoring of primes is very easy; just output one and the prime.
There's also no known proof that factoring into primes is a difficult problem,
and there is a known efficient quantum algorithm for that problem.

Can we mathematically prove that something is "difficult"?

Yes. $\;\;\;\;$ Since $\:$ BPP $\subseteq$ P/poly $\subset$ PEXP $\:$, $\:$ the problem
"Given a probabilistic Turing machine M and a non-negative integer t, is the
probability that the M halts on the empty input within t steps greater than 1/2$\hspace{.02 in}$?"
is difficult for classical algorithms, even when they can take advice.
Since $\:$ BQP $\subseteq$ PP $\:$ and [the Time Hierarchy Theorem generalizes to show that $\:$ PP $\subset$ PEXP $\:$],
that problem is also difficult for quantum algorithms.
Since BQP/qpoly does not contain EESPACE, the problem
"Given a deterministic Turing machine M and a non-negative integer s,
does M halt on the empty input without using more than 2^s space?"
is difficult even for quantum algorithms that can take quantum advice.

Is current state of the art cryptography based solely on a conjecture?

No. $\:$ Shamir secret sharing is not based on any conjecture, and quantum key distribution is only based on the current understanding of quantum physics. $\:$ Even if Shamir secret sharing is not "current state of the art" and that understanding counts as "a conjecture", it would still be the case that "current state of the art cryptography" is based on conjecture$\hspace{.02 in}$**s**, rather than "a conjecture".

Answer 2

There are problems that can be shown impossible to solve in general ( i.e., there are no general algorithms able to solve all cases, like the halting problem). Some problems have been shown to be hard to solve (any algorithm will consume lots of resources when solving some instances of the problem). Check out computational complexity theory.

Then there is the famous P vs NP problem, the suspicion that if you guess a solution and can check it does solve the problem in polynomial time ("reasonably fast") that doesn't mean that you can always construct a solution in reasonable time. Note that even if this turns out to be true, it doesn't mean all, or even many, instances of NP complete problems are hard to solve.

What you want for cryptography is problems where the vast majority of the instances are hard to solve, and the easy cases simple to identify. Given a guess of the solution (i.e., you have the key) using it must be easy, otherwise the cryptographic system is useless. I believe there are no systems in use that have been shown NP hard.

Answer 3

In a word, rarely. In fact, breaking some cryptographic systems may not even be as complex as prime factoring, and prime factoring itself isn't exponentially hard, sub-exponential algorithms exist, which explains why RSA keys have to be so long. In fact, very few cryptographic systems can even be proved as hard to break as prime factoring or discrete logarithm, where we have at least the practical assurance of many smart people working on them for a long time with no results. But then again, a paper and pencil algorithm for adding two continued fractions wasn't known for a very long time, until it was.

See an elementary survey of cryptographic security from mathematical point of view here http://www.ams.org/notices/201003/rtx100300357p.pdf.

It's not all bad: "Cryptographic protocols are not developed and marketed in the real world unless they have been approved by certain industrial standards bodies... Protocols that are based on dubious assumptions or fallacious proofs are not likely to survive this process". We don't have mathematical proofs that bridges we walk on won't fall down under us either.