[messaging] collaborative random number generation

[Natanael]

Den 11 dec 2015 01:16 skrev "Joseph Bonneau" <jbonneau at cs.stanford.edu>:
>
> 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.

Not much unlike my approach;

http://www.metzdowd.com/pipermail/cryptography/2014-April/020678.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20151211/b6a1fe51/attachment.html>