Information-Theoretic Secrecy with Access to Decryption Oracles
Christopher Portmann, Keisuke Tanaka · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2011
We analyze the security notion of information-theoretic secrecy against an adversary who can make l adaptive queries to the decryption oracle, and show that it is equivalent to requiring that the encryption scheme can perfectly encrypt l+1 different messages. This immediately yields a lower bound on the key length and an optimal construction, namely (l+1)-wise independent permutations. This also gives an operational interpretation to the notion of decryption oracles in information-theoretic security.