Why do we focus on polynomial time, rather than other kinds of time?

Question

Polynomial time seems to be mentioned quite frequently on this site. It often forms a threshold between two possible outcomes like being secure or an attack's validity. I know what $\mathcal{O}(n^c)$ means mathematically, but why do cryptographers not use other kinds of time for so many thresholds?

I don't think that I'm asking quite the same thing as What does "running in polynomial time" really mean?

Answer 1

The focus on polynomial time comes from cryptography's historical origin as a branch of computational complexity.

• It makes sense for a theoretical field to develop technology-independent ways of measuring efficiency. Actual clock time or number of clock cycles are technology-dependent. Talking about running time in an asymptotic sense is convenient because it makes specific technology irrelevant. No matter how fast machine A is compared to machine B, if machine A runs a $\Theta(n \log n)$ algorithm and machine B runs a $\Theta(n)$ algorithm, then eventually (for large enough $n$) machine B will be faster in terms of actual time.

• Algorithms that run in time $\Theta(n)$ are objectively fast/scalable/"efficient".

• Suppose an "efficient" algorithm makes calls to a subroutine (we don't count the cost of the subroutine against this algorithm), and the subroutine can also be realized by an "efficient" algorithm. Then, intuitively, the overall system (accounting for both the calling program & subroutine) should be "efficient" too. This is a basic composition property, and without it you have a very messy theory. Polynomial-time is the minimal way to define "efficient" that contains running time $\Theta(n)$ and enjoys this composition property.

It is for these reasons that "polynomial time" is synonymous with "efficient" in computational complexity. Its minimal nature makes it a natural and well-motivated definition.

However, just because it's well-motivated and natural doesn't mean it's sacred. Mihir Bellare points out asymptotic complexity as one of the arbitrary aspects of cryptographic research, to be critically examined.

As others have said here, there is plenty of work that follows a concrete (rather than asymptotic) style. There is nothing wrong with working in this style. The main differences are: (1) things are a little messier; you can't hide all the mess inside an unspecified polynomial; (2) you forfeit the (very convenient) composability property.

Answer 2

why do cryptographers not use other kinds of time for so many thresholds?

Actually cryptographer use non-asymptotic run-time specifications whenever there's a good reason for it. However whenever there's not asymptotic notions tend to be easier to come up with and allow one to more quickly assure oneself that something is (somewhat easily) feasible to compute. You see it a lot here on Crypto.SE probably because using asymptotic notions usually suffices to express that something is (in)feasible which is usually more the point of the question than precise runtime analysis.

Examples for when cryptographers actually prefer non-asymptotic results over asymptotic ones:

• Security proofs. Sure you will find asymptotic proofs every now and then but most of them are concrete (ie give concrete upper bounds for probabilities and advantages) and it is actually advised to use concrete bounds over asymptotic ones because the hidden constants could be so big that it matters.
• Runtime of implementations. Very rarely you will find serious cryptographers arguing about the efficiency of implementations using asymptotic notions like RSA e.g. taking $\mathcal O(n^3)$ operations. More often than not, concrete measurements are preferred. A similar argument holds for cryptographic implementation tricks which are usually stated in the number of underlying primitive operations, you can find examples when you are looking for efficient ECC additions and doublings.
• Attack costs. Similar to security proofs most attacks will state that they need $2^x$ oracle / primitive evaluations to achieve $y$ probability of success using $2^z$ storage. As with run-time, asymptotic bounds would be completely useless here, because all (symmetric) crypto schemes can be broken in $\mathcal O(1)$ (with a hidden constant of $2^{128}$ or more).

Answer 3

Going by some information in the comments on SEJPM's answer:

By other I meant quadratic or factorial times

Let's list some of these other time complexities:

• Constant time or $O(1)$
  • Not to be confused with "constant-time" implementations as frequently spoken of in cryptography
• Logarithmic time or $O(\operatorname{log} n)$
• Linear time or $O(n)$
• Quadratic time or $O(n^2)$
• Cubic time or $O(n^3)$
• ...

• Polynomial time or $O(n^a)$

  • Notice how this is a generalization of all of the entries from linear onwards
• Subexponential time or $O(2^\sqrt n)$
• Exponential time or $O(2^n)$
• Factorial time or $O(n!)$

These are used to refer to how long it takes to solve a given problem. The lower down on the list, the longer it takes to solve a problem of a given size (assuming that the size is large).

From working with symmetric cryptography, we know that if a problem takes $O(2^{128})$ time to solve (or better, $O(2^{256})$), then we can rest assured that no adversary will ever be able to solve that problem.

Why not use easier time problems?

Could we use a problem that has a say quadratic time solution and make $n$ large enough such that it takes time equivalent to $O(2^{256})$? Sure, make $n = 2^{128}$ and then solving your problem will cost $2^{256}$ time. But then $n$ will be so very large that actually using such a system will be impossible.

We like problems that only have exponential-time algorithms because it implies that we can keep $n$ very small and have an efficient/practical implementation of the scheme.

Cryptography would be easy if you didn't have to worry about efficiency; the magic/challenge of cryptography is to have problems that are (relatively) easy to evaluate but hard to solve. If it is equally hard to evaluate as it is to solve, then it is not useful for cryptography.

So why care about polynomial time specifically?

In general, a polynomial time algorithm is considered "efficient". It will not take until the end of the universe to solve even a large such problem.

There are some conceivable exceptions: The exponent could be so large that even reasonably small values of $n$ would lead to problems that are intractable to solve in a practical amount of time.

This question on cs.stackexchange has a table that is relevant to this topic. I will re-post it here for the discussion:

And a quote from the answer:

... you'd need to give an algorithm of logarithmic complexity input of size on the order of 2 to the something enormous in order to get it to run for a century, but for an algorithm of complexity $O(n!)$ you only input of size ~10 to make it run for that long.

If an there is an algorithm that provides a solution to the problem in polynomial time, in general that means the problem is solved too easily to be of use for cryptography.

Why don't we use problems with $O(n!)$ time solutions?

If you know of a problem where you can prove that the adversaries best solution is $O(n!)$, I'm sure the world would love to hear about it. Remember also, that the legitimate users (not adversaries) need to be able to compute whatever it is efficiently.