Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Thanks for the elegant answer! –  Jacob Torba Jan 8 at 7:31
    
Didn't spot this earlier why is the second way more secure? What's could be an attack on the first one? –  Jacob Torba Jan 8 at 20:14
    
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. $\;\;\;$ –  Ricky Demer Jan 8 at 20:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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