Plausible Deniability in Fully Homomorphic Computation

Abstract

We introduce \emph{Plausible Deniability in Fully Homomorphic Computation} (PD-FHC), a framework enabling users to outsource Boolean computations to an untrusted cloud while maintaining both computational privacy against honest-but-curious providers and plausible deniability against coercive adversaries. We define the notion of a \emph{Deniable Computation Medium} (DCM) and a \emph{Deniable Computation Scheme} (DCS) as medium-independent abstractions, then instantiate them using RGB images with Fredkin-gate circuits. One real circuit and several decoys share a single fixed Fredkin-gate wiring. Embedded control bits decide what each gate computes at each pixel, so the same wiring evaluates the real function at the real positions and decoy functions elsewhere. The cloud applies this one wiring to every pixel identically, processing all circuits in a single pass. Under coercion, the user reveals a decoy with verifiable results while the real circuit stays hidden. We formalize multi-round coercion games with existence and circuit-discovery advantages. For the image instantiation, we prove \emph{information-theoretic position privacy} under a \emph{matched-marginal condition}: when the real, decoy, and fill bits are drawn from a common per-position law and placed at random, the embedded LSB plane is exchangeable, so an honest-but-curious provider gains no advantage over guessing at locating the real positions, for any such law and not only the uniform one. We are explicit that this is a condition Alice enforces, that it is distinct from steganalytic undetectability, and that the latter requires the embedded law to match the declared service's legitimate-input law.