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

[Ian Goldberg]

On Fri, Jan 10, 2014 at 10:38:06AM -0600, Nicholas Hopper wrote:
> We'll need a hash function H that can output elements of the subgroup
> generated by B with unknown discrete logarithms.  For Curve25519, it
> should work to compute H(x) by computing SHA256(x), and mapping this
> 256-bit string to the curve as in the Curve25519 paper.

Careful here.  Curve25519 doesn't represent points at all; it only
represents x-coordinates.  Also, most of those x-coordinates aren't of
points in the subgroup generated by B (assuming you use the standard B).
Can you be more specific about "as in the Curve25519 paper"?  What's
given on p.4 doesn't necessarily land you in the subgroup.

> Step 1.  [Period Base]
> 
> Each authority (and anyone else interested) generates the "time
> period base point"  R in G, by computing
> 
>        R = H("tor-hs-rand-base-point " || period valid-after time)

And this is where the above may bite you.  But perhaps multiplying the
above result by 8 may be good enough to solve the problem?

> Step 4. [Aggregation]
> 
> If at least t = ceiling(n/2) valid shares appear in the consensus, Tor
> clients locally compute the randomizer string RAND for time period T
> as follows:
> 
> i.  Let (S[j], Q[j]) for j = 1,...,t denote the identities (S_i) and signature
> shares (Q_i) associated with t valid SHARE_i  values.
> 
> ii.  Compute the Lagrange multipliers m[j] for x points S[1]...S[t]

"for t points"?  In a full spec, this step would also need to be spelled
out, of course.

> 3. Signature of knowledge scheme [SKDH]
> 
> Given values (R,S), bases (P,Q), and exponent s such that R=s.P, S = s.Q,
> we use the "Fiat-Shamir Heuristic" with the proof of equality of
> discrete logarithms due to Chaum-Pedersen [CP92, Sec. 3.2] to generate
> 
> SK { s : s.P == R && s.Q == S } (m)
> 
> As follows:
> 
>  i. Choose random integer a in [0,p-1]
> ii. Compute:
>     U = a.P
>     V = a.Q
>     c = Hash(U || V || m)

You haven't defined "Hash".  I'd also be happier if P,Q,R,S were thrown
in there as well.

>     z = a + s*c (mod p)
> iii. Output (U,V,z)
> 
> The proof is verified by computing
>        cc = Hash(U || V || m)
> and checking that
>        z.P == U + cc.R
>        z.Q == V + cc.S
> 
> 
> 4. Distributed Key Generation [DKG]
> 
> We'll need a protocol satisfying the following specs:
>     Input: Parties S_1,...,S_n
>     Output: to all players: group public key P = x.B. player public
> key shares s_1.B, ..., s_n.B
>          to each player P_i: secret key s_i
> 
> such that the secret keys s_i are (n,t) secret shares of the (unknown)
> secret key x.
> 
> There are several options for such a protocol, depending on what we
> want to assume about the network over which the authorities will run
> the protocol (Presumably, the Internet):
> 
> - If we assume "weak synchrony" (messages are eventually delivered
>   without unbounded delay), the protocol of Kate and Goldberg [KG09]
>   can tolerate floor((n-1)/3) corruptions and still run to completion.
> 
> - If we assume bounded delay but allow "rushing" adversaries and
>   adaptive corruptions, the protocol of Garay et al [GKKZ11] can be
>   used to realize the broadcast channel required for Pedersen's
>   protocol [Ped91] while tolerating up to t-1 = floor(n/2) corruptions.
> 
> - If we assume bounded delay and static corruptions, the protocol of
>   Dolev and Strong [DS83] can be used to realize the broadcast channel
>   required for Pedersen's protocol and tolerate up to t-1 corruptions.
> 
> I'm not an expert on byzantine agreement protocols, so it is possible that
> there exist other, more easy to implement/manage options as well.

Yes: Nick (who would probably be the one writing the code anyway)
generates the shares encrypted to keys generated by the authority
operators, sends them to the authority operators, and forgets the
intermediate results.  ;-)  (Only partially kidding.)

Then again, if *that* code is written, then just having each authority
operator run an instance of that code in the role of Nick, and having
everyone add their results, works fine if everyone is online.  It's also
easy to check that the protocol succeeeded, by interpolating the
resulting public keys.  An actively malicious adversary during this
phase would cause the protocol to fail, but I think it would be good to
know that we have an actively malicious authority.  ;-)

   - Ian