
Perfectly Secret Encryption
Perfectly Secret Encryption
The Syntax of Encryption
An encryption scheme is defined by three algorithms Gen, Enc, and Dec, as well as aspecification of message space $\mathcal{M}$ with $|\mathcal{M}| > 1$
Gen
The key-generation algorithm Gen is a probabilistic algorithm that outputs a key $k$ chosen according some distribution.
We denote $\mathcal{K}$ the (finite) key space, i.e., the set of all possible keys that can be output by Gen.
Enc
The encryption algorithm Enc takes as input key $k \in \mathcal{K}$ and a message $m \in \mathcal{M}$, and outputs a ciphertext $c$.
Dec
The decryption algorithm Dec takes as input a key $k \in \mathcal{K}$ and a ciphertext $c \in \mathcal{C}$ and outputs a message $m \in \mathcal{M}$.
Perfect secrecy
DEFINITION 2.3
An encryption scheme (Gen, Enc, Dec) with message space $\mathcal{M}$ is perfectly secret if for every probability distribution for M, every message $m \in \mathcal{M}$, and every ciphertext $c \in \mathcal{C}$ for which Pr[C - c] > 0:
$$ Pr[M\ =\ m\ |\ C\ =\ c]\ =\ Pr[M\ =\ m] $$
An equivalent formulation of perfect secrecy
For every $m, m' \in \mathcal{M}$, and every $c \in \mathcal{C}$, we have
$$ Pr[Enc_K(m)\ =\ c]\ =\ Pr[Enc_K(m')\ =\ c] $$
PROOF
$$ \begin{aligned} Pr[C=c\ |\ M=m] &= Pr[Enc_K(M)=c\ |\ M=m] \ &= Pr[Enc_K(m)=c\ |\ M=m] \ &= Pr[Enc_K(m)=c] \end{aligned} $$
$$ Pr[M=m\ |\ C=c]\cdot Pr[C=c] = Pr[C=c\ |\ M=m]\cdot Pr[M=m] \ \because Pr[M\ =\ m\ |\ C\ =\ c]\ =\ Pr[M\ =\ m] \ \therefore Pr[C=c] = Pr[C=c\ |\ M=m] $$
$$ \begin{aligned} Pr[Enc_K(m) = c] &= Pr[C=c\ |\ M=m] \ &= Pr[C=c] \ &= Pr[C=c\ |\ M=m'] \ &= Pr[Enc_K(m')=c]
\end{aligned} $$
Perfect (adversarial) indistinguishability.
An adversary $\mathcal{A}$ first specifies two arbitrary messages $m_0, m_1 \in \mathcal{M}$. Next, a key $k$ is generated using Gen. Then, one of the two messages specified by $\mathcal{A}$ is chosen (each with probability 1/2) and encryped using $k$; the resulting ciphertext is given to $\mathcal{A}$. Finally, $A$ outputs a "guess" as to which of the two message was encrypted; $\mathcal{A}$ succeeds if it guesses correctly.
An encryption is perfectly indistinguishable if no adversary $\mathcal{A}$ can succeed with the probability better than 1/2.
The adversarial indistinguishability experiment $\mathsf{PrivK^{eav}_{\mathcal{A}, \Pi}}$:
- The adversary $\mathcal{A}$ outputs a pair of messages $m_0, m_1 \in \mathcal{M}$.
- A key $k$ is generated using Gen, and a uniform bit $b \in {0, 1}$ is chosen. Ciphertext $c \leftarrow \mathsf{Enc}_k(m_b)$ is computed and given to $\mathcal{A}$. We refer to $c$ as the challenge ciphertext.
- A outputs a bit $b'$.
- The output of the experiment is defined to be 1 if $b' = b$, and 0 otherwise. We write $\mathsf{PrivK^{eav}_{\mathcal{A}, \Pi}} = 1$ if the output of the experiment is 1 and in this case we say that $\mathcal{A}$ succeeds.
DEFINITION 2.6
Encryption scheme $\Pi = \mathsf{(Gen,Enc,Dec)}$ with message space $\mathcal{M}$ is perfectly indistinguishable if for every $\mathcal{A}$ is holds that
$$ \mathsf{Pr[Privk^{eav}_{\mathcal{A},\Pi}] = \frac{1}{2}} $$
LEMMA 2.7
Encryption scheme $\Pi$ is perfectly secret if and only if it is perfectly indistinguishable.
Limitations of Perfect Secrecy
THEOREM 2.11
If $(\mathsf{Gen, Enc, Dec})$ is a perfectly secret encryption scheme with message space $\mathcal{M}$ and key space $\mathcal{K}$, then $\mathcal{|K| \geq |M|}$.