Cryptogenography
Document Type
Conference Proceeding
Publication Date
2014
Published In
Proceedings Of The 5th Conference On Innovations In Theoretical Computer Science
Abstract
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.
Published By
ACM
Conference
5th Innovations In Theoretical Computer Science Conference
Conference Dates
January 12-14, 2014
Conference Location
Princeton, NJ
Recommended Citation
Joshua Brody, S. K. Jakobsen, D. Scheder, and P. Winkler.
(2014).
"Cryptogenography".
Proceedings Of The 5th Conference On Innovations In Theoretical Computer Science.
13-22.
DOI: 10.1145/2554797.2554800
https://works.swarthmore.edu/fac-comp-sci/96