Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm taking coursera cryptography course. The definition of semantic security is hard to understand. I tried to slightly restate it (the word "efficient" was in the original definition). Do I get 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 adversary decides $m_b$ is ciphered. And events are: $M_b = \{ \ \text{$exp(b) = 1$} \ \}$. I don't get this part of definition.

share|improve this question
Is the whole portion in the blockquote your modified definition? If so, what did the original definition say. – mikeazo Jul 3 '13 at 19:24
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. – koddo Jul 3 '13 at 22:02
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. – Ricky Demer Jul 3 '13 at 23:28
Only the ciphertexts must have equal length, correct? – mikeazo Jul 3 '13 at 23:44
That would penalize ciphers for being somewhat length-hiding. $\:$ – Ricky Demer 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.

share|improve this answer

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.

share|improve this answer

Your Answer


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.