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.

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

share|improve this question
    
why you need b?why p is prime? –  curious Nov 1 '13 at 16:33
    
@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 ? –  Robert777 Nov 1 '13 at 16:39
    
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. –  mikeazo Nov 1 '13 at 16:45
    
@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 ?? –  Robert777 Nov 1 '13 at 16:50
    
P.S., you are correct in your probability. Try applying Bayes rule. –  mikeazo Nov 1 '13 at 16:51

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
2  
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). –  Paŭlo Ebermann Nov 1 '13 at 17:17
    
@PaŭloEbermann correct and important since the keyspace is larger than the ciphertext space. I'll fix it. –  mikeazo Nov 1 '13 at 17:24

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.