[messaging] collaborative random number generation

[Jeff Burdges]

Oops, I omitted some explanation.  The point is that, in both cases
we're trying to do some sort of lookup.  Ideally we'd prefer that the
hash that gives the lookup location used a seed that changes over time,
 is common to all machines on the network, and cannot be predicted or
controlled by an adversary.  


On Tue, 2015-12-08 at 04:59 +0100, Jeff Burdges wrote:
> 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
> 
> 
> 
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging
-------------- 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/48d56f57/attachment.sig>