Cryptogenography
Joshua Brody, Sune K. Jakobsen, Dominik Scheder, Peter M. Winkler · 2014
We consider the following cryptographic secret leaking problem. A group of players communicate with the goal of learning (and perhaps revealing) a secret held initially by one of them. Their conversation is monitored by a computationally unlimited eavesdropper, who wants to learn the identity of the secret-holder. Despite the unavailability of key, some protection can be provided to the identity of the secret-holder. We call the study of such communication problems, either from the group's or the eavesdropper's point of view, cryptogenography. We introduce a basic cryptogenography problem and show that two players can force the eavesdropper to missguess the origin of a secret bit with probability 1/3; we complement this with a hardness result showing that they cannot do better than than 3/8. We prove that larger numbers of players can do better than 0.5644, but no group of any size can achieve 0.75.