1. Given:

    $m = \{0,1\}^{n}$; a plaintext message of length $n$ encoded in binary

    $k = randomshuffle([0, 1, ..., 2n-1])$; A secret key consisting out of unique numbers between 0 and $2n-1$ in a true random order. The key is only used once and preshared between sender and receiver.

  2. We create $t = m||NOT(m)$; a temporary variable with the original message plus the inverse of the original message. (The intention here is to make the number of 1's and 0's equal)
  3. We transpose $t$ using key $k$ as indices to create the ciphertext $c$.

    For example, the key 5-4-3-2-1-0 would reverse the order of the bits of $t$.

Full example:

  1. Given: m = 010 and k = 5-4-1-3-0-2
  2. We append the inverse of 010 (which is 101): t = 010101
  3. We tranpose t using k. The resulting ciphertext: c = 101100

To decrypt the ciphertext you would simply reverse the transposition using your key and drop the second half of the message.

Is this scheme unbreakable?


For a scheme to be information-theoretically secure, you need that $$\Pr[M=m\mid C=c]=\Pr[M=m\mid C=c^\prime]$$ for all $c,c^\prime$ (that is, any ciphertext has the same probability $M=m$, so the ciphertext doesn't change the probability $M=m$).

Let's suppose we have a $c$ and a $c^\prime$. Both of them have the same number of ones and zeroes, because both are half ones and half zeroes. That means there's a permutation that takes $c$ to $c^\prime$ (in fact, there are a lot of them, but pick one); call it $\sigma$. We want to show that the number of permutations taking $c$ to some $t_0$ is the same as the number taking $c^\prime$ to $t_0$.

We can convert a permutation $\pi$ taking $c$ to $t_0$ into a permutation $\pi\sigma^{-1}$ taking $c^\prime$ to $t_0$: $\pi\sigma^{-1}(c^\prime)=\pi(c)=t_0$. Likewise, if $\pi^\prime$ takes $c^\prime$ to $t_0$, then $\pi^\prime\sigma$ takes $c$ to $t_0$. Also, $\pi\sigma\sigma^{-1}=\pi\sigma^{-1}\sigma=\pi$, so the functions are inverses. So, there are exactly the same number of permutations taking $c$ to $t_0$ as taking $c^\prime$ to $t_0$, so $$\Pr[T=t_0\mid C=c]=\Pr[T=t_0\mid C=c^\prime]$$ for all $c,c^\prime,t_0$.

Lastly, we know that $\Pr[M=m]$ is the sum of the probability that $T=t$ for all $t$ which have $m$ as their first half. Since all these probabilities are independent of the ciphertext, so is $\Pr[M=m]$. This applies whether or not you consider that $\Pr[T=t]$ is zero if $t$'s first half and second half aren't bitwise inverses; no matter what, it doesn't depend on the ciphertext, and neither does $\Pr[M=m]$. So, this scheme is information-theoretically secure.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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