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

Kang td66bshwu at gmail.com
Thu Jan 16 17:17:05 UTC 2014

I don't think that a solution which uses DKG is overkill, I think it
would be more secure.
The more all-or-nothing security provided by DKG based schemes seems
preferable to the sliding-scale-of-influence provided by coin flipping
Then again I don't know that much about coin flipping protocols so
that could simply be me being ignorant.

On the other hand he's right that DKG-based schemes would probably be
more complex, at least in regards to number of calculations.
For instance the Fouque protocol.
I've actually implemented a proof-of-concept version of the Fouque
protocol and it's not at all efficient.
Using a 1024 bit prime it can run for 5 participants in about 2
minutes (calculations only) on a single decent computer.
I imagine a more speed focused implementation running over 10
directory authorities would have an acceptable runtime, but 20 or 30
authorities might be pushing it.

Luckily other DKG protocols apparently have far less complexity [ O(n)
as opposed to O(n^2) ] since they don't have the nice
one-round-sharing-phase feature.

I guess it's all just a balancing act with no real correct answer.
Security vs calculation complexity vs network traffic vs protocol
complexity vs ...

More information about the tor-dev mailing list