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@in.tum.de Date: Sat, 4 Jan 2014 20:45:15 +0100 To: George Kadianakis desnacked@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@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

]

...