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

  • 2
    $\begingroup$ 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. $\endgroup$ – fkraiem Sep 20 '18 at 18:31
  • $\begingroup$ 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. $\endgroup$ – eternalmothra Sep 20 '18 at 18:43

Short answer No.

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.

| improve this answer | |
  • $\begingroup$ "The message was $1$"? That is not possible since $M = \{0\}$. $\endgroup$ – fkraiem Sep 20 '18 at 18:29
  • $\begingroup$ $M=\{0\}$ was an example, right? $\endgroup$ – kelalaka Sep 20 '18 at 18:31
  • $\begingroup$ 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. $\endgroup$ – fkraiem Sep 20 '18 at 18:36
  • $\begingroup$ 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). $\endgroup$ – SEJPM Sep 20 '18 at 18:41
  • 1
    $\begingroup$ @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. $\endgroup$ – SEJPM Sep 20 '18 at 19:25

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.