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

[Nicholas Hopper]

On Fri, Jan 10, 2014 at 1:07 PM, Ian Goldberg <iang at 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.

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

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.

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