1
$\begingroup$

Is the perfect secrecy of the one time pad dependent upon the xor "randomness preserving" property (xoring a uniformly random string with any string yields a uniformly random string)? I have seen different arguments in different sources.

For example, in this discussion, the first answer derives perfect secrecy without referring to the randomness preserving issue. The derivation starts with

$$Pr[C=c]=\sum{Pr[C=c|M=m']\cdot Pr[M=m']} =\sum{Pr[K=m'\oplus c]}\cdot Pr[M=m'] =\sum{2^{-n}}\cdot Pr[M=m'] =2^{-n}$$

where the second equation, which seems to be the core of the proof, is based on the fact there's a unique $K$ such that $K=m' \oplus c$. Ostensibly this would work for any other logical operator that has an inverse, not necessarily xor.

On the other hand, the other answer to that question states "The main point in any security proof for the one-time pad is that xoring a plaintext with a (uniformly) random bit string yields a (uniformly) random bit string no matter what the plaintext was.". If this is indeed the main point in the proof, then this proof would not work for other operators that have an inverse but don't preserve randomness.

Who is right?

Thanks!

$\endgroup$
  • $\begingroup$ I think the first answer is essentially just a proof of the more informal statement in the second answer. $\endgroup$ – Guut Boy Oct 24 '17 at 7:21
  • $\begingroup$ But at which point in the first answer we rely on the randomness preserving property? what part would not work for an operator that doesn't preserve randomness? $\endgroup$ – user1767774 Oct 24 '17 at 7:22
  • 1
    $\begingroup$ What if "randomness preserving" and "has an inverse" are the same thing? $\endgroup$ – fkraiem Oct 24 '17 at 7:39
  • $\begingroup$ Are they? could you refer me to a proof? $\endgroup$ – user1767774 Oct 24 '17 at 7:45
  • 1
    $\begingroup$ strictly speaking, you can use an OTP without XOR, so i'd argue "no" $\endgroup$ – dandavis Oct 26 '17 at 2:29
1
$\begingroup$

(Answering my own question).

One time pad retains perfect secrecy using any operator $\Delta$ showing the following property: for a plaintext $M$ and a key $K$, the cyphetexts $C = M \Delta K$ is such that there is a the same constant number of $K$s that encrypt $M$ to $C$, for any tuple ($M$, $C$). Specifically, if the length of the key equals to the length of the plaintext, then for each pair ($M$, $C$) there is a single, unique key that encrypts $M$ to $C$.

Therefore, not only xor but also other operators, such as applying Vigenère cipher with a uniformly generated key whose length equals to the message length, are suitable for one time pad.

the "random preserving" property, i.e. the uniform distribution of $C$ given a uniform distribution of $K$ and regardless of the distribution of $M$, is indeed equivalent to the above definition: if $\Delta$ preserves randomness there is necessarily the same number of $K$s for any pair ($M$, $C$) - otherwise, the distribution of $C$ wouldn't have been uniform; and if there is a constant number of keys for any pair then necessarily all cyphetexts are generated with an equal probability.

$\endgroup$

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.