home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 4864 < prev    next >
Encoding:
Internet Message Format  |  1992-11-16  |  1.7 KB
  1. Xref: sparky sci.crypt:4864 sci.math:15048 comp.theory:2436
  2. Path: sparky!uunet!cs.utexas.edu!zaphod.mps.ohio-state.edu!darwin.sura.net!spool.mu.edu!olivea!sgigate!rutgers!igor.rutgers.edu!zodiac.rutgers.edu!leichter
  3. From: leichter@zodiac.rutgers.edu
  4. Newsgroups: sci.crypt,sci.math,comp.theory
  5. Subject: Re: Cryptography and P=NP
  6. Message-ID: <1992Nov16.102132.1@zodiac.rutgers.edu>
  7. Date: 16 Nov 92 15:21:32 GMT
  8. References: <1992Nov15.110945.19939@ringer.cs.utsa.edu> <PHR.92Nov15203840@napa.telebit.com>
  9. Sender: news@igor.rutgers.edu
  10. Followup-To: sci.crypt
  11. Organization: Rutgers University Department of Computer Science
  12. Lines: 23
  13. Nntp-Posting-Host: cancer.rutgers.edu
  14.  
  15. In article <PHR.92Nov15203840@napa.telebit.com>, phr@telebit.com (Paul Rubin)
  16. writes:
  17. > ... It is true that if P=NP then all cryptography everywhere (not just RSA)
  18. > is dead...
  19.  
  20. Actually, this is false.  If P=NP, then PUBLIC KEY cryptography is dead; but
  21. private key cryptography can, in principle, be much stronger.  It can, in
  22. fact, be arbitrarily strong.
  23.  
  24. The problem for public-key cryptography is that, given a ciphertext and the
  25. public key, I can guess private keys and check that I've got the right one in
  26. polynomial time by simply encrypting my proposed plaintext with the public
  27. key.  If I get the ciphertext back, I've got the key.
  28.  
  29. For private-key cyptography, I can guess all I like, but there's no way I
  30. can test the correctness of my guess with certainty.  Sure, as a PRACTICAL
  31. matter, I may have some known plaintext, or i can just recognize that I
  32. got English text back.  But we're not talking about "in practice" here.
  33.  
  34. Note that for a one-time pad, the system is unconditionally secure, even
  35. given the ability to compute non-computable functions.
  36.  
  37.                             -- Jerry
  38.