home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 4894 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  1.5 KB
  1. Xref: sparky sci.crypt:4894 sci.math:15088 comp.theory:2442
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!bu.edu!transfer.stratus.com!ellisun.sw.stratus.com!cme
  3. From: cme@ellisun.sw.stratus.com (Carl Ellison)
  4. Newsgroups: sci.crypt,sci.math,comp.theory
  5. Subject: Re: Cryptography and P=NP
  6. Message-ID: <1e99gaINNnmp@transfer.stratus.com>
  7. Date: 16 Nov 92 23:05:46 GMT
  8. References: <1992Nov15.110945.19939@ringer.cs.utsa.edu> <PHR.92Nov15203840@napa.telebit.com>
  9. Distribution: inet
  10. Organization: Stratus Computer, Software Engineering
  11. Lines: 22
  12. NNTP-Posting-Host: ellisun.sw.stratus.com
  13.  
  14. In article <PHR.92Nov15203840@napa.telebit.com> phr@telebit.com (Paul Rubin) writes:
  15. >It is true that if P=NP then all cryptography everywhere (not just RSA)
  16. >is dead
  17.  
  18. This isn't true.
  19.  
  20. You don't have to have an algorithm whose inversion is in NP to have it
  21. be unbreakable.  All you need is a lower bound on the power of the
  22. security parameter.
  23.  
  24. Ie., if the space-time required to break some algorithm is guaranteed
  25. of order at least k^5, then you know how big to choose k so that a computer
  26. using all the atoms of the universe would take billions of years to
  27. do the inversion.
  28.  
  29. Of course, I'm told that that's a problem perhaps as hard as P=?NP.
  30.  
  31. -- 
  32. -- <<Disclaimer: All opinions expressed are my own, of course.>>
  33. -- Carl Ellison                        cme@sw.stratus.com
  34. -- Stratus Computer Inc.    M3-2-BKW        TEL: (508)460-2783
  35. -- 55 Fairbanks Boulevard ; Marlborough MA 01752-1298    FAX: (508)624-7488
  36.