Paper 2026/667

The Information-Theoretic Limits of Hiding Among Decoys in the Shuffle Model

Abstract

Hiding a genuine message among plausible decoys is a recurring principle in cryptography and privacy, underlying honeywords, symmetric encryption, and anonymous data collection. We study the information-theoretic security of mechanisms that release a uniformly shuffled sequence containing one genuine message and $n-1$ decoys over a $d$-symbol alphabet. We characterize how restrictions on decoy generation determine achievable secrecy. We distinguish four classes of decoy mechanisms: i.i.d., heterogeneous independent, correlated message-oblivious, and message-dependent. For every fixed $d\ge2$, the optimal worst-case mutual information over message priors is $\Theta_d(n^{-1})$ for both independent classes and $\Theta_d(n^{-2})$ for correlated message-oblivious mechanisms. A discrete spectral construction achieves the latter rate without knowledge of the prior. Message-dependent mechanisms achieve perfect secrecy when $n\ge d$. Moreover, even with $n=3$, heterogeneous decoys can improve upon i.i.d.\ decoys by an arbitrarily large multiplicative factor. These results quantify the distinct benefits of heterogeneity, correlation, and dependence on the genuine message. A key-symmetrization reduction shows that every perfectly correct symmetric encryption scheme with a key drawn uniformly from a key space of size $n$ admits a message-dependent shuffle construction without increasing plaintext leakage. This connects optimal message secrecy to preimage-constrained channel design and yields an exact characterization of key leakage for all message-leakage-optimal ciphers when the number of keys does not exceed the plaintext support size. For canonical mechanisms, whose decoys are drawn i.i.d.\ from a blanket distribution $Q$ independently of the genuine message, a unified likelihood-ratio representation yields exact expressions for mutual information, total-variation information, message recovery advantage, and expected posterior variance, together with explicit finite-sample remainder bounds for the mutual-information expansion. For a fixed non-degenerate message prior $P$, the leading asymptotic coefficient of message mutual information is minimized by $Q^*(y)\propto\sqrt{P(y)(1-P(y))}$, which generally differs from $P$. For binary alphabets, quasi-uniform blankets exactly minimize message total-variation information for every $n\ge2$, independently of the prior.

Note: Relative to our earlier preprint version, this version adds a hierarchy of decoy-generation mechanisms and separation results, establishes connections to information-theoretically secure symmetric encryption, and develops a unified likelihood-ratio analysis with explicit finite-sample remainder bounds for the mutual-information expansions. The earlier preprint also analyzed the shuffle-DP model. The present paper focuses on shuffle-only mechanisms; we plan to present the shuffle-DP analysis in a separate manuscript.