[messaging] collaborative random number generation

[Michael Rogers]

On 11/12/15 00:15, Joseph Bonneau wrote:
> 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.

I think we may be able to improve on commit-reveal by adding an
intermediate sorting step.

Assumptions:

1. Closed set of participants, some of whom are colluding attackers
2. Some commonly known, predictable value that changes each round, e.g.
the date or a counter

In each round:

1. Each participant commits to a value
2. Any participant who doesn't commit is passed over
3. Hash the predictable value
4. Use the hash to sort the participants
5. The participants reveal their commitments in order
6. Any participant who doesn't reveal is passed over
7. Hash the revealed values to produce the output

In standard commit-reveal, each attacker can influence one bit of the
output by choosing to reveal or not. But sorting reduces the attackers'
combined influence: they can't choose to spend all their bits after the
victims have revealed. Any attacker who reveals before any victim has no
predictable influence on the output, because the victim's reveal
re-randomises the output from the attackers' point of view.

Analysis of exactly how much this helps is left as an exercise for
someone who's better at combinatorics that me. :-)

At the limit, if you run n! rounds there will be at least one round
where a victim reveals last - the attacker has no influence on that
round, and therefore no influence on the hashed output of all n! rounds.

Cheers,
Michael
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0x9FC527CC.asc
Type: application/pgp-keys
Size: 1731 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20151211/1023c2e7/attachment.key>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 473 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20151211/1023c2e7/attachment.sig>