Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem

Authors Benjamin Doerr, Marvin Künnemann



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.150.pdf
  • Filesize: 0.56 MB
  • 13 pages

Document Identifiers

Author Details

Benjamin Doerr
Marvin Künnemann

Cite AsGet BibTex

Benjamin Doerr and Marvin Künnemann. Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 150:1-150:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.150

Abstract

The cryptogenography problem, introduced by Brody, Jakobsen, Scheder, and Winkler (ITCS 2014), is to collaboratively leak a piece of information known to only one member of a group (i) without revealing who was the origin of this information and (ii) without any private communication, neither during the process nor before. Despite several deep structural results, even the smallest case of leaking one bit of information present at one of two players is not well understood. Brody et al. gave a 2-round protocol enabling the two players to succeed with probability 1/3 and showed the hardness result that no protocol can give a success probability of more than 3/8. In this work, we show that neither bound is tight. Our new hardness result, obtained by a different application of the concavity method used also in the previous work, states that a success probability of better than 0.3672 is not possible. Using both theoretical and numerical approaches, we improve the lower bound to 0.3384, that is, give a protocol leading to this success probability. To ease the design of new protocols, we prove an equivalent formulation of the cryptogenography problem as solitaire vector splitting game. Via an automated game tree search, we find good strategies for this game. We then translate the splits that occurred in this strategy into inequalities relating position values and use an LP solver to find an optimal solution for these inequalities. This gives slightly better game values, but more importantly, also a more compact representation of the protocol and a way to easily verify the claimed quality of the protocol. Unfortunately, already the smallest protocol we found that beats the previous 1/3 success probability takes up 16 rounds of communication. The protocol leading to the bound of 0.3384 even in a compact representation consists of 18248 game states. These numbers suggest that the task of finding good protocols for the cryptogenography problem as well as understanding their structure is harder than what the simple problem formulation suggests.
Keywords
  • randomized protocols
  • anonymous communication
  • computer-aided proofs
  • solitaire games

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein. From information to exact communication. In Proc. 45th Annual ACM Symposium on Theory of Computing (STOC'13), pages 151-160. ACM, 2013. Google Scholar
  2. Joshua Brody, Sune K. Jakobsen, Dominik Scheder, and Peter Winkler. Cryptogenography. In Proc. 5th Conference on Innovations in Theoretical Computer Science (ITCS'14), pages 13-22, 2014. Google Scholar
  3. George Danezis and Claudia Diaz. A survey of anonymous communication channels. Technical Report MSR-TR-2008-35, Microsoft Research, January 2008. Google Scholar
  4. Benjamin Doerr and Marvin Künnemann. Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem. ArXiv e-prints, 2016. URL: http://arxiv.org/abs/1603.06113.
  5. Sune K. Jakobsen. Information theoretical cryptogenography. In Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP'14), volume 8572 of Lecture Notes in Computer Science, pages 676-688. Springer, 2014. Google Scholar
  6. Sune K. Jakobsen and Claudio Orlandi. How to bootstrap anonymous communication. In Proc. 7th Conference on Innovations in Theoretical Computer Science (ITCS'16), pages 333-344, 2016. Google Scholar
  7. Nan Ma and Prakash Ishwar. The infinite-message limit of two-terminal interactive source coding. IEEE Trans. Information Theory, 59(7):4071-4094, 2013. Google Scholar
  8. Nan Ma, Prakash Ishwar, and Piyush Gupta. Interactive source coding for function computation in collocated networks. IEEE Trans. Information Theory, 58(7):4289-4305, 2012. Google Scholar
  9. Jiří Matoušek. On directional convexity. Discrete & Computational Geometry, 25(3):389-403, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail