[messaging] collaborative random number generation

[Jeff Burdges]

Just a quick & dirty summery of the the GNU Name System (GNS) :

We've a zone key Z = z G, a string label s, and a scalar label l =
hash0(s) or hash0(s++Z) probably.  We've an ambient DHT whose
properties we can ignore, but the record with label l in zone Z is:
- encrypted with hash1(l,Z),
- signed with l*Z,  and
- stored at location hash2(l*Z) in the DHT. 
See section 4 of https://gnunet.org/gns-paper

Now there are confirmation attacks on GNS record lookups where
adversaries see when you look up a record they know or see you lookup
the same record as someone else.


Tor has avoided these attacks in their hidden service redesign
specification, but they do so by asking the directory authorities to
generate a random number collaboratively using commit and reveal.

I'd heard that more fully decentralized applications like GNS cannot
use collaborative random number generation algorithms because there are
attacks on collaborative random number generation algorithms that work
once you get beyond a small number of relatively trustworthy machines
and GNUnet has nothing like directory authorities. 


Is there a collaborative random number generation algorithm that works
without a small number of trusted machines though?  

We've the underlying problem that any node can influence at least 1 bit
of the result by choosing to drop out.  There is nothing wrong with
using commit and reveal to compute f(n) > 128+n bits of random
information where n is the maximum number of participating peers. 
 We're in trouble if we hash this in a predictable way to produce a 128
bit number though.  

Instead, we want some multi-stage commit reveal reveal .. reveal
protocol that walks down the amount of information by kicking out nodes
before their late commitments can further impact the result.  

It sounds feasible.  Anyone know if anyone has worked out the details
and security proof for something like this?

Jeff



-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20151208/5558fc68/attachment.sig>