Proving two definitions of perfect security are equivalent

Anon

8/7/23, 6:38 AM

I'm trying to prove that the following two definitions are equivalent:

$\forall m\in M $ and $c\in C$ $\Pr[C=c \mid M=m]=\Pr[C=c]$

$\forall m_1,m_2 \in M $, $E_k(m_1)=E_k(m_2)$, where $E_k(m_i)$ stands for the distribution over $k$ of the encrypted message $m_i$.

First - just to make sure, I am indeed supposed to show two directions, right? (i.e. first $\Rightarrow$ second and second $\Rightarrow$ first). This is my understanding regarding showing an equivalence for any two definitions.

If so, I'm able to prove the direction first $\Rightarrow$ second but I'm unable to do the second direction. How do I use the fact that for every pair of messages I have some conclusion about any single general message $m$?

Thanks.

0 + 0

perfect-secrecy

Titanlord

8/7/23, 7:14 AM

I don't really understand the second definition. Do you mean something like $Pr[Enc_k(m_1) = c] = Pr[Enc_k(m_2) = c]$

Marc Ilunga

8/7/23, 1:31 PM

The second statement would somehow show that the encryption is not correct? Since you can not decrypt, the ciphertext is the same for all messages. On the bright side, very secure!

Anon

8/7/23, 2:27 PM

@Titanlord yes, exactly.

Score:1

Crypto

Titanlord

8/7/23, 8:18 AM

Yes, you are right, you need to prove both directions. In Katz & Lindell's textbook (2nd edition) you can find the proof for first $\Rightarrow$ second. The other direction is left for exercise. I try my best to give a correct solution for that.

First we have to know that the following holds:

$$ Pr[Enc_k(m) = c] = Pr[C = c | M = m] $$

First $\Rightarrow$ Second proves, that assuming $Pr[Enc_k(m_1) = c] = Pr[Enc_k(m_2) = c]$ is correct, then $Pr[C = c | M = m] = Pr[M = m]$ holds.

We want to show that assuming $Pr[C = c | M = m] = Pr[M = m]$ is correct, then $Pr[Enc_k(m_1) = c] = Pr[Enc_k(m_2) = c]$ holds.

My solution is:

$$Pr[Enc_k(m_1) = c] = Pr[C = c | M = m_1] = \frac{Pr[M = m_1 | C = c] \cdot Pr[C = c]}{Pr[M=m_1]} $$

Because we assumed that $Pr [ M = m_1 | C = c] = Pr[M=m_1]$ we get:

$$ \Rightarrow Pr[C = c] = Pr[C = c | M = m_2] = Pr[Enc_k(m_2) = c]$$

0 + 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Proving two definitions of perfect security are equivalent

TH: การพิสูจน์ว่าคำจำกัดความของการรักษาความปลอดภัยที่สมบูรณ์แบบสองคำนั้นเทียบเท่ากัน

RO: Demonstrarea a două definiții ale securității perfecte sunt echivalente

RU: Доказательство эквивалентности двух определений совершенной безопасности

VI: Chứng minh hai định nghĩa về bảo mật hoàn hảo là tương đương

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.