Semantic Security Game

Question

I need help understanding semantic security, in particular, the part on the 'game'.

But first, from my understanding, is semantic security is a 'weaker' and more flexible way to determine that a cryptographic function is secure enough for use? I understand that the definition for perfect secrecy is often too rigid and hence semantic security gives some leeway in defining something that's secure enough. And the official definition is: An encryption scheme is semantically secure, if an adversary cannot guess with better probability than 1/2 whether the given ciphertext is an encryption of message m0 or m1.

There is a popular explanation using a 'game' the challenger and adversary plays, however, I am a little confused with how it works.

Can someone help me understand the 'game' and how it is used to determine whether something is semantically secure? How does

The game:

1. The challenger picks a random key k

2. The adversary first sends 2 messages, m1 and m0 to the challenger

3. The challenger either outputs the encryption of m1 or m0.

4. The adversary is trying to guess whether he was given the encryption of m0 or m1

for b = 0,1 Wb: = [event that exp(b) = 1]

Advss[A,E]: = |Pr[W0] - Pr[W1] | element of [0,1]

A simple definition I saw to summarise the above is "An adversary sends two plaintext messages of equal length to the challenger and receives one encrypted message; semantic security means an adversary can’t distinguish which plaintext message was encrypted."

Question 1: In step 3, it says that in Experiment 1, the challenger will output the ciphertext of m1, and in Experiment 0, the ciphertext of m0. Correct me if im wrong, but the challenger will only send ONE message, either the ciphertext of m1 or m0 right, and not both?

Question 2: I don't get the part where the game is trying to see if the adversary can distinguish which plaintext message was encrypted. How would the adversary be able to do that, with only one ciphertext being revealed by the challenger? Because there is always a 1/2 ambiguity. And when are cases where it would successfully and unsuccessfully distinguish the two?

Answer 1

1. Correct, the challenger sends either $E_k(m_0)$ or $E_k(m_1)$, not both.

2. If the cipher is not semantically secure, the attacker will have better than 1/2 probability of guessing the which plaintext is which.

For example, take the $ROT_K$ cipher, where the alphabet is the upper-case English alphabet and K is the rotation amount, which is a key. Every letter always encrypts to the same output, so eg for $K=13$, $E_K(“A")=“N"$ The attacker can submit a two chosen plaintexts, say $m_0=“AAAAAAAA"$ and $m_1=“ABCDEFGH"$. If the returned message comes back with 8 of the same letter in a row, it must be an encryption of $m_0$, if it's 8 sequential letters it must be an encryption of $m_1$, so the attacker can beat the game with probability 1. Other ciphers might not be this trivial, but they'll still have a success probability > 1/2.