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?

  • $\begingroup$ Your description of the one-time pad is off. There is no "inverse key". $\endgroup$ – Henno Brandsma Nov 13 '18 at 22:34
  • $\begingroup$ one-time pad over groups, OK, I didn't notice that, I was thinking of the standard Vernam xor-cipher. $\endgroup$ – Henno Brandsma Nov 13 '18 at 22:44
  • $\begingroup$ 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)$? $\endgroup$ – Henno Brandsma Nov 13 '18 at 22:47
  • $\begingroup$ @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 $\endgroup$ – Javier Nov 13 '18 at 22:50
  • $\begingroup$ A confusing notation. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.