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*:

- The challenger chooses a random key
*k* and a random bit *b* (*b* is one bit of information, so *b*=0 or *b*=1)
- The attacker chooses two plaintexts
*x*_{0} and *x*_{1}, which he sends to the challenger.
- The challenger encrypts one of the plaintexts (chosen as random, as above) with his key and sends the result
*e*_{k}(*x*_{b}) to the attacker.
- The attacker (presumably) analyzes the ciphertext that he was sent, and sends back his "guess"
*b'* of which of the two plaintexts was encrypted.
- 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* = *e*_{k}(*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 *x*_{0} and *x*_{1} such that *p*(*x*_{0}) = 0 and *p*(*x*_{1}) = 1. He then transmits these two messages to the challenger, receives *y*_{b} back, and sends back his guess of *b'* = *A*(*y*_{b}). We know that this guess is correct (that is,*A*(*y*_{b}) = *p*(*x*_{b}) ) at least 0.5 + *e* of the time.

But the messages *x*_{0} and *x*_{1} were chosen such that *p*(*x*_{b}) = *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* = *x*_{1}x_{2}x_{3}...x_{n}, then applying a block cipher *e*_{k} in ECB mode means computing the ciphertext as *y* = *e*_{k}(*x*_{1})*e*_{k}(*x*_{2})*e*_{k}(*x*_{3})...*e*_{k}(*x*_{n}), that is encrypting each block separately and then concatenating the results):

The attacker chooses two different block-size pieces of plaintext, call them *a*_{0} and *a*_{1}. The two messages sent as part of the game above will be *x*_{0} = *a*_{0} a_{0} and *x*_{1} = *a*_{0} a_{1} (ie. 2 blocks in size). That is, for *b* in {0, 1}, *x*_{b} = *a*_{0} a_{b}.

He will receive from the challenger the encrypted version of one of his messages; *e*_{k}(*x*_{b}) = *e*_{k}(*a*_{0}) *e*_{k}(*a*_{b}). 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)