5
$\begingroup$

I need to prove that the following encryption scheme is a perfect cipher:

Let $p$ be a prime. The secret key is a pair $(a,b)$ sampled uniformly at random from $\mathbb{Z}_p^* \times \mathbb{Z}_p$. An encryption of a message $M \in \mathbb{Z}_p$ is defined as:

$E_{a,b}(M) = aM + b \mod p$

The problem is that I don't understand what do I need show formally. What I could find regarding the definition of a perfect cipher is that knowing the ciphertext gives absolutely no information towards knowing the plaintext, or in a probabilistic language:

$\mathbb P(plaintext = P|C) = \mathbb P(plaintext = P)$, where $C$ is ciphertext.

Needless to say that it doesn't help me at all...

$\endgroup$
6
  • $\begingroup$ why you need b?why p is prime? $\endgroup$
    – curious
    Nov 1, 2013 at 16:33
  • $\begingroup$ @curious If it's more comfortable for you, you can ignore b and the requirement of p being a prime. How do you show that it's a perfect cipher ? $\endgroup$
    – Robert777
    Nov 1, 2013 at 16:39
  • $\begingroup$ Welcome to Crypto.SE. I hope you find the site useful. Is this homework? If so, we allow homework questions, but expect you to describe what you have tried that hasn't worked, etc. See here. $\endgroup$
    – mikeazo
    Nov 1, 2013 at 16:45
  • $\begingroup$ @mikeazo Yes it is. I don't understand what is the formal definition of a perfect cipher, so I don't even know where to start - what do I need to show ?? $\endgroup$
    – Robert777
    Nov 1, 2013 at 16:50
  • $\begingroup$ P.S., you are correct in your probability. Try applying Bayes rule. $\endgroup$
    – mikeazo
    Nov 1, 2013 at 16:51

1 Answer 1

5
$\begingroup$

Since this is homework, I'm not going to give the answer, but will hopefully point you in the right direction.

You are correct when you say for a perfect cipher, the probability should hold that $\mathbb{P}(P=m|C=c)=\mathbb{P}(P=m)$. In words, this means that given that you see the ciphertext is $c$ what is the probability of the plaintext being $m$ (note, I'm using $P$ for the plaintext space and $C$ for the ciphertext space). If being given the ciphertext does not help the adversary at all (i.e., the probability of any plaintext does not change at all given the ciphertext), then the cipher is said to be perfect. Almost all modern ciphers that we use today we cannot prove this property. For the cipher you are studying, however, it is possible.

By applying bayes rule, we get $\mathbb{P}(P=m|C=c)=\frac{\mathbb{P}(C=c|P=m)\mathbb{P}(P=m)}{\mathbb{P}(C=c)}$ and we want to show that this equals $\mathbb{P}(P=m)$. Therefore, if the other term on top cancels out the term on bottom, we would get what we want.

To help a little more, think about what the two terms are. On bottom we have $\mathbb{P}(C=c)$. In other words, what is the probability of each ciphertext (independent of plaintext). The ciphertext space is $\mathbb{Z}_p$ so the size of it is $p$.

The other term is $\mathbb{P}(C=c|P=m)$, meaning, given a plaintext message $m$, what is the probability that the ciphertext is some $c$. So, given a plaintext $m$ if all ciphertexts in $C$ are produced by the same number of keys, then $\mathbb{P}(C=c|P=m)$ would simply be $\mathbb{P}(C=c)$ in which case the two terms would cancel as we want.

I'll leave that up to you to show.

$\endgroup$
2
  • 2
    $\begingroup$ Actually, we don't need just that we could produce every single ciphertext $c$ using some key $(a,b)$, but that every ciphertext is produced by the same number of keys (since the key is sampled uniformly). $\endgroup$ Nov 1, 2013 at 17:17
  • $\begingroup$ @PaŭloEbermann correct and important since the keyspace is larger than the ciphertext space. I'll fix it. $\endgroup$
    – mikeazo
    Nov 1, 2013 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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