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.
- 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
- 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