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

We study the achievable level of information-theoretic security for symmetric encryption under low-entropy keys (e.g., passwords and biometrics), where classical notions such as perfect secrecy and entropic security are usually unattainable. We consider a model in which messages $M$ and keys $K$ are drawn independently from distributions $(p_m,p_k)$. Prior work on homophonic ciphers (HC) and honey encryption (HE) suggests that randomized encryption tailored to $p_m$ can improve security. We ask what the optimal achievable level is among all symmetric encryption schemes, and which necessary and/or sufficient conditions on encryption schemes characterize when this level can be achieved.

For key confidentiality (KC), we show that the optimal achievable level is $I(K;C)=\operatorname{negl}(\ell)$, i.e., the ciphertext reveals only negligible information about the key. Moreover, this holds if and only if, informally, decrypting under any key induces sampling of messages according to $p_m$. HC and HE following this principle achieve this level, whereas $p_m$-agnostic schemes (except for trivial schemes) do not in general. For message confidentiality (MC) against message-recovery attacks, we show that the optimal bound on the adversary’s success probability is $p_{\max}+\operatorname{negl}(\ell)$, where $p_{\max}$ is the baseline success probability of guessing the most likely message or key under $(p_m,p_k)$. We construct a scheme OE tailored to $(p_m,p_k)$ that attains $p_{\max}+O(2^{-\ell})$, and prove that $p_k$-agnostic schemes (including HC and HE) cannot in general achieve this bound. Our results on necessary and/or sufficient conditions characterize fundamental principles governing the use of randomness in probabilistic encryption.

The main technical challenge is to handle a discretization-induced negligible error that must be propagated throughout the derivation of our bounds and necessary and/or sufficient conditions. To facilitate the analysis, we introduce a continuous-ciphertext framework that separates structural constraints from discretization error.