Are asymptotic lower bounds relevant to cryptography?

Question

An asymptotic lower bound such as exponential-hardness is generally thought to imply that a problem is "inherently difficult". Encryption that is "inherently difficult" to break is thought to be secure.

However, an asymptotic lower bound does not rule out the possibility that a huge but finite class of problem instances are easy (eg. all instances with size less than $10^{1000}$).

Is there any reason to think that cryptography being based on asymptotic lower bounds would confer any particular level of security? Do security experts consider such possibilities, or are they simply ignored?

An example is the use of trap-door functions based on the decomposition of large numbers into their prime factors. This was at one point thought to be inherently difficult (I think that exponential was the conjecture) but now many believe that there may be a polynomial algorithm (as there is for primality testing). No one seems to care very much about the lack of an exponential lower bound.

I believe that other trap door functions have been proposed that are thought to be NP-hard (see related question), and some may even have a proven lower bound. My question is more fundamental: does it matter what the asymptotic lower bound is? If not, is the practical security of any cryptographic code at all related to any asymptotic complexity result?

Answer 1

Just because a lower bound has been shown does not necessarily make the problem good for crypto. For example, approximation algorithms or probabilistic algorithms could be used to break the system.

That said, I would imagine that a lower-bound could strengthen the argument for a particular system. So, it would seem that a lower bound is neither necessary nor sufficient, but would have it's benefits.

Answer 2

The practical security of any cryptosystem ultimately depends on the separation of the complexity classes P and NP. Until that day comes, and let's not hold our breath waiting for someone to prove the P vs NP conjecture either way, no cryptosystem can be said to be so "complex" as to be unbreakable. For example, say you could show that a certain cryptosystem could be broken by proving that the solution to cracking the algorithm could be reduced to just being able to guess a 256 bit key. Given the laws of physics as we know it and how these laws apply to our current state-of-the-art computer systems, guessing a 256 bit key is considered to be "hard". But how do we know that in some distant galaxy far, far away , there isn't some super-intelligent race that has machines that can guess big keys? We don't and that is why proving that P does not equal NP is so hard to do: you have to show a mathematical proof that there can be no possible shortcut (algorithm) for solving an NP complete problem AND you have to be able to prove that HAL will never be able to guess a 256 bit key with reasonable consistantcy in polynomial time. Good luck!

Answer 3

Of course, asymptotic bounds (depending on some security parameter $n$, often the key size) alone say nothing about the practice, as in practice we do not use $n \to \infty$, but a fixed $n$.

So while these asymptotic bounds on the hardness are nice, quite more usable are bounds for the actually used values. Something like

Breaking AES with a key size of 128 bit takes at least $2^{100}$ steps of calculation.

is much more useful than something like

Breaking an AES-like algorithm (defined here) with unlimited key-size $n$ takes (for $n \to \infty$) at least $\Omega(2^{n})$ steps,

as the last one does not say how large one has to make $n$ to attain any security at all, and thus does not say anything about the actually used AES.

For RSA, where different key-sizes are actually usable, we also are quite more interested in bounds (still depending on $n$) which are valid for the values in use.