[tor-dev] Proposal 225: Strawman proposal: commit-and-reveal shared rng

[George Kadianakis]

I'm forwarding a private email by Florian Dold which is related to
this discussion. I talked with Florian during CCC and we talked some
more over email. Reposting with his permission.

Thanks!


From: Florian Dold <dold at in.tum.de>
Date: Sat, 4 Jan 2014 20:45:15 +0100
To: George Kadianakis <desnacked at riseup.net>
>
> Hi!
>
> I'm afraid there is not much usable information in the slides, it's
> just a quick overview of what I'm currently implementing for GNUnet
> ...
>
> However, I do have some comments / ideas for the distributed nonce
> generation in Tor.  From what I read, most of your current efforts
> focus on protocols for distributed *key* generation, which might be
> overkill, as your scenario needs less structure --- only a random
> value, not a key pair must be generated.
>
> There's been a lot of theoretical discussion about that in literature
> about exactly that, usually under the name "Collective Coin Flipping"
> or "Leader Election" (which also must generate a random number), and I
> think these ideas are more appropriate for your problem than those
> from DKG.
>
> Let me sketch how their protocols (see [1], [2] and many many more)
> work. For simplicity, let's only generate single bit:
>
> 1. Each player P_i broadcasts a boolean b_i.
> 2. The resulting random bit is f(b_1,...,b_n)
>
> Now, when f = XOR, this corresponds exactly to the protocol we
> discussed, which is not secure against adaptive adversaries.  However,
> when choosing f as the majority function
>
> f(b_1,...,b_n) = 1 if sum(b_1,...,b_n) > ceil(n/2), 0 otherwise
>
> it won't be as easy for a single player (or even a small coalition) to
> influence the resulting bit (as there's a chance that their choices
> don't even influence the final result).
>
> There are constructions for the function 'f' in literature that are
> even more influence-resilient than the majority function.
>
>
> But of course, this is only part of the issue: Problems arise when
> players don't broadcast their values correctly.  This essentially
> boils down to the byzantine consensus problem, and there are various
> approaches to this.  One of the simplest implementations of this are
> based on gradecast [3], a multicast protocol that also gives a
> "confidence level" for the correctness of the broadcast.  There are
> many optimizations of gradecast, including some probablistic
> constructions for settings with a large number of players.
>
> The last paragraph, however, also might apply to distributed key
> generation that do *not* use the Fouque-protocol with its complex
> zero-knowledge proofs of fair encryption to avoid private channels.
>
>
> Does this help?  While still somewhat complex, the collective coin
> flipping protocols are probably still less complex than establishing a
> distributed key and then doing threshold elgamal, as proposed by
> Nicholas Hopper.
>
> Happy Hacking!
> Florian
>
> [1] http://www.cs.huji.ac.il/~nati/PAPERS/coll_coin_fl.pdf
> [2] www.cs.yale.edu/homes/aspnes/papers/stoc97-proceedings.pdf
> [3] http://arxiv.org/abs/1007.1049
>
> On Sat, Jan 4, 2014 at 6:38 PM, George Kadianakis <desnacked at riseup.net>
wrote:
> > Hey there,
> >
> > I'm the guy that talked with you about Distributed Key Agreements in CCC.
> > We talked about its applications in Tor (we need Distributed Nonce
> > Agreement) and attacks on the naive commit-and-reveal method.
> >
> > I was wondering if your slides or talk is uploaded somewhere on the
> > Internet. I found
> > https://gnunet.org/content/video-30c3-talk-gnu-name-system but it doesn't
> > seem to be the one I was looking for.
> >
> > Thank you!
> >
> > [BTW, the relevant Tor ticket is:
> > https://trac.torproject.org/projects/tor/ticket/8244
> > and the threshold elgamal idea is here:
> > https://lists.torproject.org/pipermail/tor-dev/2013-December/005944.html
]
> >
> >