Wednesday, 15 January 2014

Trusted random number generation

When you're engaging in some activity online that requires random numbers and you don't know if you can trust the other side, you have a problem. Say it's a game, and you each need to roll dice regularly. If you each just generate random numbers and tell each other what they were, you can't know that your opponent isn't lying in their own favour. You also can't just generate the random numbers for each other, because that has the same problem. To trust the randomness, you need something that neither side can lie about, that can't be rigged to favour one side or the other, and that can't be known ahead of time.

Something like this:
  1. Both encrypt a seed and send it.
  2. Once you receive your partner's seed, send the key to decrypt your side. This is important, because your partner can't change their seed at this point, and neither can you.
  3. Decrypt the seeds and combine them in some agreed way (say, by multiplying or adding them together).
  4. Generate a random number using the combined seed.
  5. Discard seeds and start over to avoid look-ahead cheating.
It seems simple enough, and there are some variations you can do for other, more complicated scenarios. Unfortunately, it doesn't stretch far beyond the limited concept of shared, verified randomness. It can't be used to verify identity, for instance. It only tells me that I can trust the random numbers generated this way, not that the other machine generating them is who I expect to be on the other end. Also, since I'm not a security expert, it's possible (or very likely) that there's a blatant flaw in the scheme that allows it to be biased for some purpose. I don't know.

Mokalus of Borg

PS - So far I've been unable to determine a version that allows the equivalent of both sides drawing random cards and keeping them secret.
PPS - For now, this is obviously a trusted P2P dice mechanism and nothing more.

No comments: