I need some explanations about a cryptographic notion called unconditionally secure cryptosystem.
The definition is as follows:
$\forall m_0, m_1 \in M, \mid m_0\mid = \mid m_1\mid$.
$\forall c \in C, \text{ Pr}[\text{Enc}(k, m_0) = c] = \text{Pr}[\text{Enc}(k, m_1) = c].$
where $M$ is the set of clear messages, $C$ the set of encrypted messages, $Enc$ the encryption function and $k$ the key.
I understand the definition, but I don't know the practical use. Let's take some examples.
We consider $\Pi = (Gen, Enc, Dec)$ an unconditionally secure cryptosystem with messages defined as follows: $M=C=\{0,1\}^n$. For each function below, we have to say if the resulting cryptosystem remain unconditionally secure. ($x \cdot y$ is concatenation)
- $\text{Enc}'(k, m) = 0 \cdot \text{Enc}(k, m)$
- $\text{Enc}'(k, m) = \text{Enc}(k, m) \cdot \text{LSB}(m)$, with $\text{LSB}(m)$ is the lower weight bit of m
- $\text{Enc}'(k, m) = \text{Enc}(k, m \mid{}_{1..\mid{}m\mid{}/2}) \cdot \text{Enc}(k, m \mid{}_{\mid{}m\mid{}/2+1..\mid{}m\mid{}})$, with $m\mid{}_{i..j}$ denotes the bit sequence $i$ to $j$ of $m$
- $\text{Enc}'(k, m) = \text{Enc}(0^n, m)$, with $0^n$ is the string compound of $0$, $n$ times
- $\text{Enc}'((k_1,k_2), m) = \text{Enc}(k_1, m) \cdot \text{Enc}(k_2, m)$
- $\text{Enc}'(k, m) = \text{Enc}(k, m) \cdot k$
I hope that all these examples will help me to understand. Could someone help me with this? Thanks ;)
To prove that $Enc'$ is unconditionally secure, you must show the second condition in the definition. So, take the first as an example,
Let $m,m'$ be arbitrary messages in $M$. We know that $Pr[Enc(k,m)=c]=Pr[Enc(k,m')=c]$, furthermore, we know that $Pr[0\bullet Enc(k,m)=0\bullet c]=Pr[0\bullet Enc(k,m')=0\bullet c]$, so it must be the case that $Pr[Enc^'(k,m)=c]=Pr[Enc^'(k,m')=c]$ since $0\bullet Enc(k,m)=Enc^'(k,m), \forall m\in M$.
Therefore, the first is unconditionally secure.
Now look at the second one. Assume it is unconditionally secure, and I'll give a counterexample example, thus proving that it is not unconditionally secure.
Let $M=\{0,1\}$, $C=\{00, 10, 01, 11\}$, $m=0, m'=1$ and $c=00$. Then, $Pr[Enc^'(k,m')=c]=0$ but $Pr[Enc^'(k,m)=c]>0$. This is a contradiction, so the assumption must be false.
NOTE: See my comment on $M=C=\{0,1\}^n$. I'm assuming that was a mistake and that the ciphertext space can be larger than the plaintext space.