Semantic Security

Theorem 5.2 of the paper shows that there is no property of the plaintext message which can be efficiently estimated by looking at the ciphertext. Typical properties might be ``the last bit of the plaintext is 0'' or ``the number of 1's is twice as much as the number of 0's.'' In general, a property is defined in the paper as the value of a function $f(m)$ which takes a message as input and gives a number as output. If $f(m)$ is constant for all $m$, prediction of $f(m)$ is trivial. Similarly, if $f(m)$ is almost constant for almost all $m$, there is a simple algorithm which will be close to right with high prob

We wish to show that, except in the special cases we've mentioned, there is no efficient algorithm which will predict $f(m)$ from the ciphertext for $m$. If there were, we could run our algorithm to estimate $f(m)$ on the ciphertext from randomly generated $m$ until we found $m_1$, $m_2$ on which the algorithm behaved differently. But this would contradict the result of the previous section.

[The paper points out that it is not assumed that $f(m)$ is an easily computable function. I think this is a minor issue. The theorem really discusses the capabilities of a an easily computable program for estimating $f$.]