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