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

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?

• Your description of the one-time pad is off. There is no "inverse key". – Henno Brandsma Nov 13 '18 at 22:34
• one-time pad over groups, OK, I didn't notice that, I was thinking of the standard Vernam xor-cipher. – Henno Brandsma Nov 13 '18 at 22:44
• You have to add the demand that $m_0$ and $m_1$ have the same length, and what does the last line of the game mean? $r= E.r(c)$? – Henno Brandsma Nov 13 '18 at 22:47
• @HennoBrandsma it means that E has an algorithm r that given a ciphertext c computes one number also called r, which is written on the left – Javier Nov 13 '18 at 22:50
• A confusing notation. – Henno Brandsma Nov 13 '18 at 22:51

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.