[messaging] collaborative random number generation

[Joseph Bonneau]

I can give some context on public randomness sources since I have been
thinking about this a lot over the past year. This is tangentially related
to secure messaging but here is a summary.

There are 3 basic approaches I know of:
(1) Commit and reveal. This either requires bounties to punish participants
who don't reveal (this can be enforced in Bitcoin or similar
cryptocurrencies) or the protocol is vulnerable to manipulation by parties
who don't reveal.

(2) The unicorn protocol proposed by Lenstra/Wesolowski (
https://eprint.iacr.org/2015/366.pdf). Any party can submit random nonces
directly and the result is a hash of all of them. But, the hash is a
specially designed slow and non-parallelisable hash. At time t0 you stop
accepting new inputs, and the hash takes until time t1 to complete. (t1-t0)
must be long enough that it is beyond any reasonable clock skew. This is a
promising approach but has a few problems in practice, you have to reason
about clock skew and hardware acceleration of the hash and it requires a
designated leader.

(3) Randomness as a byproduct of Bitcoin-style consensus protocols. I wrote
this up here: https://eprint.iacr.org/2015/1015.pdf. The basic idea is that
you hash the most recent Bitcoin block. The puzzle solution guarantees that
there is significant min-entropy in each block, equal to the difficulty of
the puzzle. Manipulating this requires manipulating the consensus protocol,
either by finding valid blocks and discarding them or trying to
preferentially propagate blocks in the event of a tie. These attacks are
clearly computationally possible, but expensive. Bitcoin is designed to
make them hard.

Personally I lean towards approach #3 being the most practical for many
applications, including yours. If the adversary's goal is to violate
privacy and they have to launch an expensive attack on Bitcoin consensus to
do it, you are probably okay. The nice part is that the protocol is
completely non-interactive, everybody just samples from the Bitcoin network
and you have your randomness.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20151210/f6aac66f/attachment.html>