0
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ Did you look at the proof of the original statement and try to adapt it? $\endgroup$ – SEJPM Aug 3 '16 at 12:03
  • $\begingroup$ 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? $\endgroup$ – Guut Boy Aug 3 '16 at 22:28
  • $\begingroup$ ... 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. $\endgroup$ – Guut Boy Aug 3 '16 at 22:31
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ @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$ $\endgroup$ – mercury0114 Mar 18 at 20:53
  • $\begingroup$ @HilderVitorLimaPereira For a fair dice Pr(D=2) + Pr(D=4) is 2/6, but Pr(D=2k | D<5) is 1/2 $\endgroup$ – mercury0114 Mar 19 at 9:34

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.