Polynomials and efficient computability

Question

In public key crypto, the popular definitions of security (CPA, CCA1,2) depend on PPT adversaries. I'm trying to understand why adversaries should be PPT.

It's clear that adversaries should be at most probabilistic sub-exponential, because otherwise they could exhaust the message space. It's also clear that adversaries should be at least PPT, because any computer can run low-order polynomial algorithms (barring unusual cases) and there's no good way to distinguish low-order polynomials from very high-order (and practically inefficient) polynomials.

So why not allow the adversaries to be probabilistic quasi-polynomials? Where quasi-polynomial means its time complexity is larger than all polynomials and smaller than all exponentials, like $n^{log(n)}$. Is there some example showing why it would not make sense for an adversary to be probabilitic quasi-polynomial?

Answer 1

The reason I was taught why poly-time is the conventional way to define "efficient" algorithms is that it's the smallest notion closed under various forms of composition.

If we have an algorithm for deciding whether some input is in some language and we let $N$ be the length of the input, then we'd like to call all the following operations efficient:

• Returning "yes" or "no" all the time costs one (or constant) time.
• Reading the input costs $N$ time.
• Calling one efficient algorithm taking time $A(N)$, then passing the result through an efficient algorithm taking time $B(N)$ gives a total time of $A(N) + B(N)$, so our class of "efficient running times" should be closed under addition.
• If an algorithm taking $A(N)$ time on its own is efficient, and you have an algorithm with $A(N)$ steps where each step is a call to another efficient algorithm taking $B(N)$ time, then you end up with $A(N)B(N)$ time, so "efficiency" should be closed under multiplication.

Plug all that together and you get "polynomial in $N$" as the smallest possible "efficiency notion" - which does not of course exclude other, larger notions such as the ones mentioned above.

This is not so much a cryptography as a general complexity theory/theoretical CS point, which cryptographers have borrowed for their notions of security.

Answer 2

There is nothing stopping you from doing this. I don't know of any cryptosystem that is in use today that would be considered unsecure against a quasi-polynomial time adversary. RSA is probably the closest. It is super-polynomial (thanks to GNFS), so it would still be secure in a quasi-poly time adversarial model.

The only argument I see against quasi-polynomial time adversary models is that it obviously does not reflect reality as well as the PT adversary (otherwise we would see much larger RSA keys in use).

Answer 3

An example: low outcome, or expectation in terms of game theory, can be the reason for a class of adversaries that are neither probabilistic quasi-polynomial nor PPT, and would only go after polynomial-logarithmic-time targets.