文章基本信息

标题：Searching for Cryptogenography Upper Bounds via Sum of Square Programming
本地全文：下载
作者：Dominik Scheder ; Shuyang Tang ; Jiaheng Zhang 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：149
页码：1-12
DOI：10.4230/LIPIcs.ISAAC.2019.31
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Communication Complexity; Secret Leaking; Sum of Squares Programming