Paper 2026/424

CRISP: Channel-Randomised Single-Image Steganography with Permutations

Abstract

We introduce CRISP (\underline{C}hannel-\underline{R}andomised Single-\underline{I}mage\\ \underline{S}teganography with \underline{P}ermutations), a homomorphic steganography scheme for outsourced computation. In the setting we consider, a client (Alice) hides Boolean inputs in the least-significant bits of cover images and asks an honest-but-curious cloud (Carol) to evaluate a logic circuit, gate by gate, directly on those images so that a receiver (Bob) can later extract the result. The setting is natural for outsourcing but non-standard for steganography: Carol knows that steganographic embedding is used, knows the scheme, and knows the public channel-assignment permutations; the only secret is the per-execution pixel position $(\mathit{row}, \mathit{col})$ in the image at which the bits live. The security goal is therefore positional hiding under known presence, not Cachin-style undetectability. CRISP embeds all three inputs of a Fredkin gate (a universal reversible three-bit logic gate) into the three RGB channels of a single cover image at a secret pixel position, and writes all three outputs into a single output cover at the same position. Two independently sampled permutations $(\pi_{\mathrm{in}}, \pi_{\mathrm{out}}) \in S_3 \times S_3$ assign channels to logical roles at the input and output of each gate, and both travel with the public circuit specification. Two results about the limits of this design follow, and we regard them as the more useful contribution. First, per-gate resampling of $\pi_{\mathrm{out}}$ does not give circuit privacy. We prove that a server holding the circuit specification reads the channel-to-role map at every gate directly, and that a weaker adversary holding only the images recovers the same map and the wiring graph with nine channel-pair comparisons per gate. Second, a $1/(h{\times}w)$ positional bound proved on a single image does not survive a full multi-image transcript when ancillary wires carry publicly known constants. We restate the security game over the whole transcript and prove a bound $2^{\lambda}/(2^{\lambda}+n-1)$ with $n = h{\times}w$ and $\lambda$ the gap between the number of secret input bits and the collision entropy of the server's prior on them. Constants embedded only at the secret pixel push $\lambda$ up by one bit each, and enough of them pin the pixel down exactly. Two cheap repairs drive $\lambda$ back to zero and restore the exact $1/(h{\times}w)$ bound. The decay is polynomial, not super-polynomial, so the bound is statistically small but not cryptographically negligible in the standard sense.