# For perfect secrecy, does the keyspace need to be uniform?

The definition of perfect security is just that: $Pr(M =m | C=c) = Pr(M=m)$. We can prove that one time pad is perfectly secure for any distribution on a message space $M$, and it happens to be that the keyspace $K$ has a uniform distribution. Does that have to be true?

For example, let's say $M= \{0 \}$, $K=\{ 0,1 \}$ where $0$ is chosen with probability $p$ and $1$ chosen with probability $1-p$. Then we could have $c = m \oplus k$, and $c=0$ with probability $p$ and $c=1$ with probability $1-p$. Is this perfectly secure if $p \neq \frac12$?

• A scheme with only one possible plaintext is obviously perfectly secure: a ciphertext does not give an attacker any additional information about the plaintext because the attacker already knows what the plaintext is anyway. – fkraiem Sep 20 '18 at 18:31
• It's meant to be obviously perfectly secure because $Pr(M=m) =1$, but I was wondering if it didn't count as an example because the keyspace is not uniformly distributed. – eternalmothra Sep 20 '18 at 18:43

Let give an example with a bad distribution on (a different) message space with 2 elements.

$$\Pr[m=0] = p$$ and $$\Pr[m=1] = 1-p$$ and

$$\Pr[k=0] = p$$ and $$\Pr[k=1] = 1-p$$

• with $$p^2$$ prob the message was 0 and key was 0 and result 0

• with $$p-p^2$$ prob the message was 0 and key was 1 and result 1

• with $$p-p^2$$ prob the message was 1 and key was 0 and result 1

• with $$(1-p)^2$$ prob the message was 1 and key was 1 and result 0

if ($$p < 1/2$$):
when you see a 0 at the ciphertext the probability that key is 1 message is 1 is $$Pr_{m=1,k=1} = \frac{(1-p)^2}{(p^2)+(1-p)^2} > 1/2$$

Since $$p^2 < (1-p)^2$$. When $$p < 1/2$$ the ciphertext will leak information where as in an perfect secrecy this probability must be 1/2.

No information is leaked for ciphertext 0, in this example.

• "The message was $1$"? That is not possible since $M = \{0\}$. – fkraiem Sep 20 '18 at 18:29
• $M=\{0\}$ was an example, right? – kelalaka Sep 20 '18 at 18:31
• Oh, right. Your answer is still not satisfactory, though: you show one scheme which has non-uniform keys and is not perfectly scret, but that does not prove that it is not possible to have non-uniform keys and perfect secrecy. – fkraiem Sep 20 '18 at 18:36
• Simple fix: replace all occurences of "0.3" with $p$ and all occurences of "0.7" with $1-p$ (if you want to go fancy use $p$ for the plaintext distribution and $q$ for the key distribution). – SEJPM Sep 20 '18 at 18:41
• @kelalaka a few things with the edit: $\Pr_{m=1,k=1}$ must be smaller than 1/2 because the nominator is larger than the denominator and you can use a bulleted-list to improve the formatting on the listing of the probabilities. Additionally it needs to be shown that the probability of a given plaintext ($m=0$) underlying a given ciphertext doesn't match $p$ (=$\Pr[M=0]$). As for the $p$-$q$ split it should be possible even though I'm too tired right now to figure it out in detail. – SEJPM Sep 20 '18 at 19:25