Proof one-time pad is perfectly secret with eavesdropping game definition

Question

I have the following definition of perfect secrecy (please assume that the probabilistic version is not available):

If we consider the eavesdropping game given by:

$$\begin{array}{|r | r|} \hline Alice & Eve \\ \hline & (m_0,m_1) = E.m()\\ k \leftarrow Gen() & \ \\ b \leftarrow fair\_coin() & \\ c \leftarrow Enc_k (m_b) & \\ & r = E.r(c)\\ \hline \end{array}$$

one says that a symmetric encription system is perfectly secret if there is no attack $E$ which wins the game with probability strictly greater than $1/2$, where winning the game means that at the end of the process $b = r$.

With this definition I have to prove that the $(G,l)$-one time pad (that is one-time pad over groups) given by $Enc_k(m) = m \circ k$ and $Dec_k(c) = c \circ k^{-1}$ is perfectly secret. Here one defines for $m = (m_1,\ldots,m_l)$ and $k = (k_1,\ldots,k_l)$, $m \circ k = (m_1 \circ k_1,\ldots,m_l \circ k_l)$ and $k^{-1} = (k_1^{-1},\ldots,k_l^{-1})$.

My approach

$k$ is uniformly distributed by assumption and since $m_b$ should be independent of $k$ then $m_b \circ k$ is uniformly distributed. But no attack can distinguish in a uniformly distributed sequence with probability greater than 2.

Is my approach correct?

Answer 1

Might be too late.. but yes the approach is correct. As you said, since the one time pad is being used, Eve doesn't really need $c$(not even choosing the two messages) she could just use some simulator $\sigma$ and generate a random uniform $c' = \sigma((G, l))$ and run $r = E.r(c')$. So the distribution of $(m_0, m_1)$ doesn't matter, r and b are independent. Thus equal with probability at most $1/2$

Now, I'll try to answer this more "formally".

Notation: Let $(S, B)$ denote the system that emulates Alice, meaning a systems $S$ correlated with a uniformly distributed bit $B$. $S$ performs the $otp-enc(m_B)$. Let $S_0$ be Alice when the bit is zero(i.e sends $otp-enc(m_0)$, $S_1$ is defined similarly. Let $D$ be a distinguisher(Eve) characterized by a joint distribution $P^{M_0,M_1}[m_0, m_1]$ over the set of possible messages, and an algorithm $R: (G,l) \to \{0,1\}$. $R$ takes a cipher text and outputs a bit.

The setup: Eve is trying to win the bit guessing game wherein a distinguisher $D$ interacts with $(S, B)$ and outputs a bit $R$. The advantage of Eve is $\Delta^D((S, B)) = 2Pr^{D(S, B)}[R = B] - 1$. In other words by how much she performs better than when she just guess.

Now observe that what the question asks is to show that the advantage is 0 for any Eve.

Another type of game Eve could play is a distinction game where Eve is connected and interacts with either $S_0$ or $S_1$ and outputs a bit $R = 0$ if she thinks she is interacting with $S_0$ and outputs 1 otherwise. The advantage of Eve in this game is $\Delta^D(S_0, S_1) = Pr^{DS_1}[R = 1] - Pr^{DS_0}[R = 1]$. I introduce the following result without proof:

$\Delta^D((S, B)) = \Delta^D(S_0, S_1)$., for a uniform $B$.

So we can instead find the advantage of the distinguishing problem, which seems easier. We have that $Pr^{DS_1}[R = 1] = Pr^{KM_0}[m_0 \oplus k = c] = \frac{1}{|G|^l}$. This is the same for $Pr^{DS_1}[R = 0]$. So $\Delta^D(S_0, S_1) = 0$.

Therefore $\Delta^D((S, B)) = 0$, which is what we wanted to show.

Remark: if Eve were to be allowed to additionally ask for encryption of up to $t$ messages, that would somehow be a proof of information theoretic ind-cpa security of the OTP. Although some could argue that this notion doesn't really fit with the OTP.