Manuel Blum - Computer Science Department, UC Berkeley

Shafi Goldwasser - Laboratory for Computer Science, MIT

Crypto 84 - A Workshop on the Theory and Application of Cryptographic Techniques

This paper expands on the idea of probabilistic cryptography. The motivation behind probabilistic encryption is the ability for an adversary of a deterministic algorithm (such as RSA and Rabin) to compute partial information from the original message. A deterministic algorithm is one where a given input value will always produce the same output ciphertext. This property is held by both the RSA and Rabin cryptosystems.

A probabilistic encryption algorithm does not always produce the same output ciphertext. It produces a ciphertext that is one of a random set of possible ciphertexts for a given message. The goal of such algorithms is to provide polynomial security - a polynomial time adversary can not find one message m whose encodings he can distinguish from the encodings of a random message. In other words, an adversary gets no information from the ciphertext that aids in computing any portion of the cleartext.

Previous schemes which accomplished polynomial security were computed in a bit-by-bit fashion, which was very inefficient. This paper aimed to combine the efficiency of RSA and Rabin with the polynomial security of probabilistic algorithms. The computational cost for transforming an l-bit long cleartext into an (l + k)-bit long ciphertext is O(lk²/log k) for encryption and O(k³) + O(lk²/log k) for decryption. The value k is the security parameter. If the length of the message l < k the scheme is at least as fast as RSA or Rabin, and when l > k it is slightly faster. In both cases it adds the security of no partial information being able to be computed.

The algorithm given in this paper uses the notion of a cryptographically strong pseudo-random bit (CSPRB) generator. The CSPRB generator takes as input a k-bit random seed and produces as output a k^t-bit sequence, where t > 0 is fixed. The generator produces as output, high quality pseudo-random sequences of numbers where, if the k bit seed is unknown, the sequence of numbers cannot be distinguished from truly random sequences of the same length by any statistical test which runs in polynomial in k time.

To send an l-bit message m,

1. Obtain an l-bit output from a CSPRB generator, using a k-bit random input seed S.
2. Take the bitwise exclusive-or of the message m against the l-bit CSPRB output sequence: this is the ciphertext C.
3. Send the result of the exclusive-or C, along with a public-key encryption of S.

The recipient can decrypt the message by,

1. Decrypt the seed S using the private key.
2. Obtain the correct l-bit CSPRB output sequence using S.
3. Take the bitwise exclusive-or of the l-bit CSPRB output sequence with the ciphertext C, to get m.