0
$\begingroup$

Prove or refute: For every encryption scheme that is perfectly secret it holds that for every distribution over the message space $M$, every $m, m'∈ M$, and every $c ∈ C$: $$Pr[M = m | C = c] = Pr[M = m' | C = c]$$

I am trying to solve problem $2.3$ of Katz's cryptography book and I have thought about doing the following but I don't know if what I think is right: I know that since the scheme is perfectly secret then $Pr[M = m | C = c] =Pr[M=m]$ and also $Pr[M = m' | C = c] =Pr[M=m']$, then I would have to show that $Pr[M=m]=Pr[M=m']$ for all $m,m'\in M$ in case the proposition is true, it is always true that in a secure encryption scheme you have to $Pr[M=m]=Pr[M=m']$ for all $m,m'\in M$?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Well according to Definition 1 in cs.umd.edu/~jkatz/crypto/f02/lectures/lecture3.pdf , the conditional probability of $C=c$ indeed can be omitted as you said. As for whether $Pr[M=m] = Pr[M=m']$, I don't think this is true, because the probability to select $m\in M$ is not necessarily equal to the probability to select $m'\in M$ - Think of an HTTP protocol, there are messages that cannot be sent, however a one time pad is perfectly secure for HTTP traffic, right? $\endgroup$ – yacovm Jan 28 '20 at 0:09

Your Answer

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

Browse other questions tagged or ask your own question.