I'm taking a Coursera cryptography course. The definition of semantic security is hard to understand. I tried to restate it with some slight changes (the word "efficient" was in the original definition). Have I gotten it right?

The adversary chooses two messages: $m_0, m_1$. We encrypt one of these messages: $c \leftarrow E(k, m_b)$. The adversary has to guess which message was ciphered.

There are two events: $M_b = \{ \ \text{adversary $A$ decides that $m_b$ is ciphered} \ \}$.

$E$ is semantically secure if for all "efficient" adversaries $A$ advantage $\operatorname{Adv}[A, E] = \big| \ \Pr(M_0) \ - \ \Pr(M_1) \ \big|$ is negligible.

This means the adversary can't tell which of the two messages is ciphered.

What if it could? What does this definition mean in practice?

Update: in the original definition (which is given on a diagram and wasn't stated clearly) there is a concept of two experiments, $exp(b)=1$ when the adversary decides $m_b$ is ciphered. And events are: $M_b = \{ \ \text{$exp(b) = 1$} \ \}$. I don't get this part of definition.

  • $\begingroup$ Is the whole portion in the blockquote your modified definition? If so, what did the original definition say. $\endgroup$
    – mikeazo
    Jul 3 '13 at 19:24
  • $\begingroup$ mikeazo: I threw out the idea of experiment, $exp(b)=1$ when the adversary decides that $m_b$ is ciphered. So $M_b = \{ \ exp(b)=1 \ \}$. That was written on a diagram and I don't understand why this thing is needed here. $\endgroup$
    – koddo
    Jul 3 '13 at 22:02
  • $\begingroup$ That thing is needed to make semantic security possible. $\:$ Consider an adversary that always $\hspace{.47 in}$ decides that $m_{\hspace{.01 in}0}$ is ciphered. $\:$ Another thing that's needed is for $m_{\hspace{.01 in}0}$ and $m_1$ to have equal length. $\endgroup$
    – user991
    Jul 3 '13 at 23:28
  • $\begingroup$ Only the ciphertexts must have equal length, correct? $\endgroup$
    – mikeazo
    Jul 3 '13 at 23:44
  • $\begingroup$ That would penalize ciphers for being somewhat length-hiding. $\:$ $\endgroup$
    – user991
    Jul 3 '13 at 23:52

What if it could? What does this definition mean in practice?

Consider $M_0=$ attack and $M_1=$ don't attack. If the adversary can distinguish which message you are sending to your troops, they can optimize their strategy to defeat you.

Another example. Say you are casting a yes ($1$) no ($0$) vote for a proposed piece of legislation. If the adversary can distinguish between yes and no votes, they might be able to throw the election (by discarding votes that don't go their way) or persecute you according to your vote.


That basically means 'an adversary running in a reasonable amount of time can (or cannot) distinguish one message from another once encrypted'. If we didn't care about that, there would be no point in using cryptography altogether. mikeazo gives a few good examples why this is important.

Furthermore here's the definition for the security of an encryption scheme as given in Introduction to Modern Cryptography p. 21:

an encryption scheme is secure if no adversary can compute any function of the plaintext from the ciphertext.

Not as good as HAC for a reference but good enough.

I know the question is about distinguishing two messages and my quote focuses on a single message but since the adversary compares $m_0$ to $m_1$ to reach some conclusion, I would argue that this is a function of at least one plaintext.


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.