prove of disprove the modified shannon's theorem when the correctness requirement is relaxed

Wan

3/12/24, 10:20 AM

Suppose the correctness requirement of private-key encryption scheme is now relaxed to require only that $$ \Pr[Dec_k(Enc_k(m)) = m] \ge \frac{1}{2} + \epsilon. $$ Prove of disprove that if an encryption scheme satisfies the perfect secrecy and the relaxed correctness, then $|M| \le 2|K|$, where $M, K$ are the message space and the key space, respectively.

The following is my thinking. Assume $|M| > 2|K|$. For fixed $c \in M$, define $p(m) = \sum_{k \in K} \Pr[Dec_k(c) = m]$. Since $\sum_{m \in M} p(m) = |K| < \frac{1}{2}|M|$, there exists $m_0 \in M$ such that $p(m_0) < \frac{1}{2}$. I want to show that $\Pr[Enc_k(m_0) = c]$ is small and find $\Pr[Enc_k(m_0) = c] \ne \Pr[Enc_k(m_1) = c]$ for some $m_1$ which contradicts with perfect secrecy, but I failed.

Tanks for any help.

0 + 0

perfect-secrecy

Elon Musk

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

EN: prove of disprove the modified shannon's theorem when the correctness requirement is relaxed

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.