🚀 go-pugleaf

A teaser to get your attention:  

    For the purpose of privacy, this scheme of Blum and Goldwasser's
    is the best that academia has to offer thus far.
		- Giles Brassard, "Modern Cryptography: A Tutorial"
		  (Springer-Verlag, 1988)

The scheme is a version of a technique called "probabilistic encryption" 
and looks like a very interesting variation on the public-key theme.
I'll define it briefly here.


--- Blum and Goldwasser's probabilistic encryption ---

Let p and q be two randomly chosen distinct large primes congruent to 3
modulo 4.  Their product n=pq is a Blum integer.  p and q are the
private key and n is the public key.  Fact:  each quadratic residue
(perfect square) modulo a Blum integer has exactly four square roots,
one of which is itself a quadratic residue, and which is called the
principal square root.  

Assumptions:  
  - Square root modulo a Blum integer is trap-door one-way.
  - Repeated squaring of a random seed x_0 modulo a Blum integer,
    extracting the low-order bit at each iteration, yields a
    cryptographically strong pseudo-random bit stream.
Both of these assumptions have been proved correct assuming that 
factoring is hard.

Method for enciphering a message:
  Let m be some t-bit message.  Let x_0 be some random quadratic residue
modulo n.  Repeatedly square x_0, t times, yielding the sequence x_0 ... x_t.
Let b_i be the low-order bit of x_i, and let B be the t-bit sequence
b_0 ...  b_t-1.  The encipherment of m is the pair of integers <x_t, m xor B>.

Method for deciphering a message:
  Compute the sequence x_0 ... x_t-1 from x_t by repeatly extracting the
principal square root of each x_i+1 to yield x_i.  Extract the low-order 
bits b_0 ... b_t-1 and exclusive-or them with the ciphertext c to give
the message m.

Speedups:
  The low-order log(log(n)) bits of each x_i can be used without
compromising the pseudo-random number stream.  x_0 can be computed
from x_t using some number theory and a couple of modular exponentiations;
once x_0 is known, decryption is as fast as encryption.

----

To quote Brassard again:

   Not only is this scheme faster than RSA, but the difficulty of 
   breaking it is proved equivalent to that of factoring and it leaks
   no partial information on the cleartext if factoring is hard.

Some drawbacks:  the ciphertext is expanded by log(n) bits, so there's
a small space cost.  The speed on long messages is one modular squaring
per log(log(n)) bits, which is still too slow to be practical for
encrypting very long messages.  There is no digital signature capability.

Still, the practicality of the algorithm and the excellent cryptographic
guarantees makes it a very attractive method.  Does anyone know if it's
gotten much attention?


[ Marc Ringuette | Cranberry Melon University, Cucumber Science Department  ]
[ mnr@cs.cmu.edu | 412-268-3728 |      ".surivorter erutangis a ma I"       ]