Difference between revisions of "Open Problems:79"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Formatting)
 
(2 intermediate revisions by 2 users not shown)
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.  "How to share a secret without revealing the secret owner?"  Please see Brody et al. {{cite|BrodyJSW-14}}.
+
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.
  
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:'''
 
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?
+
; <span>First round:</span>
 +
: 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.
  
<references />
+
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}}.

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