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 <[email protected]> Date: Sat, 4 Jan 2014 20:45:15 +0100 To: George Kadianakis <[email protected]> > > 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 <[email protected]> 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 ] > > > > _______________________________________________ tor-dev mailing list [email protected] https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
