# is the perfect secrecy of one time pad dependent on the xor randomness preserving property?

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!

• I think the first answer is essentially just a proof of the more informal statement in the second answer. – Guut Boy Oct 24 '17 at 7:21
• 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? – user1767774 Oct 24 '17 at 7:22
• What if "randomness preserving" and "has an inverse" are the same thing? – fkraiem Oct 24 '17 at 7:39
• Are they? could you refer me to a proof? – user1767774 Oct 24 '17 at 7:45
• strictly speaking, you can use an OTP without XOR, so i'd argue "no" – dandavis Oct 26 '17 at 2:29

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$.
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.