Perfect secrecy theorem

Let $E = (E,D)$ be a Shannon cipher defined over $(K,M, C)$. Consider a probabilistic experiment in which $k$ is a random variable uniformly distributed over $K$. Then $E$ is perfectly secure if and only if for every predicate $Φ$ on $C$, for all $m_0,m_1 2M$, we have

$Pr[Φ(E(k,m_0))] = Pr[Φ(E(k,m_1))]$

I dont understand the meaning of $Φ$ in this theorem

• I edited your question to add mathjax, but I was not sure what the $2M$ is there for as it doesn't appear to be used anywhere. Aug 17, 2018 at 21:54

Assume that there exists some predicate $\Phi'$ such that $Pr[\Phi'(E(k,m_0)] \neq Pr[\Phi'(E(k,m_1)]$, for some $m_0,m_1$ pair. Then, if you are given a ciphertext that corresponds to some of those two messages, computing that predicate you can tell whether $m_0$ or $m_1$ was encrypted, which means that your cipher does not provide perfect secrecy.
For a more precise enunciation, you can check Lemma 2.4 of Katz & Lindell's "Introduction to Modern Cryptography" and its proof, where the predicate used there is $\Phi(c)$ := "$E(k,m)=c$", for $k\in K,m\in M$. And then, you have $Pr[E(k,m_0)=c] = Pr[E(k,m_1)=c]$.
• Your definition was that "for every predicate $\Phi$..." Thus, what I said must hold for every possible predicate. I gave you the example of "Introduction to Modern Cryptography", but you might want to try any other predicate of your own choosing. The "for every predicate" means that, no matter which predicate you choose, the equality must still hold if the cipher provides perfect secrecy. For instance, you could think of a predicate like "The most significant bit of the ciphertext is 1" and, still, the equality would be true for a perfectly secret cipher. Aug 18, 2018 at 10:36