# Difference between revisions of "Open Problems:79"

(Formatting) |
(Formatting) |
||

Line 10: | Line 10: | ||

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$. | 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$. | ||

− | + | ; <span>First round:</span> | |

− | If Alice has the secret, | + | : If Alice has the secret, |

+ | :* with probability $2/3$, she decides that Bob speaks in the second round | ||

+ | :* with probability $1/3$, she speaks in the second round. | ||

+ | :Else (if she does not have the secret) | ||

+ | :* with probability $1/3$, she decides that Bob speaks in the second round | ||

+ | :* with probability $2/3$, she speaks in the second round. | ||

− | + | ; <span>Second round:</span> | |

− | + | : If the speaker has the secret, announce it. Otherwise, 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 the state of the art bounds, see the papers of Jakobsen {{cite|Jakobsen-14}} and Doerr and Kunnemann {{cite|DoerrK-16}}. | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | 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 |

## Latest revision as of 03:32, 28 April 2017

Suggested by | Joshua Brody |
---|---|

Source | Banff 2017 |

Short link | https://sublinear.info/79 |

Cryptogenography, introduced by Brody et al. [BrodyJSW-14], is concerned with the following question: “How to share a secret without revealing the secret owner?” 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$. Here is a protocol that achieves success probability $1/3$.

- First round:
- If Alice has the secret,
- with probability $2/3$, she decides that Bob speaks in the second round
- with probability $1/3$, she speaks in the second round.

- Else (if she does not have the secret)
- with probability $1/3$, she decides that Bob speaks in the second round
- with probability $2/3$, she speaks in the second round.

- Second round:
- If the speaker has the secret, announce it. Otherwise, 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 the state of the art bounds, see the papers of Jakobsen [Jakobsen-14] and Doerr and Kunnemann [DoerrK-16].