💻 computer science

Plausible Deniability in Fully Homomorphic Computation

This paper introduces PD-FHC, a framework for plausible deniability in fully homomorphic computation that utilizes a single Fredkin-gate wiring on RGB images to simultaneously execute a real Boolean circuit and multiple decoys, thereby allowing users to outsource computations to untrusted clouds while maintaining information-theoretic position privacy and the ability to reveal a verifiable decoy under coercion.

Original authors: Shahzad Ahmad, Stefan Rass, Zahra Seyedi

Published 2026-07-13

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Shahzad Ahmad, Stefan Rass, Zahra Seyedi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a photo lab technician who needs to perform a secret, private calculation on a batch of images. Maybe you need to check if a specific measurement in a photo is higher than a certain limit. But there's a catch: you have to send these photos to a cloud computer you don't fully trust.

Usually, if you want to keep your data secret, you use Fully Homomorphic Encryption (FHE). Think of this as putting your photos in an unbreakable, glowing glass box. The cloud can still do math on the box, but it can't see inside. The problem? The glowing box is a dead giveaway. If a bossy, coercive adversary (like a government agent or a strict boss) demands to know what you're doing, they can point at the glowing box and say, "You're definitely doing secret math! Hand over the key!" You can't deny it because the box itself screams "Secret!"

This paper introduces a clever new trick called PD-FHC (Plausible Deniability in Fully Homomorphic Computation). Instead of a glowing box, imagine you are hiding your secret math inside a massive, ordinary-looking image filter.

The Magic Trick: One Wiring, Many Stories

Here is how the magic works, using a playful analogy:

Imagine you have a giant grid of 12,000 tiny light switches (these are the pixels in an image). You want to perform a secret calculation using a specific pattern of switches (your "real" circuit). But you also want to be able to tell a different story if someone forces you to explain what you did.

The authors use a special type of switch called a Fredkin gate. Think of a Fredkin gate as a magical traffic cop for three lanes of data. It has a control bit (a little flag) that decides what it does:

If the flag is down, it lets the cars pass straight through.
If the flag is up, it swaps the cars in the two side lanes.

Now, here is the genius part: The cloud provider only sees the traffic cop's instructions (the wiring), not the flags.

The Setup: You take your secret calculation and turn it into a specific pattern of flags. You also invent several "decoy" calculations (like checking image brightness or color balance) and turn those into different patterns of flags.
The Embedding: You hide the flags for your secret calculation in a few specific light switches. You hide the flags for your decoy calculations in other switches. For every single remaining switch in the image, you fill it with random noise.
The Cloud's Job: You send the image to the cloud. You tell them, "Please run this specific traffic cop pattern on every single switch in the image." The cloud doesn't know which switches hold your secret, which hold a decoy, and which are just random noise. They just apply the same rule to everyone, all at once.
The Result: Because the flags (control bits) are different for each group of switches, the traffic cop ends up doing your secret math on the secret switches, a decoy math on the decoy switches, and random noise math on the rest.

The "Plausible Deniability" Moment

Now, imagine the coercive adversary shows up. "What were you calculating?" they demand.

You can't say, "I did secret math," because that's the truth. But you can say, "Oh, I was just running a brightness check on these specific pixels!" You point to one of your decoy circuits.

The adversary checks the math. They see the flags you hid, they see the result, and they verify that the math works perfectly. They have no way of knowing that this was just a decoy. The "real" secret calculation is still hidden among the random noise and the other decoys, looking exactly like the rest of the image.

