Proceedings Of The 5th Conference On Innovations In Theoretical Computer Science
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.
5th Innovations In Theoretical Computer Science Conference
January 12-14, 2014
Joshua Brody, S. K. Jakobsen, D. Scheder, and P. Winkler.
Proceedings Of The 5th Conference On Innovations In Theoretical Computer Science.