Editing Open Problems:79

{{Header
|source=banff17
|who=Joshua Brody
}}
Cryptogenography, introduced by Brody et al. {{cite|BrodyJSW-14}}, is concerned with the following question: &ldquo;How to share a secret without revealing the secret owner?&rdquo;
In this problem, there are $k$ players and an eavesdropper.  Input is a random bit $X \in \{0,1\}$, also called &ldquo;the secret.&rdquo;  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$.  Here is a protocol that achieves success probability $1/3$.

'''First round:'''
If Alice has the secret, 

* with probability $2/3$ she asks Bob to speak second
* with probability $1/3$ she speaks second.

Else (vice-versa)
* with probability $2/3$ she speaks second
* with probability $1/3$ she asks Bob to speak second.

'''Second round:'''
If the speaker has the secret, announce it, else announce a random bit.

For large $k$, the following bounds can be shown:  $0.5644 \le $ maximum success probability $\le 0.75$. Can we improve these bounds? For more information, including state of the art bounds, see: {{cite|Jakobsen-14|DoerrK-16}}