Paper 2026/646

On Optimal Information-Theoretic Security in Symmetric Encryption under Low-Entropy Keys

Abstract

Low-entropy keys such as passwords and biometrics are pervasive, yet classical information-theoretic guarantees, such as perfect secrecy and entropic security, cannot generally be achieved in this regime. Honey encryption (HE) and homophonic ciphers (HC) tailor encryption to the message distribution to provide meaningful security, but their analyses do not establish optimal guarantees for arbitrary distributions. We ask: for messages and keys drawn independently from arbitrary distributions $(p_{\mathrm m},p_{\mathrm k})$, what is the optimal information-theoretic security achievable by any symmetric encryption scheme, and which conditions characterize its attainment? For key confidentiality (KC), the optimal guarantee is that the ciphertext $C$ reveals only negligible information about the key $K$, i.e., $I(K;C)=\operatorname{negl}(\ell)$. For uniform schemes, this is achieved if and only if decrypting under every fixed key yields a distribution statistically close to $p_{\mathrm m}$. HC and HE achieve this guarantee. For message-recovery security (MRS), the optimal guarantee is that no adversary guesses the message with probability above $p_{\max}+\operatorname{negl}(\ell)$, while a trivial adversary achieves at least $p_{\max}$ by guessing the most likely message or decrypting under the most likely key. We construct MRS-OE, a uniform scheme tailored to $(p_{\mathrm m},p_{\mathrm k})$ that attains $p_{\max}+O(2^{-\ell})$, and prove that $p_{\mathrm k}$-agnostic schemes, including HC and HE, cannot achieve optimal MRS in general. We also show that optimal KC and optimal MRS generally cannot be achieved simultaneously. Technically, we establish the KC characterization through flow and cut analysis on a weighted directed acyclic graph. We also introduce a continuous-ciphertext framework that separates structural constraints from discretization error.