Paper 2026/1899

Key-Space Complexity of Information-Theoretic Target-Distribution Semantic Security

Abstract

We study the uniform key-space complexity of information-theoretic target-distribution semantic security (TDSS) for symmetric encryption. Given a message distribution \(P\), we ask for the minimum size of a uniform key space such that observing the ciphertext improves the optimal prediction probability of any Boolean predicate of the message by at most \(\varepsilon\). Our main construction is a sample-based encryption scheme with \(\kappa\) keys: for a secret key $k\in[\kappa]$, the message is placed in the $k$-th position, and each of the remaining $\kappa-1$ positions is filled with an independent sample from a dummy distribution $P_{D}$. When \(P_D=P\), the posterior distribution of the message conditional on the ciphertext is exactly the empirical distribution of \(\kappa\) independent samples from \(P\). This gives a universal semantic-security bound of \(1/(2\sqrt \kappa)\), so \(\kappa=O(\varepsilon^{-2})\) keys suffice for every message distribution, independently of the message-space size. We prove a complementary lower bound in terms of \(\|P\|_2\), matching this rate up to constants for sufficiently flat distributions. In particular, for the uniform distribution on \(|\mathcal{M}|\) messages, the optimal key-space size is $\Theta\!\left(\min\{|\mathcal{M}|,\varepsilon^{-2}\}\right).$ The same framework recovers and generalizes the classical key-length scaling of entropic security: taking \(P_D\) uniform on \(\{0,1\}^n\), a mixture-and-cloning argument protects every source of min-entropy at least \(h\) using $n-h+2\log(1/\varepsilon)+O(1)$ secret-key bits. It also yields a broader source-family view of information-theoretic semantic security, showing that short-key TDSS is possible for any family of sources with bounded second-order R\'enyi divergence from a common reference distribution. We further study zero-advantage TDSS (i.e., $\varepsilon=0$) for restricted predicate classes \(\mathcal F\). We show that a perfectly correct cipher achieving zero-advantage TDSS for $\mathcal F$ with a uniform $\kappa$-element key space exists if and only if $P$ admits a decomposition into $\kappa$-sparse posteriors that preserve the prior Bayes-optimal prediction for every $f\in\mathcal F$. This sparse-convex characterization implies that \(|\mathcal F|+1\) keys always suffice. Surprisingly, point, threshold, and interval predicates can all be protected exactly with only two keys for every message distribution. Our results connect information-theoretic encryption with sparse convex decompositions and the shuffle model, and provide a systematic view of zero-advantage and approximate TDSS with short secret keys.