P=?NP Doesn't Affect Cryptography In the following pair of postings to the Usenet newsgroup sci.crypt, I point out that the still-unsolved problem of whether "P=NP" has no practical bearing on problems in cryptography. Loosely speaking, the class, P, consists of all problems that can be solved by a computer in an amount of time that can be expressed as a polynomial in the size of the problem. The class NP consists of all problems whose solution can be verified in polynomial time. The belief that the P=NP problem is important to cryptography is widespread. See, for example, Bruce Schneier's otherwise excellent "Applied Cryptography, 2nd ed.," John Wiley & Sons, 1996, p. 239 ff. Here are the posts: ---------------------------------------------------- sci.crypt #43500 (28 more) Newsgroups: sci.crypt,alt.security.pgp From: reinhold@world.std.com (Arnold G Reinhold) Subject: P=?NP Doesn't Affect Cryptography Organization: A.G. Reinhold, Cambridge, MA Date: Thu Nov 02 15:35:51 EST 1995 Lines: 46 In another thread, Steve Morgan (smorgan@netcom.com) correctly points out: >Even if factoring *is* polynomial, it isn't necessarily practical. >I'm sure we all remember from our "sorting and searching" classes >just how slow O(n**2) algorithms are. And only a few applications >justify an O(n**3) algorithm. A polynomial algorithm of, say >O(n**20) is essentially intractable even for small values of n. Conversely, an algorithm that ran in O(exp(n**0.1)) would make factoring billion bit numbers easy. The equivalence relation used to define the class P is not a meaningful one when real computations are involved. Most polynomials represent a computation cost far to high to bear. Calling polynomial time algorithms "tractable" and exponential time algorithms "intractable" is an abuse of language that misleads people into thinking that P=?NP is somehow important to cryptography. For example, one respected contributor to this forum told the SSL mailing list: "One of the open questions in crypto is whether true one-way functions exist, functions whose inverse cannot be efficiently calculated. This is related to the well-known computer science question of whether complexity class P is different from NP. Until the latter is resolved there will be no assurance that computational cryptography is even theoretically possible. " Don't get me wrong, P=?NP is an important open problem in mathematics. But it has no relevance to whether widely used cryptographic algorithms are secure or not. The best one can hope for is that methods developed to prove or disprove P=NP might also help settle some practical questions as well. I shudder to think of the headline in the New York Times when a result is finally announced: "New Mathematical Proof Shakes/Relieves Codemakers" It just ain't so. Arnold Reinhold ---------------------------------------------------- sci.crypt #43713 (5 more) Newsgroups: sci.crypt,alt.security.pgp From: reinhold@world.std.com (Arnold G Reinhold) Subject: Re: P=?NP Doesn't Affect Cryptography Organization: A.G. Reinhold, Cambridge, MA Date: Wed Nov 08 13:56:59 EST 1995 Lines: 77 hpa@storm.net (H. Peter Anvin) writes: >Actually, P != NP is a necessary but not sufficient condition for the >existence of one-way functions. ... Well, yes and no. The problem is one of definitions. The standard complexity theory definition of a one-way function is a function in P whose inverse cannot be computed in polynomial time. From this definition, if one-way functions exist then obviously P!=NP. But to say that functions which are usefully "one-way" can't exist if P=NP is nonsense. In reality, polynomial time functions can be too hard to compute, while superpolynomial functions can be perfectly computable for all practical purposes. Bob Silverman of The MathWorks Inc. cites a very real example of the later: >... the Cohen-Lenstra prime-proving algorithm is *nearly* > polynomial in log N. Its time is O[(log N)^(logloglog N)] >logloglog N changes so slowly for practical-sized problems that the >complexity might as well be polynomial. It is o((log N)^4) for all N >less than 2.2 x 10^23 DIGITS "O[(log N)^(logloglog N)]" is a superpolynomial function of logN and so Cohen-Lenstra earns the complexity theory seal of intractability, yet, for practical computations all our problems should be so tractable. Consider a hypothetical function F, with the following properties: Computing F(n) requires n^20 steps Computing Finverse(n) requires exp(n^.1) steps By the complexity theory definition, F is a one-way function. From the standpoint of practical cryptography, Finverse would serve as a perfectly usable one-way function. Divide the natural numbers, Z, into two parts: H1 = [1,M] H2 = (M+1,infinity) where M is big from the point of view of computation, say 2^(2^1000)). Most of the results in classical complexity theory apply *only* in H2. In fact, any function H1 -> Z can be bounded by a polynomial of arbitrary degree. Indeed any such function is identical to a polynomial of degree at most M. However, all computers, past, present and future, only calculate in H1. Jay Sulzberger points out that even the use of "big O" notation, i.e. O(f), is inappropriate in H1. Computer scientists seem to think the ignored constants must be modest, a factor of 10 maybe, when in fact they could well be enormous. I suspect the undue attention paid to classical complexity theory arises from an inclination to assume that results that are true in H2 must somehow be sort of true in H1. But there is neither a theoretical nor a practical basis for this belief. Yet a whole generation of computer scientists wrongly believes that complexity theory illuminates computation and that the P=?NP problem is the missing link to a theoretical basis for cryptography. Christopher B. Browne (cbbrown@io.org) asks: "I'm not sure here if you're trolling ..." Nope, just trying to call attention to a naked emperor. Arnold Reinhold ---------------------------------------------------- http://world.std.com/~reinhold Intro and minor edit, May 30, 1996