Score:2

Shift cypher, perfectly secure?

in flag

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.

forest avatar
vn flag
It's perfectly secure in the same way a single-bit XOR cipher is perfectly secure when encrypting a single bit.
in flag
@forest Why though? The answer of Daniel S shows a counterexample.
Score:1
ru flag

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.

in flag
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?
Daniel S avatar
ru flag
I've added some more words; let me know if further clarification is necessary.
in flag
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?
Daniel S avatar
ru flag
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.
in flag
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$?
Daniel S avatar
ru flag
Because for each $m$ outside of our belief set there is exactly 1 value of $k$ out of 30 that would lead to $y=1$ and for each $m$ in our belief set there are 2 values of $k$ out of 30 that would lead to $y=1$.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.