Difference between revisions of "Open Problems:79"
(Created page with "{{Header |source=banff17 |who=Joshua Brody }} <references />") |
|||
| Line 4: | Line 4: | ||
}} | }} | ||
| + | Cryptogenography is concerned with the following question. "How to share a secret without revealing the secret owner?" Please see Brody et al. {{cite|BJSW-14}} and Jakobsen {{cite|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? | ||
<references /> | <references /> | ||
Revision as of 21:38, 31 March 2017
| Suggested by | Joshua Brody |
|---|---|
| Source | Banff 2017 |
| Short link | 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?
