Summary: We revisit the question, originally posed by A.C.-C. Yao [Theory and applications of trapdoor functions (Extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, FOCS 1982, Chicago, Illinois, USA, 1982, 80–91 (1982)], of whether encryption security may be characterized using computational information. Yao provided an affirmative answer, using a compression-based notion of computational information to give a characterization equivalent to the standard computational notion of semantic security. We give two other equivalent characterizations. The first uses a computational formulation of Kelly’s (1957) model for “gambling with inside information” [J. L. Kelly jun., A new interpretation of information rate. Bell. Syst. Tech. J. 35, 917–926 (1956)], leading to an encryption notion which is similar to Yao’s but where encrypted data is used by an adversary to place bets maximizing the rate of growth of total wealth over a sequence of independent, identically distributed events. The difficulty of this gambling task is closely related to Vadhan and Zheng’s (2011) notion of KL-hardness [S. Vadhan and C. J. Zheng, Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012, New York, NY: ACM, 817–836 (2012; Zbl 1286.65008), Electronic Colloquium on Computational Complexity (ECCC) 18, 141 (2011)], which in certain cases is equivalent to a conditional form of the pseudoentropy introduced by J. Håstad et. al. [SIAM J. Comput. 28, No. 4, 1364–1396 (1999; Zbl 0940.68048)]. Using techniques introduced to prove this equivalence, we are also able to give a characterization of encryption security in terms of conditional pseudoentropy. Finally, we will reconsider the gambling model with respect to “risk-neutral” adversaries in an attempt to understand whether assumptions about the rationality of adversaries may impact the level of security achieved by an encryption scheme.
For the entire collection see [Zbl 1321.94009].