Score:2

Katz/Lindell 2.4 - Generalizing from 2 messages to any message space?

fr flag

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).

Myath avatar
in flag
What do you mean "the solution"? Does the book provide said solution?
Foobar avatar
fr flag
Yes, the book does.
kelalaka avatar
in flag
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?
Score:3
ru flag

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.

Daniel avatar
ru flag
@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.
Daniel avatar
ru flag
@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.
Daniel avatar
ru flag
@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$".
kelalaka avatar
in flag
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.
Daniel avatar
ru flag
@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]$....
Daniel avatar
ru flag
@kelalaka ... you choose the distribution that assigns $1/2$ to $m$ and $1/2$ to $m'$, and $0$ to all other messages, which can be phrased as the distribution that is uniform over $\{m,m'\}$, and then apply perfect secrecy to this distribution, to get what you want. The proof is 100% complete at this point, no general cases need to be addressed.
Foobar avatar
fr flag
@Daniel Thanks for the detailed explanation! I have added the full problem text to make things more clear. It says the equation must hold for every $m, m' \in M$ (not sure if that changes anything)
Foobar avatar
fr flag
@Daniel I have also added in the full solution
Daniel avatar
ru flag
@Roymunson The exercise asks you to prove that, assuming perfect secrecy (which talks about arbitrary distributions over the whole message space), it follows that, **for every pair** $m,m'$ and for every ciphertext $c$, $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$. To prove such statement you begin by fixing $m,m'$ and $c$, so for the rest of the proof these values are just constants and you can apply perfect secrecy with *any* distribution of your choice, in particular, you can use the one that assigns $1/2$ to both $m$ and $m'$ and zero to all other messages.
Foobar avatar
fr flag
@Daniel Is it not implicit that $M$ could be any distribution?
Daniel avatar
ru flag
@Roymunson The confusion here really comes from math and proofs, not cryptography. You have two definitions: a scheme is perfectly secure if, for every distribution $M$ over the message space $\mathcal{M}$, for every message $m$ and every ciphertext $c$, it holds that $\Pr[M = m | C = c] = \Pr[M = m]$. On the other hand, let's give a name to the second notion, let's say a scheme is "variant" perfect secure if, for every pair of messages $m$ and $m'$, and every ciphertext $c$, it holds that $\Pr[\mathsf{Enc}_k(m) = c] = \Pr[\mathsf{Enc}_k(m') = c]$....
Daniel avatar
ru flag
@Roymunson ... Note that this second definition of "variant" perfect security does *not* talk about distributions over the message space at all, whereas the first definition does. These two notions are equivalent, even though, once again, one requires certain property to hold for *any* possible distribution, while the other does not talk about distributions at all.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.