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*and_{0}*x*, which he sends to the challenger._{1} - The challenger encrypts one of the plaintexts (chosen as random, as above) with his key and sends the result
*e*(_{k}*x*) to the attacker._{b} - 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*such that

_{1}*p*(

*x*) = 0 and

_{0}*p*(

*x*) = 1. He then transmits these two messages to the challenger, receives

_{1}*y*back, and sends back his guess of

_{b}*b'*=

*A*(

*y*). We know that this guess is correct (that is,

_{b}*A*(

*y*) =

_{b}*p*(

*x*) ) at least 0.5 +

_{b}*e*of the time.

But the messages *x _{0}* and

*x*were chosen such that

_{1}*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*in ECB mode means computing the ciphertext as

_{k}*y*=

*e*(

_{k}*x*)

_{1}*e*(

_{k}*x*)

_{2}*e*(

_{k}*x*)...

_{3}*e*(

_{k}*x*), that is encrypting each block separately and then concatenating the results):

_{n}
The attacker chooses two different block-size pieces of plaintext, call them *a _{0}* and

*a*. The two messages sent as part of the game above will be

_{1}*x*=

_{0}*a*and

_{0}a_{0}*x*=

_{1}*a*(ie. 2 blocks in size). That is, for

_{0}a_{1}*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*). All he now has to do is compare the two halves of the encrypted message. If they are the same, it means that

_{b}*b*= 0; if they are different, it means that

*b*= 1.

(Part of the Everything2 Crypto Project)