# What does "running in polynomial time" really mean?

I'm currently learning private-key cryptography. I've been able to see that perfect secrecy is achievable if no assumption is made about the computational power of the attacker.

However, perfect secrecy is quite heavy to use, so we relax our assumptions to achieve the so-called computational secrecy, by assuming that the computational power of the adversary is bounded.

Then they speak about "efficient adversaries". They are defined as "running in polynomial time". I'm sorry, I know what asymptotic time-complexity is, but here I have no idea of what it means.

I'm confused because there seem to be a restriction. Security is said to be preserved only against efficient adversaries, that run in a feasible amount of time. In other words, they seem to say that polynomial time is a limitation on the adversary, and I don't understand that because to me it is the best complexity that can be achieved by an algorithm. If we are protected against polynomial adversaries, shouldn't we be protected against ALL adversaries ?

So maybe I'm missing something... Can someone explain what an efficient adversary really is ?

• I think one part of this question (why "efficient" == "polynomial time") might be better suited for CSTheory. However, I think you have the concepts backwards. Consider the task of finding the correct $k$-bit key among all $2^k$ possibilities (brute force). Without additional information provided by cryptanalysis, the best way is to check every key, which takes $O(2^k)$ time. This is not polynomial time but exponential time, and is therefore asymptotically out of reach for a polynomial time adversary. The point of cryptography is to make sure the best attack algorithm is not polynomial time. Jun 7 '13 at 10:20
• So saying that the adversary runs in polynomial time would actually mean that adversary can't find any polynomial time algorithm to determine the key ? It's is a special way to say it. But I indeed see your point. It is probably just about terminology. Jun 7 '13 at 10:24
• Yes, well it's more general than that, it says that the adversary is assumed to only be able to run polynomial time algorithms, because his computational abilities are bounded (in an asymptotic sense). So if he cannot find such an algorithm to solve problem P, problem P is computationally "secure" (informally) against this adversary. Sure, the adversary can use an exponential time algorithm to try to solve P, but in this security model it is assumed the algorithm will not terminate in a feasible amount of time, and hence is as good as no algorithm. It is mostly terminology. Jun 7 '13 at 10:34

Perfect secrecy is achievable in a few cases, such as one-time pads, and, well, that's pretty much it. Most cryptographic protocols are vulnerable to an all-powerful, all-knowing attacker. If you do not put any restriction on what the attacker can do, then

1. Guess the key.
2. Profit.

breaks almost any cryptography, as does

1. Wave a magic wand.
2. Profit.

So at the very least we must restrict our model attackers who can do things we haven't even imagined. Cryptography also doesn't aim to protect against lead pipe cryptanalysis. So we assume that attackers are only allowed to do things “inside the system”. Based on Turing's thesis, we assume that the attacker can only compute computable functions, and that the function computed by the attacker does not depend on the key. (It's ok if the attacker can make random choices too, as long as their probability isn't influenced by the key.)

Even a deterministic attacker who does not know the key can still break most cryptographic protocols with enough effort. All he has to do after all is enumerate all possible keys. But for sufficiently large key sizes, this should be unrealistic: as a rule we aren't interested in attacks that would take more than the lifetime of the universe.

If you want to analyse the resistance of an algorithm very precisely, you would need to know exactly how powerful the attacker's computer is, and study all possible ways in which he can make the computation required by the attack to find which one is the fastest (or more generally the cheapest). This is impractical. To start with, we look at the asymptotic behavior of the attacks: the way the attacks become harder as the parameters (such as key size) become larger.

In computational complexity, there is a nice break between polynomial and super-polynomial algorithms. This break fits cryptography well. The usual methods of doing realistic stuff tend to be polynomial, whereas enumerating all keys is exponential in the size of the key (or more precisely in the strength of the key). So restricting to polynomial attackers combines two nice properties:

• It is good for getting theoretical results.
• It does a good job of including realistic attackers and excluding unrealistic ones.
• Thank you very much for your answer, it is very clear. So if I get it correctly, saying that an attacker is polynomial actually states that the time he is ready to spend on the problem is polynomial with the size of the key. Hence, since exploring successfully the key space is exponential with the size of the key, we can expect that there is only little probability that he shall actually succeed in breaking the system. This would indeed explain why we consider superpolynomial attackers as unrealistic, as you said. Thanks again. Jun 7 '13 at 18:37
• @Backslash36 Actually in general it is polynomial in terms of some security parameter. For encryption this often is the key size, for other systems might be other things. Jun 9 '13 at 16:18