2
$\begingroup$

I'm trying to solve problem 2.4 in "Introduction to Modern Cryptography" (2nd edition) for self-study.

The problem asks to prove that perfect secrecy $$ Pr[M = m | C = c] = Pr[M = m] $$

implies

$$ Pr[Enc_k(m) = c] = Pr[Enc_k(m') = c] $$

The solution goes as follows:

Fix two messages $m, m'$ and a ciphertext $c$ that occurs with nonzero probability, and consider the uniform distribution over $\{m, m'\}$. Perfect secrecy implies that $Pr[M = m | C = c] = \frac{1}{2} = Pr[M = m' | C = c]$ So

$$ \frac{1}{2} = Pr[M = m| C = c] = \frac{Pr[C = c| M = m] * Pr[M = m]}{Pr[C = c]} $$

simplifies to

$$ \frac{\frac{1}{2}Pr[C = c | M = m]}{Pr[C = c]} $$

and so $Pr[C = c | M = m]$ = $Pr[Enc_k(m) = c]$ = $Pr[C = c]$. Since an analogous calculations holds for $m'$ as well, we conclude that $Pr[Enc_k(m) = c]$ = $Pr[Enc_k(m') = c]$

My issue is that this solution assumes a message space of 2, which is not generalizable.

Is there something I'm missing that makes this solution generalizable?

Edit: To be clear, here is the full problem text.

Lemma 2.4: An encryption scheme (Gen, Enc, Dec) with message space $M$ is perfectly secret if and only if Equation (2.1) holds for every $m,m' \in M$ and every $c \in C$. Where equation 2.1 is the 2nd equality in this post.

The problem asks to prove "other direction", which in this case means proving perfect secrecy => equation 2.1. (In the textbook, the reverse direction is already proved).

Improve this question
$\endgroup$
3
  • $\begingroup$ What do you mean "the solution"? Does the book provide said solution? $\endgroup$
    – Myath
    Dec 31, 2021 at 8:11
  • $\begingroup$ Yes, the book does. $\endgroup$
    – Foobar
    Dec 31, 2021 at 9:55
  • $\begingroup$ No, book doesn't have a solution. There is a solution that one can purchase seperately. As you see the result there is not $1/2$ so you might guess that it will cancel. Working larger message space will require $1/n$, play in this way? $\endgroup$
    – kelalaka
    Dec 31, 2021 at 10:10

1 Answer 1

Reset to default
3
$\begingroup$

This is not a claim about a "message space of size 2". The message space can be as large as you want, and the second characterization simply says that, for every $m,m'$ you pick from this message space, and for every possible ciphertext $c$, the probability that $m$ is encrypted as $c$ is the same as that of $m'$ being encrypted as $c$, which is written as $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$.

Now, in regards to the sketch of the solution you give, it's not really true that it is "assuming" a message space of size two. You want to prove a claim about two fixed messages $m$ and $m'$ (namely, you want to prove that $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$), and you want to do it while making use of perfect secrecy, which states that, for every message $\mu$ and every ciphertext $\gamma$,$^*$ and very importantly, for every distribution $M$ over the message space, it holds that $\Pr[M=\mu|C=\gamma] = \Pr[M=\mu]$.

Given that perfect secrecy holds for any distribution, we can arbitrarily choose any distribution that helps us towards proving our claim. The solution you're proposing simply takes the probability distribution that samples $m$ with probability $1/2$, $m'$ also with probability $1/2$, and all the other messages are sampled with probability $0$. One can also say that the message space is "restricted" to $\{m,m'\}$, but what is actually happening is what I said just before. Now that we have fixed the probability distribution, we also fix $\mu = m$ and $\gamma = c$ first, apply perfect secrecy, then fix $\mu = m'$ and apply perfect secrecy again, to obtain different expressions that can be manipulated to obtain what we need.

In short, this is just an artifact of the proof since the claim you want to prove is only concerned with a fixed pair of messages $m,m'$, so you can restrict a probability distribution to only these two elements, and apply perfect secrecy to this distribution.

$^*$ Notice I use other names instead of $m$ and $c$, since the latter are fixed already in our context.

Improve this answer
$\endgroup$
12
  • $\begingroup$ @kelalaka Unless I'm missing something this is not an assumption per se but rather a choice you can make in the proof for it to work. It is not an assumption in the sense that it is not that it doesn't work for more "general" settings or something like that. The claim itself deals with a fixed pair of messages $m,m'$. If one wants something more general then one should look at modifying the characterization rather than its proof. $\endgroup$
    – Daniel
    Dec 31, 2021 at 16:45
  • $\begingroup$ @kelalaka I'm not sure we're even talking about the same thing here. You're right that perfect security is not restricted to uniform, as it applies for any distribution (as I already mentioned in my answer), but the characterization being proved here talks about any fixed pair of messages $m,m'$. To prove that this characterization is equivalent to perfect security, one considers the message space to be $\{m,m'\}$ and applies perfect security then, but this is not a simplification, nor an assumption, this is just part of the proof. $\endgroup$
    – Daniel
    Dec 31, 2021 at 20:12
  • $\begingroup$ @kelalaka That said, to concretely address what you said: The characterization being proposed talks about pairs $m,m'$, so it is natural to consider a proof where perfect security is applied to the message space $\{m,m'\}$. I insist this is not a simplification, this is the way to proceed with the proof. If one wants a "generalization" then one must find another characterization to prove, like: "for every $c$ the value of $\Pr[\mathsf{Enc}_k(m) = c]$ is constant, no matter $m$". $\endgroup$
    – Daniel
    Dec 31, 2021 at 20:16
  • $\begingroup$ I'm into more educative. The answer of the book simplified as consider the uniform distribution over {m1,m2}, that was my point. Between the first and second paragraphs of your answer, the proof of uniform distribution of larger message space is missing! After that, it is nice to talk about arbitrary distribution. $\endgroup$
    – kelalaka
    Dec 31, 2021 at 20:23
  • $\begingroup$ @kelalaka This "consider the uniform distribution over $\{m,m'\}$" is not a simplification, it is the way to proceed with the proof. I think you're suggesting that this is just the "base case" for illustration purposes and that the general case is missing, but I insist that this is simply not the case. The claim is about a (fixed) pair of messages $m,m'$, they're already fixed once you go into the proof, and you can choose ANY distribution over the potentially-much-larger space to prove that $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$.... $\endgroup$
    – Daniel
    Dec 31, 2021 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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