# Unconditionally secure cryptosystem

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 ;)

-
The phrasing "we have to say" sounds more like homework than like you're seeking understanding for if own sake. Please add the "homework" tag if applicable. Also: What have you tried? It cannot be right that you have no idea even for the function that throws away the key and substitutes zeroes. Or the one that appends the key in cleartext to the encrypted message. – Henning Makholm Sep 12 '12 at 0:18
It is not homework, I found this exercise on internet ;). Actually, I don't know the good way to formalize the answers. If we consider $Enc^'(k, m) = 0 \bullet Enc(k,m)$, then $Pr[Enc^'(k, m)=c] = Pr[0 \bullet Enc(k,m)=c] ?= Pr[0 \bullet Enc(k,m^')=c]$ – Jérôme Boé Sep 12 '12 at 0:38
How can $M=C=\{0,1\}^n$ when most of the $Enc^'$ functions involve concatenation? The ciphertext space would have to be larger than the plaintext space, right? – mikeazo Sep 12 '12 at 14:12

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.

-
Thanks. I think I understand better. For the fifth one, can I say that : $Pr[E((k_1,k_2),m)=c] = Pr[E((k_1,k_2),m')=c] \implies Pr[E(k_1,m)\bullet E(k_2,m)=c] = Pr[E(k_1,m')\bullet E(k_2,m')=c]$ – Jérôme Boé Sep 12 '12 at 22:00
@JérômeBoé, Your implication is correct, but doesn't really do much. You are trying to prove the first statement, the second statement is equivalent to the first, but you still haven't proven either. Start with things that are known to be true like $Pr[E(k1,m)]=Pr[E(k1,m')]$. Try then to combine the known true values to reach what you want to prove. – mikeazo Sep 13 '12 at 11:51