1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Didn't spot this earlier why is the second way more secure? What's could be an attack on the first one? $\endgroup$ – John T Jan 8 '14 at 20:14
  • $\begingroup$ The attack on the first one is that user 2 has some function F, and sends F(commitment) as its claimed-to-be-random string. $\:$ In that case, the transcript may be non-trivial auxiliary information about the resulting RNG seed. $\:$ (For example, it could conceivably allow the adversary to find a test that distinguishes the RNG output from uniform and is much simpler than could be found if the adversary was only given a random RNG seed. $\;\;\;$ $\endgroup$ – user991 Jan 8 '14 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.