2
$\begingroup$

I know that if only one character is encrypted using a shift cipher, then the shift cipher is perfectly secure. But what if the space of keys is greater than the space of messages? Would it still be perfectly secure? I think it would still be a yes, but I don't know how to deal with unused keys.

The theorem 2.10 (Introduction to Modern Cryptography, Second Edition) states that a perfectly secret encryption scheme must have the size of the keys at least as big as the messages. The author proves it by contradiction, so it's actually hard to see what happens if the key space contains more elements.

$\endgroup$
2
  • 2
    $\begingroup$ It's perfectly secure in the same way a single-bit XOR cipher is perfectly secure when encrypting a single bit. $\endgroup$
    – forest
    Mar 30 at 3:56
  • $\begingroup$ @forest Why though? The answer of Daniel S shows a counterexample. $\endgroup$
    – ryko21x
    Mar 30 at 18:41

1 Answer 1

1
$\begingroup$

Not necessarily. Consider a Caesar shift cipher on the Roman alphabet of 26 characters. We map the letter to one of the numbers 0-25, say $x$ and add a key value $k\in [0,25]$ compute $y=x+k\mod {26}$ and then map back to the alphabet. If $k$ is chosen uniformly at random then this is perfectly secure. However, if we enlarge the range of $k$ to say $[0,30]$ this is no longer perfectly secure as values $x+0\mod {26}$, $x+1\mod{26}$, $x+2\mod{26}$, $x+3\mod{26}$ and $x+4\mod{26}$ are twice as likely as the other cipher texts. This gives significant information about $x$ and hence the plaintext. For example, if we see the ciphertext "b" corresponding to $y=1$ we have more evidence that $x=23, 24, 25, 0, 1$ than the other values. Bayesian statistics therefore increases our belief that the plaintext letter lies in the set {'x','y','z','a','b'} and decreases our belief that it lies outside this set. We would not be able to make this inference with a perfectly secure cipher.

Typically, to achieve the uniformity required for perfect security, the key space needs to be a multiple of a size of the ciphertext space and the keys selected uniformly at random. However one can achieve perfect security by other means (e.g. in the above scheme, if we select the keys $\{0,1,2,3,4,26,27,28,29,30\}$ with probability 1/52 and other keys with probability 1/26, then the shift cipher is still perfectly secure.

$\endgroup$
6
  • $\begingroup$ I think I got why they are twice as likely as the other cipher texts, since if $x=0$, then $0+1\mod\ 26 = 1 = 0 + 27\mod\ 26$. But why it gives more information about $x$ and hence the plaintext? Could you please elaborate more? $\endgroup$
    – ryko21x
    Mar 30 at 14:49
  • $\begingroup$ I've added some more words; let me know if further clarification is necessary. $\endgroup$
    – Daniel S
    Mar 30 at 15:49
  • $\begingroup$ I think I see it now: For an arbitrary message that is not in our "belief set" $m$, $P(M=m\mid C = y = 1) = 0$, meanwhile $P(M=m) = 1/26$. Thus, by definition it is not perfectly secure, right? $\endgroup$
    – ryko21x
    Mar 30 at 16:44
  • $\begingroup$ Almost. For a uniform message $M$ and for $m$ outside our belief set $P(M=m|C=y=1)=1/30$ and for $m$ inside our belief set $P(M=m|C=y=1)=1/15$. Both of these are distinct from the uniform prior 1/26 and so perfect security is not attained. $\endgroup$
    – Daniel S
    Mar 30 at 17:02
  • $\begingroup$ How did you get $1/30$ and $1/15$? If $y=1$ wouldn't we know that only the possible values are $x=23,24,25,0,1$ and hence if a message it's outside our belief set, $P(M=m\mid C=y=1) = 0$? $\endgroup$
    – ryko21x
    Mar 30 at 18:05

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.