# Problem 79: Cryptogenography

Suggested by Joshua Brody Banff 2017 https://sublinear.info/79

Cryptogenography is concerned with the following question. "How to share a secret without revealing the secret owner?" Please see Brody et al. [BJSW-14] and Jakobsen [J-16].

In this problem, there are $k$ players and an eavesdropper. Input is a random bit $X \in \{0,1\}$, also called "the secret." The secret owner $J$ is chosen uniformly at random from $[k]$. Players have private randomness and they can communicate publicly on a shared blackboard visible to everyone. Players are said to win if

• everyone learns the secret, and
• eavesdropper does not guess the secret owner correctly.

We are interested in maximizing the probability that players win (maximum success probability).

For $k=2$, the following trivial protocol has success probability $0.25$. Just output $1$. It can be shown easily that maximum success probability is at most $0.5$. The bounds can be improved to $0.3384 \le$ maximum success probability $\le 0.361$.

For large $k$, the following bounds can be shown: $0.5644 \le$ maximum success probability $\le 0.75$.

Can we improve these bounds?