License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.31
URN: urn:nbn:de:0030-drops-115276
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11527/
Go to the corresponding LIPIcs Volume Portal

Scheder, Dominik ; Tang, Shuyang ; Zhang, Jiaheng

Searching for Cryptogenography Upper Bounds via Sum of Square Programming

pdf-format:
LIPIcs-ISAAC-2019-31.pdf (0.5 MB)

Abstract

Cryptogenography is a secret-leaking game in which one of n players is holding a secret to be leaked. The n players engage in communication as to (1) reveal the secret while (2) keeping the identity of the secret holder as obscure as possible. All communication is public, and no computational hardness assumptions are made, i.e., the setting is purely information theoretic. Brody, Jakobsen, Scheder, and Winkler [Joshua Brody et al., 2014] formally defined this problem, showed that it has an equivalent geometric characterization, and gave upper and lower bounds for the case in which the n players want to leak a single bit. Surprisingly, even the easiest case, where two players want to leak a secret consisting of a single bit, is not completely understood. Doerr and Künnemann [Benjamin Doerr and Marvin Künnemann, 2016] showed how to automatically search for good protocols using a computer, thus finding an improved protocol for the 1-bit two-player case. In this work, we show how the search for upper bounds (impossibility results) can be formulated as a Sum of Squares program. We implement this idea for the 1-bit two-player case and significantly improve the previous upper bound from 47/128 = 0.3671875 to 0.35183.

BibTeX - Entry

@InProceedings{scheder_et_al:LIPIcs:2019:11527,
  author =	{Dominik Scheder and Shuyang Tang and Jiaheng Zhang},
  title =	{{Searching for Cryptogenography Upper Bounds via Sum of Square Programming}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{31:1--31:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Pinyan Lu and Guochuan Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11527},
  URN =		{urn:nbn:de:0030-drops-115276},
  doi =		{10.4230/LIPIcs.ISAAC.2019.31},
  annote =	{Keywords: Communication Complexity, Secret Leaking, Sum of Squares Programming}
}

Keywords: Communication Complexity, Secret Leaking, Sum of Squares Programming
Collection: 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Issue Date: 2019
Date of publication: 28.11.2019
Supplementary Material: http://basics.sjtu.edu.cn/~dominik/sos-cryptogenography/

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI