Problems that are polynomially "hard" to compute but "easy" to verify

Question

In the (unlikely) event that $P=NP$ with a constructive proof of a polynomial time algorithm that solves 3SAT, obviously things will be very different. However, practically, it could happen that the degree of the polynomial run time is very large (e.g. $\Omega(n^{10000})$) such that any reasonably large problem is still out of reach for our current computing technology.

My question is: is it possible to find/construct a problem that have a lower-bound polynomial complexity $\Omega(n^p)$ to compute but an upper bound $O(n^q)$ to verify, with $q$ being quite small (e.g. $q=1$) and $p\gg q$. This problem would function essentially the same as current problems for which no known polynomial algorithms exist (e.g. factorization), and thus would still be usable in e.g. security systems in even in the case of $P=NP$.

Answer 1

No such problem is known (not with a known mathematical proof of a lower bound). Of course cryptographers would jump on it if we had one. As a result, cryptography is currently based on assumptions that we hope are true but we cannot prove (these are sometimes called "hardness assumptions"), and then we prove that if the assumption is valid, then the cryptographic scheme will be secure against attack.

Many good cryptosystems offer a reasonable candidate for a problem for which verification is much easier than solving, but we have no mathematical proof that this is necessarily so. For instance, factoring large integers seems like a good candidate for such a problem: it is easy to verify that you have correctly factored a large number, but it seems to be hard to find those factors in the first place. Breaking AES also seems like a good candidate for such a problem: it is easy for a cryptanalyst to verify that they have found the right AES key to decrypt some known plaintext pairs, but it seems to be hard to find the right AES key in the first place. However, we have no mathematical proof for any of these.

You might be shocked to learn that there is no explicitly known function family for which we can prove a super-linear lower bound (i.e., for every explicit function we can think of, we cannot rule out the possibility that it can be computed by a linear-size circuit). See here for a catalog of just how weak our known results are. This highlights just how far we are from being able to prove useful lower bounds.

I have some reading for you that might be helpful:

• Provable Lower Bounds for some Algorithmic Problems?

• Why haven't we proven many things computationally secure yet?

• Is there a cryptography algorithm that will remain safe if P=NP?

• Is it possible to construct an encryption scheme for which breaking is NP complete but there nearly always exists an efficient breaking algorithm?

• Is AES reducible to an NP-complete problem?

• Cryptography systems based on NP complete problems

• What is the relation between computational security and provable security?

One early attempt at what you're hoping for are Merkle puzzles. These show a gap of the form you mention, with $O(n^2)$ time for attackers to break (i.e., to solve) but $O(n)$ time for defenders to compute (i.e., to verify). In your notation, this amounts to $p=2$ and $q=1$. This result holds only under the unproven assumption that solving a single puzzle takes $n$ steps of computation, but we have no concise (constant-length) puzzle for which we have a proof that solving will take that long, so even Merkle puzzles don't do what you are hoping for -- they still rely on an unproven assumption. And, there is a proof that the basic approach found in Merkle puzzles doesn't generalize to larger gaps (larger ratios of $p/q$), so they don't seem to lead somewhere that will be practically useful, even if we ignore that they rely on an unproven assumption like every other cryptosystem.

Answer 2

What about problems that cryptocurrencies are using?

The problem is, given a hash function, to find data (of specified length) that has its hash starting with specific number of zeros. Finding it takes a long time, but it can be checked super fast just by calculating hash of this data and verifying it looks as expected.