Guessing Secrecy

Shannon’s definition of perfect secrecy captures the strongest notion of security for an encryption system and requires that the ciphertext leaks no information about the plaintext to an eavesdropper with unbounded computational power. The only known system with perfect secrecy in this model is one-time pad. Two important limitations of one-time pad in practice are, (i) the size of key space must not be less than the size of plaintext space, and (ii) the key must be chosen uniformly at random for each message to be encrypted. A number of follow up work attempt to relax these limitations by introducing relaxed or new definitions of secrecy.

In this paper we propose a new relaxation of secrecy that we call perfect guessing secrecy, or guessing secrecy for short. This is a natural definition that requires that the adversary’s success chance of the plaintext using his best guessing strategy does not change after seeing the ciphertext. Unlike perfect secrecy, guessing secrecy does allow some leakage of information but requires that the best guess of the plaintext remain the same after seeing the ciphertext. We define guessing secrecy and prove a number of results. We show that similar to perfect secrecy, in guessing secrecy the size of the key space can not be less than the size of plaintext space. Moreover, when the two sets are of equal size, one can find two families of distributions on the plaintext space and key space, such that perfect guessing secrecy is guaranteed for any pair of distributions, one from each family. In other words, perfect guessing secrecy can be guaranteed with non-uniform keys also. We also show the relation between perfect secrecy and perfect guessing secrecy. We discuss our results and propose direction of future research.