1
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ella Rose
    Aug 17, 2018 at 21:54

1 Answer 1

Reset to default
1
$\begingroup$

That predicate is basically telling you that the resulting ciphertext does not leak any information about the plaintext that has been encrypted.

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]$.

You can try to think of any other predicate. The important thing is that no such predicate must exist.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your response,i think that i understand the idea but i dont understand your last phrase "You can try to think of any other predicate. The important thing is that no such predicate must exist." $\endgroup$
    – t4rmo
    Aug 18, 2018 at 9:03
  • $\begingroup$ 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. $\endgroup$
    – Ginswich
    Aug 18, 2018 at 10:36
  • $\begingroup$ Now I understand everything, thanks for your explanation :) $\endgroup$
    – t4rmo
    Aug 18, 2018 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.