[tor-dev] A threshold signature-based proposal for a shared RNG

Nicholas Hopper hopper at cs.umn.edu
Tue Jan 21 22:15:57 UTC 2014

On Sat, Jan 18, 2014 at 11:05 AM, Kang <td66bshwu at gmail.com> wrote:
> For instance if there aren't enough valid shares then just set RAND = R.

I like this suggestion; thanks.

> Could you please confirm these for me?:
> 1. In your notation x.y = y^{x} mod p.

Sort of - the proposal is to do the arithmetic over an elliptic curve,
not in the integers mod a prime.  And p is the (prime) order of the
point B.  But if we wanted to use a multiplicative group and had a
prime q = 2p+1, then we would have x.y == y^{x} mod q.

> 2. We know P_i and that dlog_B(P_i) == s_i from the DKG protocol. This
> simplifies verification a bit since we don't need to prove that
> dlog_B(P_i) is a valid (private) keyshare, we already know it is.

Well, yes.  But we can check the outcome of the DKG protocol to make
sure that the P_i are valid shares of P.

> 3. The threshold for RAND calculation is the same as the DKG's
> threshold, not a fraction of whoever's online when the RAND
> calculation starts.

Yes, the threshold is an integer fixed at the time of keyshare generation.

> Lastly what purpose does the Sign_i(...) part serve?
> If s_i is _only_ known by S_i, and the zero knowledge proof PROOF_i
> proves that dlog_R(Q_i) == s_i, then the signature seems a little
> redundant since only S_i could have created Q_i.
> Maybe I've missed something here.

It's probably true that if the SoK is computed over the entire message
then there's no need for a separate signature.  The Sign_i part is
just there for overengineering principles.

Nicholas Hopper
Associate Professor, Computer Science & Engineering, University of Minnesota
Visiting Research Director, The Tor Project

More information about the tor-dev mailing list