Perfect security - is this definition correct?

Awerde

7/3/23, 4:23 PM

I have this definition:

each ciphertext is equally probable for a given plaintext and key chosen at random

I know that perfect security can be defined as $$\forall c \in \mathcal{C} \ \forall m_1,m_2\in \mathcal{M} \ Pr[Enc_k(m_1)=c \ for \ k \ random]=Pr[Enc_k(m_2)=c \ for \ key \ random]$$

Are these equivalent?

The easiest thing to do is to somehow show that the first definition implies the second one and vice-versa. Although I have problems with understanding these conditions. If I rewrite the first definition in a more mathematical way: Let $m \in \mathcal{M}$ $$ \forall c_1, c_2\in \mathcal{C} \ Pr[Enc_k(m)=c_1]= Pr[Enc_k(m)=c_2] $$

However, this didn't help me much. My second thought was something along the lines: if the probability for every cipher is equal then it must be equal to $\frac{1}{|\mathcal{C}|}$ (I can't imagine it could have any other value). If this is the case for every message, then it also satisfies the second definition as every probability has the same value.

I'm not sure about this reasoning, is this ok or completely wrong?

0 + 0

perfect-secrecy

Maarten Bodewes

7/3/23, 10:24 PM

I don't see any particularly wrong with the reasoning and yes, I think the first sentence and formula are kind of the same, but the second formula probably fits it better.

meshcollider

7/3/23, 11:24 PM

You need to include that $k$ is drawn uniformly from the keyspace for the probabilities in the second equation to make sense. It looks like a fixed key $k$ at the moment.

Maarten Bodewes

7/3/23, 11:27 PM

Yeah, true, because the definition reads "key chosen at random" while the message is fixed.

Awerde

7/4/23, 8:09 PM

My reasoning is in one way (first -> second), how to prove it the other way?

Maarten Bodewes

7/5/23, 2:32 PM

I'm not so good at rewriting these kind of proofs; for me this is kind of self-evident. Maybe somebody else can step in and help.

Elon Musk

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

EN: Perfect security - is this definition correct?

TH: การรักษาความปลอดภัยที่สมบูรณ์แบบ - คำจำกัดความนี้ถูกต้องหรือไม่?

RO: Securitate perfectă - este corectă această definiție?

RU: Совершенная безопасность — правильно ли это определение?

VI: Bảo mật hoàn hảo - định nghĩa này có đúng khô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.