Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
4  
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
1  
@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
2  
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 at 9:58

2 Answers 2

up vote 4 down vote accepted

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).

share|improve this answer
    
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
1  
@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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.