If m: message, M: message space, k: key, K: keyspace, c: cipher, C: cipher space and $E_k$: encryption function, such that $E_k(m) = c,\ m,m^* \in M,\ k\in K,\ c\in C.$

Then, what do the following notations actually mean in plain English?

enter image description here

What does it mean by $C=c$? If it means "If $C$ takes the value of $c$", to my understanding it is meaningless. Why would $C$ take the value of $c$? $c$ is a part of the whole message $C$. The same is true for $M$ and $m$.

  • $\begingroup$ the first: the probability two messages have the same encryption is negligible (instead of $|\mu|$ you probable mean |M|) $\endgroup$ – 111 Apr 10 '15 at 22:43

Imagine the following three scenarios. In each, you intercept an encrypted message and you know from context:

  • the message is a randomly chosen key in $\{0,1\}^n$ for some other cryptosystem
  • the message is either "It's a boy!_" or "It's a girl!", both are equally likely
  • the message is a vote from someone in a referendum; it's either "yes" or "no_", and the probability of it being "yes" (based on your knowledge of that person's preferences) is around 9/10.

Each of these scenarios describes a different context and prior knowledge you may have about the message (formally: a probability distribution on messages). An encryption scheme that's any good won't reveal anything more about the encrypted message than you already know in any of these scenarios. Even in the last case where you can make a pretty good guess at the message without breaking any encryption, the ciphertext shouldn't tell you anything more than you already know.

The last line of that definition translates to "what you know about $m$ after seeing $c$ is the same as what you would know about $m$ without seeing $c$" (for any kind of knowledge about $m$ that you may have).

  • $\begingroup$ What does it mean by $C=c$? If it means "If C takes the value of c", to my understanding it is meaningless. Why would C take the value of c? c is a part of the whole message C. The same is true for M and m. $\endgroup$ – user23794 Apr 14 '15 at 18:01
  • 1
    $\begingroup$ Capital $M, C$ are random variables. The experiment is the following: pick $m$ from some probability distribution on the message space, create a key $k$ with Gen then create $c = Enc_k(m)$ and output $c$. $\endgroup$ – Bristol Apr 14 '15 at 19:51

This would read out to the following:

(I'm citing myself here)

An encryption scheme, defined by key generator, encryption function and decryption function over a message space $M$ is perfectly secret if for every probability for a message $m$, for every message $m$ and every ciphertext $c$ which might occur ($Pr[C=c]>0$), ......

the probability that the message M is actually m if the ciphertext C is actually c is the same as it would be without knowing c.

Shortly speaking: Knowing the ciphertext doesn't help you in guessing the message.

  • $\begingroup$ I have just started my Cryptography course. I am finding trouble understanding these highly mathematical notations. Can you please tell me how to get hold of those notations, especially, those are related to probabilities? Is there anything I can do to improve my understanding? $\endgroup$ – user23794 Apr 11 '15 at 10:51
  • $\begingroup$ remember your high school time (assuming you had probability theory). Pr[X=k] means the probability that the random variable X takes the value k. Pr[X=k|Y=l] means the probability that X takes the value k in case Y took the value l. To improve your understanding, reading a book about probability theory might help. You'll need basic definitions, conditional probability, random variables, binomial distribution, birthday problem(s), random mappings. (according to the handbook of applied crypto) $\endgroup$ – SEJPM Apr 11 '15 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy