Re: Significance of "Relativizations of the P =? NP Question"

In article <43D65203.6040203@xxxxxxxxxxxxxxxx>,
Ralph Hartley <hartley@xxxxxxxxxxxxxxxx> wrote:
>The problem with that argument is that we don't really know if those
>protocols are secure.

True, but...

>In fact we know that if P=NP most, if not all, would *not* be secure. So
>we are *less* confident of that than we are that P!=NP.
>
>A proof that P!=NP (or that P=NP) would be a very surprising result! We
>would *expect* such a proof to lead to many other surprising results.
>
>So knowing that a proof of a certain kind that P!=NP would also result
>in the proof of some particular surprising results doesn't really add
>much information.

This isn't quite fair. Certainly one scenario is that P = NP and that
these protocols are not secure. However, if P != NP and we were able to
prove it, then this would presumably bolster our confidence that the
protocols *are* secure. Simultaneously proving that P != NP and that
the protocols are *not* secure is somewhat more surprising than proving
P != NP only.

For comparison, consider the statement "BPP has polynomial circuits."
Suppose that before proving or disproving this theorem, one observes
that if the proof of this fact were completely "constructive," it
would prove that P = BPP. You might argue that this observation gives
us no information; after all, maybe P does equal BPP. However, it seems
to be a difficult problem to prove that P = BPP. Knowing that a
"constructive" proof would imply P = BPP can guide one towards considering
"nonconstructive" proofs. And indeed, there is a relatively easy
nonconstructive proof that BPP has polynomial circuits, which you can
find in textbooks. Whether P = BPP remains an open problem.

Similarly, Razborov-Rudich suggests that it may be more promising to
look for a relatively easy non-natural proof of P != NP than to bang
one's head against the (most likely difficult) problem of breaking all
those cryptographic protocols.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • Re: How Secure is RSA-SHA1 ?
    ... RSA and SHA1 are the building blocks that could be used ... for building very secure as well as absolutely unsecure protocols. ... if authentication protocol was developed by your ...
    (microsoft.public.dotnet.security)
  • Re: FreeBSD 7.1 - rshd problems
    ... secure as is, perhaps being even disconnected from the internet. ... these "legacy" protocols are also quite secure with proper IPsec policies. ...
    (freebsd-questions)