# Can a shift cipher attain perfect secrecy?

On a practice question for my intro cryptography exam, it asks the following:

Assuming that keys are chosen with equal likelihood, the shift cipher provides:

A) computational security

B) perfect secrecy

C) semantic security

D) none of the above

I chose "none of the above", though I wasn't too sure. But I was certain it was not "perfect secrecy". However, when I review the exam solution key, it says "perfect secrecy" is, in fact, the answer.

Given that the message space of a shift cipher is huge, and the key space's cardinality is only 26, how can it possibly provide perfect secrecy under any circumstances?

-
Perhaps the exam referred to "shift cipher" as the textbook variant where each digit is encrypted with a different, independent key, which is really just a one-time-pad in disguise. I suggest this because the exam says "keys", whereas the traditional shift cipher has only one key. Not a very convincing argument, I agree, but otherwise, the exam is wrong and the correct answer is D. –  Thomas Dec 11 '12 at 21:52
@Thomas I thought the same, except we were taught the shift cipher with the correct method, and also taught the OTP separately... –  Eric Dec 11 '12 at 21:57
The obvious answer is D, however, I highly doubt that she's going to accept it, because her mistake is quite embarrassing. She's going to tell you that on each round a different key is used, something which is not in the wording that you/she provides. –  absinthe Feb 15 '14 at 9:58

The Caesar cipher (aka Shift cipher) has, as you said, a key space of size 26. To achieve perfect secrecy, it thus can have at most 26 plaintexts and ciphertexts. With a message space of one character (and every key only used once), it would fit the definition of perfect secrecy.

For the usual use with messages longer than one character, or multiple messages with the same key, none of the given options fit (other than the "None" option).

-
Great clarification--I think I'd best email my teacher and tell her it's wrong. Thanks! –  Eric Dec 11 '12 at 21:57
Just thought I'd let you know: She stood by her word; every letter is apparently treated as its own message. Seems silly to me... Thanks again, though! –  Eric Dec 11 '12 at 22:13
@Eric Even if you treat each letter as a single message, you get the requirement that you can't send more than one message using a fixed key. –  CodesInChaos Dec 12 '12 at 9:48
@CodesInChaos Yeah, it doesn't make intuitive sense, but I guess for the purpose of my exam, it's best to keep it in mind, then ditch the knowledge thereafter... Such is academia. –  Eric Dec 12 '12 at 14:57

For perfect secrecy:

$$number\_ of\_keys >= number\_of\_cipher >= number\_of\_plaintext$$

According to Shannon's perfect secrecy theorem:

let,

$$number\_ of\_keys = number\_of\_cipher = number\_of\_plaintext$$

then we have perfect secrecy if and only if:

1. each key is used with same probability, and
2. for each (plain,cipher) pair there is unique key.

So, with these rules, shift cipher has perfect secrecy.

-