Probabilistic public-key encryption
A minimal security requirement of an encryption scheme is that it must be difficult, in essentially all cases, for a passive adversary to recover plaintext from the corresponding ciphertext. However, in some situations, it may be desirable to impose more stringent security requirements.
The RSA, Rabin, and knapsack encryption schemes are deterministic in the sense that under a fixed public key, a particular plaintext m is always encrypted to the same ciphertext c. A deterministic scheme has some or all of the following drawbacks.
- 1. The scheme is not secure for all probability distributions of the message space. For example, in RSA the messages 0 and 1 always get encrypted to themselves, and hence are easy to detect.
- 2. It is sometimes easy to compute partial information about the plaintext from the ciphertext. For example, in RSA if c = me mod ?г is the ciphertext corresponding to a plaintext m, then
since e is odd, and hence an adversary can easily gain one bit of information about m, namely the Jacobi symbol (^).
3. It is easy to detect when the same message is sent twice.
Of coirrse, any deterministic encryption scheme can be converted into a randomized scheme by requiring that a portion of each plaintext consist of a randomly generated bitstring of a pre-specified length l. If the parameter l is chosen to be sufficiently large for the purpose at hand, then, in practice, the attacks fisted above are thwarted. However, the resulting randomized encryption scheme is generally not provably secure against the different lands of attacks that one could conceive.
Probabilistic encryption utilizes randomness to attain a provable and very strong level of security. There are two strong notions of security that one can strive to achieve.
- 8.46 Definition A public-key encryption scheme is said to be polynomially secure if no passive adversary can, in expected polynomial time, select two plaintext messages mi and m2 and then correctly distinguish between encryptions of mi and m2 with probability significantly greater than
- 8.47 Definition A public-key encryption scheme is said to be semantically secure if, for all probability distributions over the message space, whatever a passive adversary can compute in expected polynomial time about the plaintext given the ciphertext, it can also compute in expected polynomial time without the ciphertext.
Intuitively, a public-key encryption scheme is semantically secure if the ciphertext does not leak any partial information whatsoever aboirt the plaintext that can be computed in expected polynomial time.
8.48 Remark (perfect secrecy vs. semantic security>) In Shannon’s theory (see §1.13.3(i)), an encryption scheme has perfect secrecy if a passive adversary, even with infinite computational resources, can learn nothing about the plaintext from the ciphertext, except possibly its length. The limitation of this notion is that perfect secrecy cannot be achieved unless the key is at least as long as the message. By contrast, the notion of semantic security can be viewed as a polynomially bounded version of perfect secrecy — a passive adversary with polynomially bounded computational resources can learn nothing about the plaintext from the ciphertext. It is then conceivable that there exist semantically secure encryption schemes where the keys are much shorter that the messages.
Although Definition 8.47 appears to be stronger than Definition 8.46, the next result asserts that they are, in fact, equivalent.
8.49 Fact A public-key encryption scheme is semantically secure if and only if it is polynomially secure.
