Why is it important to solve a problem in Polynomial time, In cryptography?

Question

I have just started to learn Cryptography.

I am trying to learn "Merkle-Hellman Knapsack Cryptosystem".

So, right at the beginning of the discussion, a question came in my mind:

Why is it important to solve a problem in Polynomial time?

Answer 1

The concept of polynomial time is a theoretical concept that is supposed to capture what kinds of problems are possible to solve "in practice". In practical cryptography, the goal one is interested in is that no government body can break the system in less than a 100 years (say). However, this concept is hard to reason about, for many reasons. One reason is that the set of problems that can be solved in a 100 years depend on your hardware, budget, and so on. Moreover, even given a specific algorithm for a problem, it is hard to estimate how much time exactly it will require to run. To circumvent these difficulties, cryptography theory suggests the following idea:

Consider a cryptosystem which depends on a parameter $n$ tending to infinity. Analyze the security of the cryptosystem in terms of the asymptotic complexity of breaking it.

The asymptotic complexity doesn't depend too much on the exact hardware (as long as it's not a quantum computer); if next year a new CPU is revealed running 10 times as fast, a system that requires $O(2^n)$ time for breaking will still require $O(2^n)$ time for breaking. Moreover, we make the following assumption:

An algorithm runs "fast" if it runs in polynomial time (in $n$).

Polynomial time is a natural class for many reasons, the reason here being that it is the smallest class which is closed under function composition and contains superlinear functions. Putting both ideas together, we get:

A cryptosystem depending on a parameter $n$ is secure if it cannot be broken in time polynomial in $n$.

Here $n$ should be a reasonable parameter. One way of enforcing it is to require the encryption procedure to run in polynomial time in $n$.

This definition has led to a beautiful theory of theoretical cryptography. However, in practice polynomial time is not such a good notion, especially in cryptography, for two reasons:

• Polynomial time could be very slow in practical. For example, an encryption procedure running in time $O(n^{10})$ or $10^{10} n$ is not practical.

• Super-polynomial time could be practical, depending on the value of $n$. For example, $2^{n/2}$ is very practical for $n = 64$.

In applied cryptography, therefore, one tries to give running time estimates for a particular system (a particular setting of $n$) which is not asymptotic. Usually one calculates the number of "basic operations", a concept which is not defined precisely but is a better proxy than asymptotic complexity. When possible, actual simulations are run to show that the cryptosystem can be broken with weakened parameters, and to extrapolate the time it takes to break the full cryptosystem.

One problem with this approach is that it is going to be very difficult to prove that a system is secure. While this is true even for theoretical cryptography (we cannot prove the security of any cryptosystem), here it is seems that the best one can do is try to break the system and fail; proving a meaningful lower bound is probably too much to ask for.

One way to circumvent this difficulty in some situations is to use oracle (or black box) models. Suppose that a cryptosystem relies on some cryptographic primitive which we trust. We can imagine replacing this primitive by an idealized component. In this case, sometimes lower bounds on the number of queries to the black box can be proved. This allows us to gauge the security of the model, making the implicit assumption that the algorithm implementing the black box is completely opaque.

This is the approach taken by theoretical cryptography – assuming the existence of some secure cryptographic primitive (which we can't prove at the moment), it constructs cryptosystems and proves their security. However, this doesn't necessarily have practical implications, since in reality the parameter $n$ is fixed rather than tending to infinity. Even in cases in which we can rigorously prove that some cryptosystem requires $T(n)$ time to break (given some assumptions on the cryptographic primitives), usually the guarantees are very weak, and in order to get reasonably large $T(n)$, an impractically large $n$ is required.

For more information, check this classic paper on concrete security and this notorious article debunking theoretical cryptography.

Answer 2

Problems that can be solved in polynomial time are problems that can be solved quickly. It doesn't matter, whether an algorithm takes $O(n)$ or $O(n^2)$, it still take polynomial time, which is still much faster than a problem that grows exponentially with the input size.

So, now that you know that it can be solved, this means that it is easy to solve than more difficult problems. However, I think you refer (or want to get a deeper grasp) of the difference between P and NP. Both are categories of problems that can be solved in polynomial time, however only non-deterministic process can solve NP in polynomial time. In other words, polynomial time, makes it easy for a problem to be checked (so I am thinking of factorization in encryption).

PS: this might not be the best answer, but this could point you the direction for understanding