←

    Plausible Deniability Explained — Coin Toss Experiment

    Abin Varghese
    Coffee AI
    abin[at]coffeeai[dot]co
    January 21, 2022
    Abstract

    I want to show you how plausible deniability works through a simple coin toss experiment. Imagine asking people a sensitive question like 'Have you ever cheated on your taxes?' Most would lie or refuse to answer. But what if I could get honest answers while giving everyone plausible deniability? In this essay, I'll demonstrate how adding randomness through coin tosses preserves individual privacy while maintaining statistical utility. You'll see how we can learn population statistics without knowing anyone's true answer.

    Introduction

    I want to demonstrate what plausible deniability looks like and how it introduces randomness in datasets to preserve privacy. Differential privacy is built on this foundational concept.

    The Denial of Saint Peter
    Figure: The Denial of Saint Peter, about 1648, Mathieu Le Nain. Source: Wikimedia Commons

    Consider a scenario: I ask 10 people a private question which, when answered truthfully, may jeopardize their integrity and lifestyle. For example: "Have you ever cheated on your taxes?"

    People who have cheated have every reason to either not participate in the survey or simply lie. It's not difficult to guess that all participants' answers will be a resounding "no." But what if there were a way to learn about population statistics while preserving individual privacy?

    The Challenge

    Imagine 10 people, 40% of whom have actually cheated on their taxes. How can I obtain this 40% result (or approximately 30-50%, within ±10%) by introducing random noise while allowing each participant to deny the legitimacy of their answers?

    Initial Dataset
    Figure: Figure 1: Initial dataset showing 10 participants (A-J) with their true responses. A value of 1 indicates they have cheated on taxes, 0 indicates they have not. Four participants (B, C, G, H) have cheated, yielding 40%.

    Background: The Privacy Problem

    Transparent Data and Privacy Violation

    I have 10 people: A, B, C, D, E, F, G, H, I, and J. In the true response column, B, C, G, and H have cheated on their taxes (Figure 1). If you query this dataset to find what percentage of people have cheated, you learn the answer is 40%. You also know exactly who they are.

    This dataset fails to respect individual privacy because it's transparent with no noise added. The challenge: can I preserve privacy while maintaining statistical utility?

    The Randomized Response Mechanism

    I introduce a protocol using coin tosses:

    1. First coin toss: If heads, answer truthfully. If tails, proceed to step 2.
    2. Second coin toss: If heads, answer "yes." If tails, answer "no."

    This mechanism doesn't give participants a choice. It's where I add noise.

    Coin Toss Protocol
    Figure: Figure 2: The randomized response protocol. First coin toss: Heads → answer truthfully, Tails → proceed to second toss. Second coin toss: Heads → answer Yes, Tails → answer No.

    I expect some accuracy loss, but individual privacy will be preserved.

    The Experiment

    Participants A, B, and C

    First Three Participants
    Figure: Figure 3: Participants A, B, and C all get heads on their first coin toss, so they answer truthfully according to the protocol.

    For participant A, the first toss lands on heads. No need for a second toss—the response is the truth: 0 ("No," he didn't cheat). Repeating for B and C yields similar results. Both got heads the first time and answered truthfully.

    Participant D: First Deviation

    Participant D
    Figure: Figure 4: Participant D gets tails on the first coin toss, requiring a second toss. The second toss also lands on tails, so D must answer 0 (no) regardless of their true response.

    For D, the first toss lands on tails. Per the protocol, we proceed to a second toss, which also lands on tails. Person D must say 0 ("no") regardless of their true response.

    The Critical Case: Participant F

    Participant F
    Figure: Figure 5: Participant F's true answer is 0 (no), but the coin tosses force F to answer 1 (yes). This demonstrates plausible deniability—F can claim the yes was due to coin tosses, not truth.

    Focus on participant F. F's true answer is "no." However, due to the coin tosses, F had to answer "yes." This is crucial: F can now say, "Hey, I only said yes because it landed on tails and then on heads. In reality, I never cheated on taxes."

    This gives F—and each participant—plausible deniability regarding the legitimacy of their answer.

    Results and Analysis

    The Noisy Dataset

    Complete Results
    Figure: Figure 6: Complete responses after applying the randomized response mechanism. The query now returns 30% instead of the true 40%, representing a 10% accuracy loss due to added noise.

    These are the final responses. Running the same query to find the percentage of people who cheated on taxes now yields 30%. This represents a 10% loss in accuracy, attributed to the noise introduced by coin tosses. However, each individual participant's privacy is preserved.

    Data Destruction and Irreversibility

    Data Destruction
    Figure: Figure 7: The original dataset and coin toss results are destroyed, making reverse engineering impossible. Only the noisy responses remain for analysis.

    As a final step, I destroy the original dataset and coin toss results, making reverse engineering impossible. We destroy it by removing all columns except the final responses. This way, each participant's true response is destroyed, leaving only a noise-filled dataset suitable for data science and exploratory analysis.

    The Privacy Guarantee

    Final Dataset
    Figure: Figure 8: The final dataset contains only noisy responses. Each participant has plausible deniability, and no true response can be definitively determined.

    This is the beauty of differential privacy: each participant can say, "I said yes (or no) because I got tails first and then heads (or tails first and then tails again)."

    The person asking the question remains in the dark. They cannot know for sure if the participant is telling the truth or reporting coin toss outcomes.

    Discussion

    The Privacy-Utility Tradeoff

    This mechanism achieves a fundamental tradeoff in privacy-preserving data collection:

    Privacy Gains:

    • Each participant has plausible deniability
    • No individual response can be definitively attributed to its true value
    • Participants have no reason to refuse participation or lie
    • Reverse engineering is impossible after data destruction

    Utility Costs:

    • Approximately 10% accuracy loss in this example
    • Statistical noise increases with stronger privacy guarantees
    • Aggregate statistics remain useful for analysis

    Mathematical Foundation

    The randomized response mechanism provides formal privacy guarantees. Each participant's response follows a probability distribution:

    P(Response = Yes | Truth = Yes) = 0.75 (0.5 truthful + 0.25 random)

    P(Response = Yes | Truth = No) = 0.25 (random only)

    This creates uncertainty about any individual's true response while preserving statistical properties of the aggregate data.

    Practical Implications

    This simple coin toss experiment demonstrates principles underlying modern differential privacy systems:

    1. Randomization: Adding controlled noise protects individuals
    2. Plausible Deniability: Participants can deny their responses
    3. Statistical Utility: Aggregate patterns remain discoverable
    4. Irreversibility: Data destruction prevents retroactive privacy violations

    Conclusion

    I've demonstrated how plausible deniability enables privacy-preserving data collection. Through a simple coin toss experiment, I've shown how introducing randomness protects individual privacy while maintaining statistical utility.

    Each participant in this dataset can plausibly deny their response, claiming it resulted from random coin tosses rather than truth. I obtain population statistics while preserving individual privacy. This is a fundamental principle of differential privacy.

    This gives each participant a plausible deniability and NO reason to NOT participate in the survey.

    The 10% accuracy loss is a small price for guaranteeing that no participant's true response can be definitively determined. This mechanism shows that I can collect sensitive information truthfully without compromising individual privacy, enabling honest participation in surveys that would otherwise suffer from non-response or dishonest answers.

    As privacy concerns grow in our data-driven world, mechanisms like randomized response demonstrate that privacy and utility need not be mutually exclusive. I can learn about populations while protecting individuals. That's the essence of differential privacy.