Cryptogenography

Alex Crane, Joshua Brody

Imagine a subversive protest organization living under an oppressive regime that monitors all internet activity. This organization's leader might want to communicate a protest location to members via the internet. If he simply pub- lishes that information, the government will arrest him. Is it possible for the leader to tell his followers protest times and locations without revealing who he is? This is where Cryptogenography comes in. We study the ability of the leader to accurately disseminate information without revealing his identity to the government. Note that in this model the leader does not care if the govern- ment learns the location of the protest. In that way cryptogenography differs from cryptography. We seek to hide the source of information, rather than the information itself.

We studied a toy case using only two players, Alice and Bob. One of Alice and Bob holds a secret bit, 0 or 1. Both the secret holder and secret value are random with a uniform distribution. Alice and Bob communicate one bit at a time, and all of their communications are overheard by an eavesdropper, Eve. The players win if they correctly share the secret and Eve guesses the secret holder incorrectly. We are interested in the probability with which Alice and Bob can win.

Doerr and Künnemann [1] developed an algorithm called automated search, which generates good protocols for Alice and Bob's speech by searching through a finite subset of our probability space:

{(a0,a1,b0,b1):a0+a1+b0+b1=1 and a0,a1,b0,b1≥0}{(a0,a1,b0,b1):a0+a1+b0+b1=1 and a0,a1,b0,b1≥0}

Beginning in a directed reading in the spring of 2016 (with Shantanu Jain, Sophia O'Malley-Krohn, Tahmid Rahman, and Ryan Shi) we reimplemented automated search and made several improvements.

Concave functions on the space described above give upper bounds on Alice and Bob's abilities as long as they meet certain other, simple, requirements. Brody et al. [2] established an upper bound of 3/8 by providing such a function. Doerr and Künnemann subtracted a term from this function without violating the necessary restrictions, lowering the upper bound to 0.3672. We lowered the upper bound to 0.3619 by the same process.

Literature Cited:

[1] Benjamin Doerr and Marvin Künnemann. Improved protocols and hard- ness results for the two-player cryptogenography problem. arXiv preprint arXiv:1603.06113, 2016.

[2] Joshua Brody, Sune K Jakobsen, Dominik Scheder, and Peter Winkler. Cryptogenography. In Proceedings of the 5th conference on Innovations in the- oretical computer science, pages 13-22. ACM, 2014.