home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15065 < prev    next >
Encoding:
Text File  |  1992-11-16  |  2.6 KB  |  52 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
  3. From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
  4. Subject: Re: ok, i'll bite.
  5. Message-ID: <1992Nov16.190432.25281@CSD-NewsHost.Stanford.EDU>
  6. Sender: news@CSD-NewsHost.Stanford.EDU
  7. Organization: Computer Science Department,  Stanford University.
  8. References: <92320.214859RVESTERM@vma.cc.nd.edu>
  9. Date: Mon, 16 Nov 1992 19:04:32 GMT
  10. Lines: 40
  11.  
  12. In article <92320.214859RVESTERM@vma.cc.nd.edu> <RVESTERM@vma.cc.nd.edu> writes:
  13. >i understand "cryptography".  i understand "np".  someone please
  14. >explain the connection.
  15.  
  16. NP is the class of problems whose instances encrypt or hide their
  17. easily seen solution.  For example the set of composites is in NP:
  18. hidden in every composite pq is a factor between 2 and pq-1, an easily
  19. recognized key giving away the secret of pq's compositeness.
  20.  
  21. Cryptography is not defined as formally as NP, so one cannot hope for
  22. an exact correspondence.  For example the one-time-pad cryptosystem
  23. does not have a corresponding NP notion.  Here one makes up a random
  24. bitstring R of length that of the message M, and sends R and R+M (their
  25. XOR) by two different routes.  Each of R and R+M by themselves looks
  26. completely random, but R+(R+M) = M.  Even exponentially much work
  27. cannot extract M from either R or R+M by itself, showing that the full
  28. resources of cryptography go beyond mere complexity obstacles of the
  29. kind posed by problems in NP-P.
  30.  
  31. (Around 1978 Adi Shamir found a neat generalization of this to n
  32. messages sent by that many routes, such that one must intercept at
  33. least m of them to read the message.  If m = n/2 the adversary must
  34. catch at least half the couriers to read the message, and block at
  35. least half to stop it getting through.  With only m-1 couriers the
  36. message remains completely hidden.  Other applications: shifty-eyed
  37. couriers, infiltrated cells, etc.  Technique: make the parts of the
  38. message the values of a degree m-1 polynomial at 1,2,...,n where the
  39. message itself is the value at 0.)
  40.  
  41. However as a corollary of plausible assumptions about channels,
  42. computing time, and application details, many practical cryptosystems
  43. turn out to be no harder to crack than to decide membership for some
  44. set in NP.  Cracking RSA for example reduces to factoring; it is in NP
  45. (but not known to be NP-hard) to decide whether the i-th bit of the
  46. larger factor of pq in the published key is 1.  (The converse
  47. reduction, from factoring to cracking, is not known for RSA, but it is
  48. known for a variant of RSA due to Michael Rabin, which is as hard to
  49. crack as to factor integers.)
  50. -- 
  51. Vaughan Pratt              A fallacy is worth a thousand steps.
  52.