Suppose we define privacy as a game where a machine $M$ has a coin $b$, and on input $M_0, M_1$ always replies with encrypted $M_0$ if $b=0$ and encrypted $M_1$ if $b=1$. The adversary can send as many pairs $M_0, M_1$ as he wants. The goal is to guess $b$. If he cannot do better than guessing at random (i.e., with probability $1/2$), then privacy holds (Simplified Benaloh's ballot privacy definition, if anyone is curious).

Out toy machine $M$, works as follows:

  • samples a random permutation $P$.
  • applies $P$ to the base mapping ["Yes" = $A$; "No" = $B$;"Maybe" = $C$].
  • replies with a new code corresponding to an answer.

Example: if $P = [2,3,1]$, then new map is: "Yes" = $C$, "No" = $A$ and "Maybe" = $B$ and $M$ will reply with $C$ for "Yes", $A$ for "No" and $B$ for "Maybe".

We know $M$ will use one of $3!=6$ possible permutations, which means that "Yes" in $2/3$ of cases will not be $A$. However, I cannot construct a distinguisher for the privacy game from this fact.

So, on the one hand, intuition says that toy machine $M$ leaks information - looking at the code, we can make a reasonable guess. However, I cannot formally prove it's not private under the simplified definition.

I don't know if it's the (simplified) definition's drawback, faulty intuition, or my poor understanding of conditional probabilities. Any ideas?

Edit: No leakage will be if we cannot distinguish between 'real usage' ($N$ different replies with (possibly) unequal prior-known probabilities of distribution among "Yes"/"No"/"Maybe") and 'ideal case' (where $M$ outputs $N$ codes $A$, $B$ or $C$ at random regardless any probability distribution among answers).

  • $\begingroup$ It's correct that Yes in 2/3 of the case will not be A. You can't conclude from this fact that the output leaks information about the input (argument: No in 2/3 of the case will not be A either). And the output does not leak information. That's why you cannot construct a distinguisher. You want to state your definition of "leaks information", and then verify that it does not hold. $\endgroup$
    – fgrieu
    Jan 18, 2023 at 16:43
  • $\begingroup$ @fgrieu, why don't you think it's a leakage? Say someone uses the machine $M$ to reply to "Do you support a cause X?". If I see "A", most likely the person is not a supporter. It's not 100%, but more than nothing, which counts as leakage, no? So, you say intuition is faulty, right? $\endgroup$
    – pintor
    Jan 18, 2023 at 16:54
  • $\begingroup$ In the case at hand, you can't conclude anything about what someone encoded from seeing "A" out of the machine $M$. That has probability 1/3 regardless of what someone encoded. To convince you of this, check that for any of the 3 encoded choices, 2 out of the 6 permutations lead to an output of A. Any contrary intuition is incorrect. Again, you want to state your definition of "leaks information", and then verify that it does not hold. $\endgroup$
    – fgrieu
    Jan 18, 2023 at 17:39
  • $\begingroup$ @fgrieu I added the leakage definition. As I understand, no leakage means codes are uniform (1/3 for each letter) even when answers' selections are not (say we know for a fact that "Yes" is selected at 75% of cases, "No" at 20%, and "Maybe" at 5%). $\endgroup$
    – pintor
    Jan 18, 2023 at 18:16
  • 1
    $\begingroup$ @fgrieu, I'm slowly getting your point. Still looking for possible scenarios to cause privacy problems, but so far, they all fail when I compute probabilities. Do you mind writing an answer before bots take over? Special kudos if you cite a formal definition of information leakage $\endgroup$
    – pintor
    Jan 19, 2023 at 15:06

2 Answers 2


No information can leak about the input of machine $M$ from the output of machine $M$, in any game. That's because $M$ can be viewed as a probabilistic Turing machine (with no memory of earlier runs), and for each fixed input of $M$ the distribution of the output is the same. It's easy to check the later by examination: there are three possible inputs, and for each there are six equaly likely permutations, of which two yield output A, two yield output B, two yield output C, so that each of these output has probability 1/3

Note: what matters is not that the output values have the same probability. What matters is that the probability of each output value for a given input is independent of the input.

Note: in the privacy game, the input of machine $M$ is restricted to two inputs A/Yes and B/No. Therefore, to prove that $M$ does not leak information in the privacy game, we only need to check that the distributions of the output of $M$ for each of these two inputs of $M$ are the same.

For a quantitative approach of information leakage, I think we could define it as the base-2 logarithm of the ratio of the probability of guessing input correctly knowing output of $M$, to the probability of guessing input correctly not knowing the output of $M$. That could be computed from the distribution of inputs in the experiment, and the conditional probabilities $P(o|i)$ of output $o$ given input $i$ for the machine under consideration. I wish I could tell exactly how, and hope it's in this.


I’m going to assume that when you say $M$ samples a random permutation, it does so uniformly so that each permutation is equally likely. If this is not the case, then there is information leakage.

One way to measure information leakage is to compute the mutual information of the input and output. If we write $p_y$, $p_n$ and $p_m$ for the probability of input “Yes”, “No” and “Maybe” respectively, we can easily see that $$\mathbb P(\mathrm{input}=\mathrm{“Yes”},\mathrm{output}=A)=p_y\times\frac13=\mathbb P(\mathrm{input}=\mathrm{“Yes”})\mathbb P(\mathrm{output}=A)$$ and similar independence in the other eight possible combinations. It follows that $$\log\left(\frac{\mathbb P(\mathrm{input}=\mathrm{“Yes”},\mathrm{output}=A)}{\mathbb P(\mathrm{input}=\mathrm{“Yes”})\mathbb P(\mathrm{output}=A)}\right)=0$$ and likewise for the other 8 logarithms in the expression for mutual information. Hence $$I(\mathrm{input},\mathrm{output})=0.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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