Join Log in
Score:0
Jack avatar Crypto

Semantic Security Game

cn flag
Jack

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?

202
1 + 0
Score:1
SAI Peregrinus avatar Crypto
si flag
SAI Peregrinus

  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.

0 + 2
Jack avatar
cn flag
Jack
Thank you so much! This explains everything perfectly. So basically, unless the encryption scheme is weak, the attacker only has 1/2 probability of success. But if it is using a weaker scheme, e.g. the one outlined in your answer, then the attacker has some way to find some info, and their probability of success is > 1/2 and that makes it not semantically secure right?
0
Reply
SAI Peregrinus avatar
si flag
SAI Peregrinus
Exactly. Note also that there are stronger security notions than semantic security (IND-CPA), the most commonly used being AE-security (IND-CCA3). These schemes give the attacker more power, so they can get more information.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.