5
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ 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. $\endgroup$
    – Thomas
    Dec 11 '12 at 21:52
  • 1
    $\begingroup$ @Thomas I thought the same, except we were taught the shift cipher with the correct method, and also taught the OTP separately... $\endgroup$
    – Cat
    Dec 11 '12 at 21:57
  • 3
    $\begingroup$ 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. $\endgroup$
    – absinthe_minded
    Feb 15 '14 at 9:58
6
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ Great clarification--I think I'd best email my teacher and tell her it's wrong. Thanks! $\endgroup$
    – Cat
    Dec 11 '12 at 21:57
  • 1
    $\begingroup$ 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! $\endgroup$
    – Cat
    Dec 11 '12 at 22:13
  • $\begingroup$ @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. $\endgroup$
    – CodesInChaos
    Dec 12 '12 at 9:48
  • 1
    $\begingroup$ @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. $\endgroup$
    – Cat
    Dec 12 '12 at 14:57
  • $\begingroup$ This is surely not academia :) $\endgroup$
    – eckes
    Jul 23 '16 at 2:22
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

Shift cipher or ceasar cipher attains perfect secrecy only in the special case with the assumption that $26$ keys are used in equal probability in the shift cipher, and to encrypt each symbol we use a different key which is choosen equiprobably (i.e. perfectly random) from the key space.

It is easy to check all keys given a plaintext when the key is fixed for a sequence of plaintext. but if we use different key for each symbol then it is not possible to check all keys.

Suppose that you have a sequence of plaintext symbols of length $100$. If each key for each symbol is chosen equiprobably then you land up with $26^{100}$ possible keys. That is not possible to exhaustively search.

Improve this answer
$\endgroup$
1
$\begingroup$

Shift cipher does not satisfy the perfect secrecy property if message length ≥ 2.

Directly quote from https://www.ics.uci.edu/~stasio/fall04/lect1.pdf

Proof:

Take $m_1 = “AB”, m_2 = “AZ”, c = “BC”$

Then $$ \exists k ∈ K, s.t.Enc(k, m_1) = c$$ Namely k = 1.

However, for all $k ∈ K$ we have $Enc(k, m2) \neq c$, and hence $$Prob[Enc(K, m_1) = c] = 1/26 $$ while $$Prob[Enc(K, m2) = c] = 0$$ So the perfect secrecy requirement is violated, which requires above two probabilities to be equal.

Improve this answer
$\endgroup$

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.