Are asymptotic lower bounds relevant to cryptography? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-07-17T07:24:00Z https://cs.stackexchange.com/feeds/question/1226 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/1226 16 Are asymptotic lower bounds relevant to cryptography? Micah Beck https://cs.stackexchange.com/users/1038 2012-04-11T16:44:36Z 2012-04-13T07:08:10Z <p>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. </p> <p>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}$).</p> <p>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? </p> <p>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.</p> <p>I believe that other trap door functions have been proposed that are thought to be NP-hard (see <a href="https://cs.stackexchange.com/q/356/98">related question</a>), 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?</p> https://cs.stackexchange.com/questions/1226/-/1241#1241 2 Answer by Ran G. for Are asymptotic lower bounds relevant to cryptography? Ran G. https://cs.stackexchange.com/users/157 2012-04-13T01:33:19Z 2012-04-13T01:33:19Z <p>I'll try to give a partial answer, since I'm not fully aware of how this issue is considered by the entire crypto-community (maybe repost on <a href="http://crypto.stackexchange.com">crypto.SE</a>?).</p> <p>I would say there are two "kinds" of cryptographers: <em>Theoretical</em> and <em>Practical</em>. I will not try to tell them apart (every practical-cryptographer is also a bit theoretician..) but I'll say that for theoretical cryptography - this issue doesn't really matter. For any security parameter, there will be an instance size that will provide that security level, and that is usually all that we care about.</p> <p>Practical cryptographers care a lot about the issue you mention. For a given security parameter (say $2^{1024}$) cryptographers try to come up with the most efficient protocols, shaving the constant as much as possible. Look for instance for NIST's <a href="https://en.wikipedia.org/wiki/Advanced_Encryption_Standard_process" rel="nofollow">AES</a> or <a href="http://csrc.nist.gov/groups/ST/hash/sha-3/index.html" rel="nofollow">SHA-3</a> competition. The algorithms were required to be both secure and efficient. The issue here is that the notion of security is somewhat different from the "theoretical" one, and sometimes is not really asymptotic.</p> <p>A concrete example I can think of is the <a href="https://en.wikipedia.org/wiki/Discrete_logarithm" rel="nofollow">discrete log</a> or the <a href="https://en.wikipedia.org/wiki/DDH_assumption" rel="nofollow">DDH assumption</a> (the security of many cryptographic schemes are based on these assumptions). We <strong>assume</strong> that for some group $G$ computing the log takes $O(|G|)$ time. (We can't be sure: it might be that $\text{P}=\text{NP}$ and this problem can be solved in $O(\log |G|)$). Cryptographers <strong>DO</strong> care about the actual time it takes to compute the log. More accurately, they care alot about special cases for which computing the log is easy. In many papers you will see the sentence "Let $G$ be a group in which DDH is hard". See <a href="http://crypto.stanford.edu/~dabo/pubs/papers/DDH.pdf" rel="nofollow">this survey</a> for families of groups for which DDH is believed to be intractable (unless P=NP).</p>