3
$\begingroup$

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

  • 0
    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?2012-09-12

1 Answers 1