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?


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.

  • $\begingroup$ 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 $\endgroup$ – Micah Beck Apr 25 '12 at 0:04
  • 1
    $\begingroup$ @user19614, The way my first crypto professor put it, a bunch of really smart people have been trying and haven't broken it yet. $\endgroup$ – mikeazo Apr 25 '12 at 0:06
  • $\begingroup$ The same was true for Fermat's Last Theorem for 358 years. $\endgroup$ – Micah Beck Apr 25 '12 at 1:31
  • $\begingroup$ @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. $\endgroup$ – mikeazo Apr 25 '12 at 11:28
  • $\begingroup$ 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! $\endgroup$ – Micah Beck Apr 25 '12 at 12:36

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!

  • $\begingroup$ The One-Time-Pad is unbreakable. $\endgroup$ – mikeazo Apr 24 '12 at 14:13
  • $\begingroup$ @Mikeazo: Hi Mike, did Shannon offer a mathematical proof that the OTP is unbreakable? Could you supply a reference to this, I guess this guy is looking for lower bounds for solving an NP problem (cryptosystem) which is of course equivalent to separating P and NP? $\endgroup$ – William Hird Apr 24 '12 at 16:43
  • $\begingroup$ He did (netlab.cs.ucla.edu/wiki/files/shannon1949.pdf). Granted the OTP is not exactly related to the whole NP lower-bound given in the question. I just thought I'd point out that there is a perfectly secure cipher. $\endgroup$ – mikeazo Apr 24 '12 at 16:52
  • $\begingroup$ Hi Mike, I just re-read this paper again , read the last two paragraphs on page 704. Shannon never gives a mathematical proof for the security of the OTP, he only talks about the requirements of a perfect secrecy system. He shows that the OTP meets the requirements but he does not offer a mathematical proof (lower bound for the amount of work necessary to break a OTP cipher of length N) of security. Big difference, that is the P vs NP problem. $\endgroup$ – William Hird Apr 24 '12 at 18:32
  • 1
    $\begingroup$ The one-time pad has nothing to do with the P=NP problem. In fact, if you encrypt using a one-time pad, the unicity distance is the length of the text itself, and you can never even brute-force the result out, or even know if you have the right result without other information. $\endgroup$ – Joe Z. Jan 17 '13 at 13:11

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.

  • $\begingroup$ 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? $\endgroup$ – Micah Beck Apr 25 '12 at 20:06
  • $\begingroup$ 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". $\endgroup$ – Paŭlo Ebermann Apr 25 '12 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.