# Are asymptotic lower bounds relevant to cryptography?

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?

-

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.

-
Are there results of the kind you describe: concrete lower bound for "steps of calculation" to break AES or RSA? Or are you just saying that would be "more usable" if they did exist? –  Micah Beck Apr 25 '12 at 20:06
For AES, I know of no ones (though there are some results of the form "Attacks by differential|linear cryptanalyis take longer than $2^n$ encryptions" or similar, I think.) For RSA, I think there are only reductions to the RSA asumption (from plaintext recovery) or to factoring the modulus (from key recovery), but I don't know if these deliver any concrete bounds for real-live moduli. So, this is more of a "it would be better if we had those". –  Paŭlo Ebermann Apr 25 '12 at 20:58

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.

-
So if lower bounds are not the key to security, what makes us think that any particular system is secure (eg RSA)? Are security experts just hoping? I learned about public key cryptosystems in school, but now I don't know why I should have any confidence in them, even if P != NP and factoring is asymptotically hard and etc. etc –  Micah Beck Apr 25 '12 at 0:04
@user19614, The way my first crypto professor put it, a bunch of really smart people have been trying and haven't broken it yet. –  mikeazo Apr 25 '12 at 0:06
The same was true for Fermat's Last Theorem for 358 years. –  Micah Beck Apr 25 '12 at 1:31
@user19614, oh yes. There is always the chance that someone will develop a fast factoring algorithm or a practical quantum computer tomorrow and the whole world would panic. –  mikeazo Apr 25 '12 at 11:28
If a quantum computer were to be developed tomorrow, the world would have time to react, shifting to new forms of crypto. If a fast factoring algorithm were developed, there might be no lead time before it were deployable. In the realm of "anything could happen" the development of a new algorithm is hardly pie in the sky! –  Micah Beck Apr 25 '12 at 12:36