Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.