home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 4877 < prev    next >
Encoding:
Text File  |  1992-11-17  |  1.1 KB  |  28 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!telebit!phr
  3. From: phr@telebit.com (Paul Rubin)
  4. Subject: Re: Cryptography and P=NP
  5. In-Reply-To: weemba@sagi.wistar.upenn.edu's message of 16 Nov 92 14:52:03 GMT
  6. Message-ID: <PHR.92Nov16132959@napa.telebit.com>
  7. Followup-To: sci.crypt
  8. Sender: news@telebit.com
  9. Nntp-Posting-Host: napa.telebit.com
  10. Organization: Telebit Corporation; Sunnyvale, CA, USA
  11. References: <1992Nov15.110945.19939@ringer.cs.utsa.edu>
  12.     <PHR.92Nov15203840@napa.telebit.com> <97800@netnews.upenn.edu>
  13. Date: 16 Nov 92 13:29:59
  14. Lines: 12
  15.  
  16.     >It is true that if P=NP then all cryptography everywhere (not just RSA)
  17.     >is dead;
  18.  
  19.     Why?  Assuming you mean public-key, the question of whether there
  20.     exist one-way functions is not dependent on P!=NP, right?
  21.  
  22. No.  All you need is a polynomial-time method to decide if a given
  23. key is the right one for decrypting a given ciphertext.  If you have
  24. any info at all about the nature of the traffic (e.g., it's English
  25. text), you can guess and verify the secret key.  The difference
  26. is that the problem instance is a block of ciphertext instead of
  27. a public key from which to recover the private key.
  28.