A cryptosystem is said to be semantically secure if it is secure against eavesdroppers.

I will describe this in the form of a game played between a challenger (an authorized user of the cryptosystem) and an attacker (someone who wishes to learn more about the plaintext and/or key).

Formally, a cryptosystem is (t, e) semantically secure if no attacker running in time t can win the following game with probability of at least 0.5 + e:

  1. The challenger chooses a random key k and a random bit b (b is one bit of information, so b=0 or b=1)
  2. The attacker chooses two plaintexts x0 and x1, which he sends to the challenger.
  3. The challenger encrypts one of the plaintexts (chosen as random, as above) with his key and sends the result ek(xb) to the attacker.
  4. The attacker (presumably) analyzes the ciphertext that he was sent, and sends back his "guess" b' of which of the two plaintexts was encrypted.
  5. The attacker wins the game if b = b'.

While this definition may seem a little convoluted, it is actually very strong. It implies that the attacker can not learn any property of the message (with a high enough probability). We can easily prove that, if a cryptosystem is (t, e)-semantically secure according to the definition above, then no attacker can "learn" any "property" of the plaintext from the ciphertext alone.

The terms in quotes are not defined formally. For the purposes of this proof, let's assume that a "property" is anything that can be expressed as a predicate p : P --> {0, 1}. For example, p could be "the least significant bit of the message" or "1 if the message has an odd number of 1 bits, 0 otherwise," etc. Also, we say that the attacker "learns" a property of the plaintext if he can, through some mechanism, find the true value of p(x) from the ciphertext with a high enough probability (more than 0.5, obviously; 0.5 is what he would get by guessing). We consider high enough to be 0.5 + e.

We will prove by contradiction. Assume that, for some predicate p, the attacker can deduce the true value of p(x) with probability of at least 0.5 + e from the ciphertext. That is, given a ciphertext y = ek(x), the attacker knows a function A(y) that is equal to p(x) with probability of at least 0.5 + e. If this is true, we will prove that the ciphertext is not semantically secure as defined above.

The proof is simple: the attacker constructs two plaintext messages x0 and x1 such that p(x0) = 0 and p(x1) = 1. He then transmits these two messages to the challenger, receives yb back, and sends back his guess of b' = A(yb). We know that this guess is correct (that is,A(yb) = p(xb) ) at least 0.5 + e of the time.

But the messages x0 and x1 were chosen such that p(xb) = b, so b' = b at least 0.5 + e of the time, which contradicts the hypothesis that the cryptosystem is semantically secure, q.e.d.

Block ciphers are semantically secure when applied on a plaintext equal to the size of the block. When naively run in electronic code book (ECB) mode, block ciphers are not semantically secure (in fact, they are perfectly insecure, that is e = 0.5; b can be guessed with 100% certainty); DES is semantically secure when run in cipher block chaining (CBC) mode or output feedback (OFB) mode (with some constraints).

Trivial proof that a block cipher is not semantically secure in electronic code book mode: (briefly: if a plain text x is represented as a sequence of blocks, x = x1x2x3...xn, then applying a block cipher ek in ECB mode means computing the ciphertext as y = ek(x1)ek(x2)ek(x3)...ek(xn), that is encrypting each block separately and then concatenating the results):

The attacker chooses two different block-size pieces of plaintext, call them a0 and a1. The two messages sent as part of the game above will be x0 = a0 a0 and x1 = a0 a1 (ie. 2 blocks in size). That is, for b in {0, 1}, xb = a0 ab.

He will receive from the challenger the encrypted version of one of his messages; ek(xb) = ek(a0) ek(ab). All he now has to do is compare the two halves of the encrypted message. If they are the same, it means that b = 0; if they are different, it means that b = 1.

(Part of the Everything2 Crypto Project)