What This Paper Proves (and What It Doesn't)

The authors are very careful about what they claim to have solved and what is still a mystery.

What is Proven:

The "Position" Secret: If you fill your image with random noise that matches the statistical pattern of your secret data, the cloud provider cannot tell where your secret switches are. It's like trying to find a specific grain of sand on a beach when every grain looks exactly the same. The paper proves that under these specific conditions, the cloud's chance of guessing the right spot is no better than random guessing.
The "Existence" Secret: If you are forced to reveal some of your circuits, you can reveal the decoys. The paper proves that the adversary cannot prove that more circuits exist beyond the ones you revealed. It's like a magician showing you a few empty pockets; you can't prove there isn't a hidden pocket you didn't show them.

What is Ruled Out or Not Solved:

No "Invisible" Math: The paper explicitly states that this does not hide the fact that a computation is happening. The cloud knows a calculation is running because they are doing it. The magic is only in hiding which calculation it is and where the secret data is.
No "Magic" Obfuscation: The authors reject the idea of using complex cryptographic tricks to hide the structure of the circuit (the wiring). They admit that the wiring is visible to the cloud. The only thing hidden is the meaning of the gates, which comes from the hidden flags.
No "Perfect" Cover for Any Image: You cannot just take a random holiday photo and hide your secret in it. The paper argues that if the photo's natural "noise" doesn't match the random noise you add, a smart detector might spot the difference. You need to use a cover story that expects high randomness (like a dithering service or a noise-injection tool). If you try to hide your secret in a normal photo, you might get caught.

How Sure Are They?

The authors are very confident in their math but honest about the limits.

The Math: They have proven that if you follow their rules (matching the random noise perfectly), the cloud's advantage in finding your secret is exactly zero. This isn't a guess; it's a mathematical certainty based on the properties of the Fredkin gate.
The Real World: They ran simulations (computer tests) with images ranging from 128x128 pixels up to 512x512 pixels and circuits with 5 to 302 gates. These tests showed that the system works fast enough to be practical, competing with existing encryption tools.
The Weak Spot: The only thing they don't have a hard proof for is the "semantic" part. Can you always invent a decoy story that sounds believable? For example, if you claim you were checking "image brightness," does the math actually look like a brightness check? The paper admits this requires human creativity and domain knowledge. It's a "plausible" story, but the paper doesn't prove you can automate it perfectly.

The Bottom Line

This paper offers a way to outsource secret math to the cloud without leaving a glowing "I'm doing secrets!" sign. It turns your secret calculation into a needle in a haystack, where the haystack is filled with other needles that look exactly the same. If someone forces you to show a needle, you can show them a fake one that passes every test.

It's not a magic shield that makes the math invisible, and it doesn't work if you try to hide it in the wrong kind of picture. But for the right setup, it gives you a powerful new superpower: the ability to say, "I was just doing this boring thing," and have the math prove you right.

Technical Summary: Plausible Deniability in Fully Homomorphic Computation (PD-FHC)

1. Problem Statement

Outsourcing computation to untrusted cloud providers exposes users to two distinct threats that existing technologies fail to address simultaneously:

Computational Privacy: Protecting data from honest-but-curious providers (addressed by Fully Homomorphic Encryption (FHE) and Trusted Execution Environments (TEEs)).
Plausible Deniability: The ability to credibly deny the existence or intent of a computation when coerced by a powerful adversary.

Current solutions have critical gaps:

FHE: While it hides data values, the transmission of ciphertexts is conspicuous. A coercive adversary can demand decryption keys, and the mere use of FHE confirms that a private computation is occurring.
TEEs: These produce attestation logs that serve as undeniable proof of execution. Furthermore, they are vulnerable to side-channel leaks.
Secure Multi-Party Computation (MPC): While robust against the revelation of a single party's share, it does not allow participants to deny that the computation occurred or to substitute a different computation.
Deniable Encryption/Storage: These address static data (messages or files) but do not extend to dynamic computational intent.

The paper identifies a gap where a user needs to outsource a Boolean computation while maintaining the ability to deny what was computed and, to an external observer, that a computation occurred at all.

2. Methodology

The authors propose PD-FHC, a framework that embeds Boolean computations into a cover medium (specifically RGB images) using Fredkin gates and Least Significant Bit (LSB) steganography.

Core Mechanism:

Shared Wiring, Variable Semantics: The framework utilizes a single, fixed wiring of universal Fredkin gates. A Fredkin gate is a reversible 3-input/3-output gate where a control bit determines whether the two data bits are swapped.
- If the control bit is 0, the gate acts as a pass-through.
- If the control bit is 1, the gate swaps the data bits.
- By setting the control bits via embedded data, the same physical wiring can implement different logical functions (e.g., AND, OR, NOT, or complex circuits) at different locations.
Multi-Location Embedding: The user (Alice) embeds one "real" circuit and $L-1$ $L - 1$ "decoy" circuits into the LSBs of an image.
- Real Circuit: Embedded at a secret set of positions $\Lambda_{j^*}$ .
- Decoy Circuits: Embedded at other disjoint position sets $\Lambda_j$ .
- Fill Bits: All remaining LSB positions are filled with bits drawn from a specific distribution $\pi$ .
Uniform Processing: The cloud provider (Carol) receives the image and the wiring specification ( $C_{obf}$ ). She applies the Fredkin gate uniformly to every pixel position in parallel. She does not know which positions contain real data, decoy data, or fill noise.
Coercion Response: If coerced, Alice reveals the position sets, inputs, and outputs for a decoy circuit. Because the wiring is identical and the decoy circuit produces verifiable results consistent with the cloud's output, the adversary cannot distinguish the decoy from the real computation.

Theoretical Foundations:

Deniable Computation Medium (DCM): An abstract framework defining a medium with addressable bit-positions, read/write capabilities, and a gate family that applies uniformly.
Matched-Marginal Condition: For information-theoretic security, the bits at real positions, decoy positions, and fill positions must be drawn from the same per-position probability law $\pi$ . Under this condition, the LSB plane is "exchangeable," meaning the statistical distribution of the image is invariant to the permutation of positions.

3. Key Contributions

Abstract Framework: Definition of a Deniable Computation Medium (DCM) and a Deniable Computation Scheme (DCS) that separate the security model from specific cover media (e.g., images, audio, packets).
Threat Model Formalization: A two-phase model distinguishing between:
- Honest-but-Curious (HBC) Cloud: Concerned with computational privacy (hiding the data).
- Coercive Adversary: Concerned with plausible deniability (hiding the existence and intent of the computation).
- The authors define novel multi-round coercion games measuring "existence distinguishing" (can the adversary prove hidden circuits exist?) and "circuit discovery" (can the adversary identify the real circuit among revealed decoys?).
Image-Based Instantiation: A concrete implementation using RGB images and Fredkin gates.
- Proof of Position Privacy: Under the matched-marginal condition, the paper proves that the cloud provider gains zero advantage (information-theoretically) in locating the real circuit positions compared to random guessing, regardless of the distribution $\pi$ .
- Partial Circuit Hiding: The wiring is visible, but the gate semantics are hidden. The paper proves that without knowledge of the control bits, the wiring reveals nothing about which function is being computed.
Implementation and Benchmarking: A Python implementation benchmarked across circuit sizes (5–302 gates) and image dimensions ( $128^2$ to $512^2$ ).

4. Results

Security Guarantees:
- Computational Privacy: The cloud learns nothing about the secret data values or the specific function computed, provided the gate family preserves the statistical distribution of non-secret positions (a property Fredkin gates satisfy via bit-permutation).
- Existence Hiding: Under the matched-marginal condition, the existence advantage is exactly zero. An adversary cannot distinguish between an image containing only fill bits and one containing hidden circuits.
- Circuit Discovery: The advantage of identifying the real circuit among unrevealed decoys is bounded by the semantic plausibility of the decoys and side-channel leakage. The position and wiring vectors contribute zero to the adversary's advantage.
Performance: The implementation shows competitive performance with TFHE (a leading FHE library) for Boolean circuits while providing deniability that FHE cannot offer.
Visual Imperceptibility: The modification of LSBs results in a maximum $\pm 1$ shift per channel, yielding PSNR > 50 dB, making changes visually imperceptible.

5. Significance and Claims

The paper claims to be the first framework to simultaneously satisfy computational privacy, existence hiding (against external observers), and partial circuit hiding (against the cloud provider).

Modest Claims and Limitations:

Scope of Cover Plausibility: The authors explicitly state that PD-FHC does not work for arbitrary images (e.g., holiday snapshots). The cover service must legitimately expect high-entropy LSB inputs (e.g., dithering, noise injection, or encrypted-domain processing). If the declared service expects natural images, the uniform LSB plane required for security becomes detectable.
Real Input Constraints: The information-theoretic zero-advantage guarantee holds exactly only if the user's real input bits also follow the same distribution $\pi$ as the decoy and fill bits. For structured real inputs, the advantage is bounded by the statistical distance ( $\Delta$ ) between the real input distribution and $\pi$ .
Semantic Plausibility: The security against circuit discovery relies on the $\epsilon$ -plausibility of decoy circuits. The paper admits that constructing semantically believable decoys (e.g., a brightness check vs. a cryptographic hash) is a manual, domain-specific task and not yet automated.
Active Attacks: The framework assumes an honest-but-curious cloud and passive external observers. It does not protect against active attackers who might modify the image or refuse to compute.
No Cryptographic Obfuscation: The paper explicitly avoids claiming cryptographic circuit obfuscation (which is subject to impossibility results). The "obfuscation" is purely steganographic, relying on the hidden control bits to vary gate semantics.

In summary, PD-FHC offers a novel approach to outsourcing computation where the user can credibly deny the specific intent of the computation by presenting a verifiable, alternative function that is indistinguishable from the real one under coercion, provided the statistical conditions of the cover medium are met.