Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Distributed Random Number Generation

I was wondering if there is a way for a network of N participants to agree that a number from 1 to M was chosen at random. (e.g. not influenced by any of the participants) This has been solved for values of n=2 and m=2 by the coin tossing protocol. Does anyone know of any solutions that can work for arbitrary values of N and M?

like image 210
Alexandros Marinos Avatar asked Oct 22 '08 00:10

Alexandros Marinos


People also ask

How do you generate a random number from a distribution?

Use rand to generate 1000 random numbers from the uniform distribution on the interval (0,1). rng('default') % For reproducibility u = rand(1000,1); The inversion method relies on the principle that continuous cumulative distribution functions (cdfs) range uniformly over the open interval (0,1).

What are random number generators used for?

Random number generators or RNGS are hardware devices or software programs which take non-deterministic inputs in the form of physical measurements of temperature or phase noise or clock signals etc and generate unpredictable numbers as its output.

How do I generate a random number from a normal distribution in Excel?

Formula SyntaxUse the formula "=NORMINV(RAND(),B2,C2)", where the RAND() function creates your probability, B2 provides your mean and C2 references your standard deviation. You can change B2 and C2 to reference different cells or enter the values into the formula itself.


1 Answers

Edit

Better algorithm (thanks wnoise):

  1. Everyone picks a secret number from 0 to M-1
  2. Everyone appends a load of random gunk to their number and hashes the result with a secure hash
  3. Everyone tells everyone else this hash
  4. Everyone tells everyone else their secret number, plus the random gunk they appended to it
  5. Everyone verifies that the numbers and hashes+gunk match
  6. Add all the secret numbers together modulo M, then adds 1 to get the final result

As a participant, I should be satisfied with this because I know that I had full influence over the final result - the final number could have been anything at all, depending on my choice of secret number. So since no-one else could predict my number, they couldn't have predicted the final result either.

Any way to reduce the messages from the 3M^2 that i suspect a broadcast approach would require?

I reckon that only the hash publication has to be a broadcast, but it's still O(M^2). I guess the only way around that would be to pre-exchange digital signature keys, or to have a trusted communication hub.

Edit2 - How safe is the hashing thing?

Possible attacks include:

  1. If I can generate a hash collision then I have two secret numbers with the same hash. So once I know everyone else's secret numbers I can choose which of my secret numbers to reveal, thus selecting one of two possible results.
  2. If I generate my secret number and random gunk using a PRNG, then an attacker trying to brute-force my hash doesn't have to try every possible number+gunk, only every possible seed for the PRNG.
  3. I use the number+gunk that everyone reveals to determine information about their PRNGs - I could try to guess or brute-force the seeds, or calculate the internal state from the output. This helps me predict what numbers they will generate next time around, which narrows the search space for a brute-force attack.

Therefore, you should

  1. Use a trusted, unbroken hashing algorithm.
  2. Use a cryptographically secure random number generator that has a big seed / state, and try to seed it from a good source of entropy.
like image 84
nhinkle Avatar answered Jan 06 '23 08:01

nhinkle