# Difference between revisions of "Open Problems:79"

Line 7: | Line 7: | ||

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 | 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 | * everyone learns the secret, and | ||

* eavesdropper does not guess the secret owner correctly. | * eavesdropper does not guess the secret owner correctly. | ||

Line 13: | Line 12: | ||

We are interested in maximizing the probability that players win (maximum success probability). | 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 $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$. | For large $k$, the following bounds can be shown: $0.5644 \le $ maximum success probability $\le 0.75$. | ||

+ | |||

Can we improve these bounds? | Can we improve these bounds? |

## Revision as of 21:45, 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$. 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?