home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / crypt / 3115 < prev    next >
Encoding:
Text File  |  1992-09-08  |  3.2 KB  |  78 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!cis.ohio-state.edu!daisy.learning.cs.cmu.edu!Marc.Ringuette
  3. From: Marc.Ringuette@daisy.learning.cs.cmu.edu
  4. Subject: Probabilistic encryption
  5. Message-ID: <9209060713.AA27357@news.cis.ohio-state.edu>
  6. Sender: daemon@cis.ohio-state.edu
  7. Organization: The Ohio State University Department of Computer and Information Science
  8. Date: Sun, 6 Sep 1992 05:27:00 GMT
  9. Lines: 67
  10.  
  11. A teaser to get your attention:  
  12.  
  13.     For the purpose of privacy, this scheme of Blum and Goldwasser's
  14.     is the best that academia has to offer thus far.
  15.         - Giles Brassard, "Modern Cryptography: A Tutorial"
  16.           (Springer-Verlag, 1988)
  17.  
  18. The scheme is a version of a technique called "probabilistic encryption" 
  19. and looks like a very interesting variation on the public-key theme.
  20. I'll define it briefly here.
  21.  
  22.  
  23. --- Blum and Goldwasser's probabilistic encryption ---
  24.  
  25. Let p and q be two randomly chosen distinct large primes congruent to 3
  26. modulo 4.  Their product n=pq is a Blum integer.  p and q are the
  27. private key and n is the public key.  Fact:  each quadratic residue
  28. (perfect square) modulo a Blum integer has exactly four square roots,
  29. one of which is itself a quadratic residue, and which is called the
  30. principal square root.  
  31.  
  32. Assumptions:  
  33.   - Square root modulo a Blum integer is trap-door one-way.
  34.   - Repeated squaring of a random seed x_0 modulo a Blum integer,
  35.     extracting the low-order bit at each iteration, yields a
  36.     cryptographically strong pseudo-random bit stream.
  37. Both of these assumptions have been proved correct assuming that 
  38. factoring is hard.
  39.  
  40. Method for enciphering a message:
  41.   Let m be some t-bit message.  Let x_0 be some random quadratic residue
  42. modulo n.  Repeatedly square x_0, t times, yielding the sequence x_0 ... x_t.
  43. Let b_i be the low-order bit of x_i, and let B be the t-bit sequence
  44. b_0 ...  b_t-1.  The encipherment of m is the pair of integers <x_t, m xor B>.
  45.  
  46. Method for deciphering a message:
  47.   Compute the sequence x_0 ... x_t-1 from x_t by repeatly extracting the
  48. principal square root of each x_i+1 to yield x_i.  Extract the low-order 
  49. bits b_0 ... b_t-1 and exclusive-or them with the ciphertext c to give
  50. the message m.
  51.  
  52. Speedups:
  53.   The low-order log(log(n)) bits of each x_i can be used without
  54. compromising the pseudo-random number stream.  x_0 can be computed
  55. from x_t using some number theory and a couple of modular exponentiations;
  56. once x_0 is known, decryption is as fast as encryption.
  57.  
  58. ----
  59.  
  60. To quote Brassard again:
  61.  
  62.    Not only is this scheme faster than RSA, but the difficulty of 
  63.    breaking it is proved equivalent to that of factoring and it leaks
  64.    no partial information on the cleartext if factoring is hard.
  65.  
  66. Some drawbacks:  the ciphertext is expanded by log(n) bits, so there's
  67. a small space cost.  The speed on long messages is one modular squaring
  68. per log(log(n)) bits, which is still too slow to be practical for
  69. encrypting very long messages.  There is no digital signature capability.
  70.  
  71. Still, the practicality of the algorithm and the excellent cryptographic
  72. guarantees makes it a very attractive method.  Does anyone know if it's
  73. gotten much attention?
  74.  
  75.  
  76. [ Marc Ringuette | Cranberry Melon University, Cucumber Science Department  ]
  77. [ mnr@cs.cmu.edu | 412-268-3728 |      ".surivorter erutangis a ma I"       ]
  78.