Score:2

Two untrusting people want to come up with a random number

cn flag

Two people want to come up with a random number. They don't trust each other nor any third party. What are the known solutions to this problem?

I am a quantum cryptography student and am currently working quantum random number generation. Any solutions, either classical or quantum are welcome.

EDIT

Ok so here's what I understood by reading through some papers. Assume two mistrusting parties want to come up with a random bit. In the classical scenario (without assuming computational hardness) the task is impossible. In the quantum scenario, there are two variants; strong and weak versions. If the desired outcome of each party is not known it's called the strong version and vice-versa. The strong version has a non-zero bound on its bias whereas the weak version can have an arbitrarily small bias.

https://arxiv.org/pdf/1911.13283.pdf

Frédéric Grosshans avatar
co flag
Not an answer, but just to help your search : this problem is called coin-flipping
Dotman avatar
cn flag
Thank you for that. That really helped!
Score:5
es flag

The random number required is an integer between 0 and $\ell$. Each person picks a random number $x_i$ between 0 and $\ell$, and each person picks an $n$-bit random blinding factor $b_i$ where $n\geq 128$ and $n$ must be agreed in advance. Each then announces a hash commitment calculated as $H(b \mathbin\|x)$. They then each open their commitments by announcing their values of $b$ and $x$, and calculate their random number as $$x_1 + x_2\ \pmod \ell.$$ This is quantum-secure if the hash and choice of $n$ are together quantum-secure.

As @poncho points out, the person that opens their commitment last can simulate a failure to complete the protocol if they are unhappy with the particular shared random value that would be generated during that invocation of the protocol. This could be a problem particularly if $\ell$ is small.

One way of avoiding this problem is to ensure that there is a forfeit for failure to complete the protocol. For example, each person could deposit funds with a trusted arbitrator that would confiscate those funds from the person that did not complete the protocol. The forfeit should equal or exceed the maximum possible gain from simulating a failure.

poncho avatar
my flag
One attack against this protocol is a 'simulated failure' attack; suppose Alice picked $x_1$ and Bob picked $x_2$; they go through the protocol and Alice opens her commitment to $x_1$. Now, Bob see he doesn't like the result $x_1 + x_2 \bmod \ell$, and so he simulates a failure (network failure, computer reboot, whatever). This can be addressed by a metaprotocol; it may be important that you do so
knaccc avatar
es flag
@poncho thanks, great point
kelalaka avatar
in flag
What if there is a really error? Why a honest person should lose fund in this case?
knaccc avatar
es flag
@kelalaka An honest person should resume (rather than restart or abandon) the protocol as soon as technical difficulties are resolved, and there will be no forfeit. A dishonest person would want to abandon the protocol and never resume it.
Score:1
cn flag

I think this paper solves at least partially your problem.

kelalaka avatar
in flag
We call this as link only answer and consider as a comment. Could you a little explain what does this paper?
Dotman avatar
cn flag
This was really helpfull... @kelalaka I will try to add a comment once I understand it
Dotman avatar
cn flag
Ok so here's what I understood by reading through some papers. Assume two mistrusting parties want to come up with a random bit. In the classical scenario (without assuming computational hardness) the task is impossible. In the quantum scenario, there are two variants; strong and weak versions. If the desired outcome of each party is **not** known it's called the strong version and vice-versa. The strong version has a non-zero bound on its bias whereas the weak version can have an arbitrarily small bias.
Score:1
in flag

Manuel Blaum looked this issue in 1981 in Coin Flipping By Telephone A Protocol For Solving Impossible Problems

The technical details are on the paper. This protocol guarantees those (from the paper, bolds are mind);

  1. If either participant following protocol does not catch the other cheating, he or she can be sure that the coins each have exactly 50-50 independent chance to come up heads (provable under the reasonable assumption that factoring is hard.
  2. If either participant catches the other cheating, he or she can prove it to a judge (this assumes that all messages are sent signed).
  3. After Bob flips coins to Alice, she knows which coins came up heads, which tails. He should have absolutely NO idea how they came up (not even a good guess).
  4. After the sequence of coin flips, Alice should be able to prove to Bob which coins came up heads, which tails.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.