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.
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:
- Each player P_i broadcasts a boolean b_i.
- 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
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