Teorema

<aside> 💡

Se $(Gen, Enc, Dec)$ è uno schema di cifratura perfettamente segreto con spazio dei messaggi $M$ e spazio delle chiavi $K$, allora $|K| \geq |M|$

</aside>

Dimostrazione

Mostriamo che se fosse $|K|<|M|$ lo schema non potrebbe essere perfettamente segreto

Sia $|K|<|M|$, sia $M$ distribuita uniformemente e sia $c \in C$ tale che $Pr[C=c]>0$

Definiamo $M(c)\stackrel{\text{def}}{=} \{m |m = Dec_k(c), \text{ per qualche } k \in K\}$, chiaramente $|M(c)| \leq |K|$

Se $|K|<|M|$ allora $\exist m' \in M$ tale che $m' \notin M(c)$, ma allora risulta $Pr[M=m'|C=c] =0 \neq Pr[M=m'] = \frac{1}{|M|}$

Pertanto lo schema non è perfettamente segreto, quindi deve essere $|K|>|M|$