Maximal Correlation Secrecy
This work addresses the challenge of designing efficient cryptosystems with short keys for secure communication, offering a stronger and more practical secrecy measure than existing approaches.
The paper tackles the problem of ensuring secrecy in cryptosystems with short keys by showing that maximal correlation between message and ciphertext provides strong secrecy guarantees, achieving key lengths of approximately 2 log(1/ρ) independent of message length and proving these ciphers are near-optimal.
This paper shows that the Hirschfeld-Gebelein-Rényi maximal correlation between the message and the ciphertext provides good secrecy guarantees for cryptosystems that use short keys. We first establish a bound on the eavesdropper's advantage in guessing functions of the message in terms of maximal correlation and the Rényi entropy of the message. This result implies that maximal correlation is stronger than the notion of entropic security introduced by Russell and Wang. We then show that a small maximal correlation $ρ$ can be achieved via a randomly generated cipher with key length $\approx2\log(1/ρ)$, independent of the message length, and by a stream cipher with key length $2\log(1/ρ)+\log n+2$ for a message of length $n$. We establish a converse showing that these ciphers are close to optimal. This is in contrast to entropic security for which there is a gap between the lower and upper bounds. Finally, we show that a small maximal correlation implies secrecy with respect to several mutual information based criteria but is not necessarily implied by them. Hence, maximal correlation is a stronger and more practically relevant measure of secrecy than mutual information.