🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: sci.crypt
Article #1780

Re: Cryptography and P=NP

#1780
From: Paul Rubin
Date: Mon, 16 Nov 1992 13:29
12 lines
1181 bytes
    >It is true that if P=NP then all cryptography everywhere (not just RSA)
    >is dead;

    Why?  Assuming you mean public-key, the question of whether there
    exist one-way functions is not dependent on P!=NP, right?

No.  All you need is a polynomial-time method to decide if a given
key is the right one for decrypting a given ciphertext.  If you have
any info at all about the nature of the traffic (e.g., it's English
text), you can guess and verify the secret key.  The difference
is that the problem instance is a block of ciphertext instead of
a public key from which to recover the private key.
Technical Details
Message-ID: <PHR.92Nov16132959@napa.telebit.com>
Path: arc1-ca.pugleaf.net!sparky!uunet!telebit!phr
References: <1992Nov15.110945.19939@ringer.cs.utsa.edu> <PHR.92Nov15203840@napa.telebit.com> <97800@netnews.upenn.edu>

Show Full Headers
Complete Article Headers
Newsgroups: sci.crypt
Path: arc1-ca.pugleaf.net!sparky!uunet!telebit!phr
From: phr@telebit.com (Paul Rubin)
Subject: Re: Cryptography and P=NP
In-Reply-To: weemba@sagi.wistar.upenn.edu's message of 16 Nov 92 14:52:03 GMT
Message-ID: <PHR.92Nov16132959@napa.telebit.com>
Followup-To: sci.crypt
Sender: news@telebit.com
Nntp-Posting-Host: napa.telebit.com
Organization: Telebit Corporation; Sunnyvale, CA, USA
References: <1992Nov15.110945.19939@ringer.cs.utsa.edu>
 <PHR.92Nov15203840@napa.telebit.com> <97800@netnews.upenn.edu>
Date: 16 Nov 92 13:29:59
Lines: 12