As a newcomer to cryptography, I'm working on Exercise 2.12 in the book, Introduction to Modern Cryptography.It looks like this:

Using the proof of the theorem that says if $E$ is a perfectly secret encryption scheme, then $\lvert K\rvert \geq \lvert M\rvert$), I've shown that the lower bound for the size of the keyspace is as below: $$\lvert K\rvert \geq (1-\epsilon)\lvert M\rvert$$

But here's the problem: I proved this under the condition that $$\lvert\Pr[M=m\mid C=c]-\Pr[M=m]\rvert\leq\epsilon$$

So I think I should show that this definition is equivalent to the condition given in the exercise.

My question is whether the two definitions are equivalent, and if so, how can I prove it?

  • $\begingroup$ I'm curious how you proved it. If $|K|$ < $|M|$ there will be an impossible message-ciphertext pair (m, c). Since we can freely choose a distribution for $M$, let $P(m) > \epsilon$. Then $P(m) - P(m | c)$ > $\epsilon$. $\endgroup$ Commented Mar 16, 2021 at 21:35

2 Answers 2


Short answer: the two definitions are not equivalent.

Long answer:

  • The condition $|\Pr[M=m\mid C=c]-\Pr[M=m]|\leq\epsilon$ doesn't allow us to have less keys than messages. Encrypt an arbitrary message to get a ciphertext $c$, then use all keys to decrypt $c$. If $|K| \lt |M|$, there exists a message $m$ which can not be decrypted from $c$ using any key. Then $|\Pr[M=m\mid C=c]-\Pr[M=m]| = \Pr[M=m]$ and since we can assign an arbitrary distribution to our message space, we can make $\Pr[M=m] > \epsilon$

  • The definition of $\epsilon$-perfect secrecy given in the book (the one you show in the image) does allow us to have fewer keys than messages. For example:

    Suppose the message space $M$ contains all 4 English letter words, $|M|$ = $26^4$. Let's use a one-time-pad encryption scheme without the identity key, thus $|K|$ = $|M| - 1$.

    Any adversary playing a game will choose two messages $m_0$, $m_1$. If our returned ciphertext $c=m_0$ the adversary knows for sure that the encrypted message is $m_1$. If our returned ciphertext $c=m_1$ the adversary knows for sure that the encrypted message is $m_0$. But if we return any other ciphertext, the one-time-pad scheme ensures that the best an adversary can do is to make a random guess. Therefore, the probability for an adversary to win a game is not greater than

    $1 \cdot \Pr(c \in \{m_0, m_1\}) + \frac{1}{2} \cdot (1 - \Pr(c \in \{m_0, m_1\}))$ = $\frac{1}{2} + \Pr(c \in \{m_0, m_1\}) \cdot \frac{1}{2} = \frac{1}{2} + \frac{1}{2|K|}$

    Thus, this scheme achieves $\epsilon$ perfect secrecy if $\epsilon \geq \frac{1}{2|M-1|}$

  • Let's find a lower bound for $\epsilon$. Suppose an adversary chooses $m_0$ and $m_1$ uniformly at random. Upon receiving a ciphertext $c$ it computes $M_c = \{ m | \exists k. enc_k(m) = c\}$ (it might be computationally infeasible to compute $M_c$, but we're not concerned about computational resources in this exercise).

    Note that at least one of $m_0, m_1$ is in $M_c$. If some $m_i \not \in M_c$ the adversary knows for sure that the encrypted message is the other one. If both messages are in $M_c$, the adversary makes a random guess.

    The probability of such adversary succeeding is $\frac{1}{2} \cdot \Pr(m_0, m_1 \in M_c) + 1 \cdot (1-\Pr(m_0, m_1 \in M_c))$ = $ 1 - \Pr(m_o, m_1 \in M_c) \cdot \frac{1}{2}$

    Let's estimate $\Pr(m_0, m_1 \in M_c)$ - the probability that both messages are in $M_c$. One message will certainly be in $M_c$ because we encrypted it to $c$, the other message is chosen uniformly at random from $M$, so the probability of both being in $M_c$ is $|M_c| / |M| \leq |K| / |M|$

    Thus an adversary can win a game with a probability $p \geq 1 - |K| / |M| \cdot \frac{1}{2} = \frac{1}{2} + \frac{1}{2} \cdot (|M| - |K|) / |M|$. If we want $\epsilon$ secrecy we must have $\frac{1}{2} + \epsilon \geq p$ which implies that:

    $|K| \geq |M| \cdot (1-2\epsilon)$

    note that I have not shown this lower bound is attainable.

  • $\begingroup$ can you please provide the details for the sake of other users reading this interesting question? $\endgroup$
    – kodlu
    Commented Mar 17, 2021 at 19:43
  • 1
    $\begingroup$ @kodlu I had to revise my knowledge about the $\epsilon$-perfect secrecy and updated my answer now. $\endgroup$ Commented Mar 18, 2021 at 15:25

This question has been discussed in Beating Shannon requires BOTH efficient adversaries AND non-zero advantage by Yevgeniy Dodis, NYU, 2012/053.

First, consider the Definition 1 and Remark 2. Remark 2 is as same as $\Pr[\mathsf{PrivK}^{\mathsf{eav}}_{\mathcal{A},\mathsf{\Pi}}]\leq\frac{1}{2}+\epsilon$.

enter image description here

Then consider the second part of the Theorem 1 without decryption error (for exactly being same as the thing that the question wants).

enter image description here

In the following, the proof is explained. Again, you can omit decryption error (for exactly being the same as the thing that the question wants).

enter image description here


Your Answer

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

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