How to Fool an Unbounded Adversary with a Short Key

摘要

We consider the symmetric encryption problem which manifests when two parties must securely transmit a message m with a short shared secret key. As we permit arbitrarily powerful adversaries, any encryption scheme must leak information about m - the mutual information between m and its ciphertext cannot be zero. Despite this, we present a family of encryption schemes which guarantee that for any message space in {0,1}~n with minimum entropy n - l and for any Boolean function h : {0, l}~n → {0,1}, no adversary can predict h(m) from the ciphertext of m with more than 1~(w(1) advantage; this is achieved with keys of length l+w( log n). In general, keys of length l+s yield a bound of 2~(-θ(s)) on the advantage. These encryption schemes rely on no unproven assumptions and can be implemented efficiently.