How to fool an unbounded adversary with a short key
The symmetric encryption problem which manifests itself when two parties must securely transmit a message m with a short shared secret key is considered in conjunction with a computationally unbounded adversary. As the adversary is unbounded, any encryption scheme must leak information about m; in particular, the mutual information between m and its ciphertext cannot be zero. Despite this, a family of encryption schemes is presented that guarantee that for any message space in {0,1}n with minimum entropy n lscr and for any Boolean function h:{0,1}n rarr {0,1} no adversary can predict h(m) from the ciphertext of m with more than 1/nomega(1) advantage; this is achieved with keys of length lscr+omega(logn) In general, keys of length lscr+s yield a bound of 2 Theta(s) on the advantage. These encryption schemes rely on no unproven assumptions and can be implemented efficiently. Applications of this to cryptosystems based on complexity theoretic assumptions are discussed and, in addition, a simplified proof of a fundamental "elision lemma" of Goldwasser and Micali is provided
IEEE Trans. Inf. Theory