Article View: sci.crypt
Article #1780Re: Cryptography and P=NP
From: Paul Rubin
Date: Mon, 16 Nov 1992 13:29
Date: Mon, 16 Nov 1992 13:29
12 lines
1181 bytes
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!phrReferences:
<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