An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information
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(lk2/log k) for encryption and O(k3) + O(lk2/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 kt-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,
The recipient can decrypt the message by,