0

We have the following theorem:

Let $\Pi$ be a perfectly-secret scheme over message space $M$, and let $K$ be determined by $Gen$. Then $|K| ≥ |M|$.

How can we prove that the above theorem is valid for almost perfect secrecy? The definition for almost perfect secrecy is as follows:

The encryption scheme $\Pi = (Gen,Enc,Dec)$ over a message space $M$ is almost perfectly secret or $\varepsilon$-perfectly secret if for every probability distribution over $M$, $\forall m \in M$ and $\forall c \in C$ for which $Pr[C = c] > 0$ and for a constant $\varepsilon < 1$:

$$|Pr[M = m|C = c] - Pr[M = m]| < \varepsilon$$

EDIT

enter image description here

SEJPM
  • 45,967
  • 7
  • 99
  • 205
Don
  • 1
  • 1
  • 2
    Did you look at the proof of the original statement and try to adapt it? – SEJPM Aug 03 '16 at 12:03
  • The definitions seem to be missing some details. What is K? What is C and c, and how can M = m if m is an element in M? – Guut Boy Aug 03 '16 at 22:28
  • ... my point is that we can of course try to guess, but it might be easier to answer your question if you are a bit more precise. – Guut Boy Aug 03 '16 at 22:31

1 Answers1

1

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$. This violates your definition of $\epsilon$-perfect secrecy, thus we must have $|K| \geq |M|$.

Note that there is a different definition of an $\epsilon$-perfect secrecy, the one requiring that an adversary playing a game could not succeed with a probability higher than $\frac{1}{2} + \epsilon$. Such definition allows to have fewer keys than messages. For more information, have a look at Almost (epsilon) perfect secrecy - lower bound of keyspace size

mercury0114
  • 257
  • 1
  • 7
  • @HilderVitorLimaPereira Why should the last statement of your comment be true? Each term in a sum is not conditioning on c anymore. $Pr(m | c)$ indicates the probability that a message m was encrypted to the observed ciphertext c. I chose a message m that can not be encrypted to c. So if I observe a ciphertext c, then I know for sure that the plaintext message is not m, i.e. $P(m | c) = 0$ – mercury0114 Mar 18 '21 at 20:53
  • @HilderVitorLimaPereira For a fair dice Pr(D=2) + Pr(D=4) is 2/6, but Pr(D=2k | D<5) is 1/2 – mercury0114 Mar 19 '21 at 09:34