I\'ve been having trouble with coming up with a random number generator that pro

Question

I've been having trouble with coming up with a random number generator that produces a random number between two parties. My current scheme is this:

User 1 gives user 2 the hash of their randomly generated seed, user 2 responds with their unhashed seed. User 1 generates the random number by feeding his own unhashed seed and user 2's seed into a seeded RNG. User 1 discloses the resulting random number and discloses his own seed. User 2 accepts the outcome if the seed matches the hash and seeded RNG produces the same.

I'm not too good with the cryptography behind this but is this safe? Is it okay to just make the RNG seed by just appending one seed to the other? Is there any specific RNG I should use?

Explanation / Answer

Why should user 1 disclose the resulting random number in addition to disclosing his own seed,
when user 2 can compute the resulting random number from the two seeds?

That might be safe enough, but it's far from secure.
For one thing, each user obtains user obtains proof that the "random number" is only pseudorandom.
For another thing, one would need to hope that the RNG still works well when one half of its
seed is chosen in a way that adversarially depends on the hash of the other half of its seed.

A simple, somewhat good way is the following:
User 1 gives user 2 a commitment to a random string whose length is equal to the RNG's seed length.
User 2 gives user 1 a random string whose length is equal to the RNG's seed length.
User 1 sends User 2 the opening of the commitment, and both users
feed the xor of the two allegedly random strings into the RNG.

A secure way is the following:
User 1 gives user 2 a commitment to a random string whose length is equal to the output length,
and a zero-knowledge argument of knowledge of how to open the commitment.
User 2 gives user 1 a random string whose length is equal to the output length.
User 1 gives user 2 the value that was committed to (but not the opening information!),
and a zero-knowledge argument of knowledge of how to open the commitment to that value.
Both users output the xor of the two allegedly random strings.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.