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$ – mercury0114 Mar 16 at 21:35

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 Mar 17 at 19:43
  • 1
    $\begingroup$ @kodlu I had to revise my knowledge about the $\epsilon$-perfect secrecy and updated my answer now. $\endgroup$ – mercury0114 Mar 18 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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