On Fri, Jan 10, 2014 at 1:07 PM, Ian Goldberg iang@cs.uwaterloo.ca wrote:
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.
You're right, I misread the section on p.4; if we use Curve25519 the result of the hash needs to be scalar multiplied by 8 to wind up in the subgroup.
- 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.
Hash(x) could be implemented by computing y = SHA256("tor-hs-rand-sok-hash" | x) and taking the first 128 bits of y as the output.
As far as including P,Q,R,S in the hash: sure, sounds good.
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.)
Ha! Yes, byzantine agreement is much easier with a trusted party. :)
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. ;-)
Let's call this the "optimistic approach", and it would certainly be an option, although one issue is that when it fails we can say that someone is malicious but not which authority(s). Although one possibility is to have the ability to fall back to a full byzantine-tolerant protocol in that event.