Difference between revisions of "Open Problems:79"
Joshuabrody (talk | contribs) |
(Formatting) |
||
| Line 3: | Line 3: | ||
|who=Joshua Brody | |who=Joshua Brody | ||
}} | }} | ||
| − | + | Cryptogenography, introduced by Brody et al. {{cite|BrodyJSW-14}}, is concerned with the following question: “How to share a secret without revealing the secret owner?” | |
| − | Cryptogenography is concerned with the following question | + | 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 | ||
* 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. | ||
| − | 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$. Here is a protocol that achieves success probability $1/3$. |
| − | |||
| − | 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:''' | '''First round:''' | ||
| Line 27: | Line 23: | ||
If the speaker has the secret, announce it, else announce a random bit. | 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}} | |
| − | |||
| − | 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}} | ||
| − | |||
Revision as of 03:16, 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 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: [Jakobsen-14,DoerrK-16]
