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

Fri Jan 10 16:38:06 UTC 2014

A Threshold Signature-based Shared RNG

0.  Overview

This proposal is for a design of a shared RNG to address ticket #8244 -
"The HSDirs for a hidden service should not be predictable indefinitely into the
future," /without/ requiring byzantine agreement protocols at each RNG period.
The basic idea of this proposal is to have directory authorities use a
deterministic threshold signature scheme to sign Hash(time-period) in
each consensus document.  This is done simply by having each authority
contribute a publicly-verifiable share of the signature during the
voting process.  As long as at least ceiling(n/2) authorities
are honest, the signature can be re-constructed by each client.  Since
the signature is hard to compute if you don't control at least
ceiling(n/2) authorities, its inclusion in the input to a hash
function (e.g. for
use in constructing the HS hash ring) will make the output of the hash
function pseudorandom.  (In the strong cryptographic sense that unless
you can break the signature scheme, you can't distinguish the hash
from a truly random string of the same length)

1. Notation and such

This protocol can work over a group G, using a subgroup generated by
an element B of prime order p.  We'll use Curve25519 [Curve25519] for
concreteness, but any group where the Computational Diffie-Hellman
problem is difficult would do.

We'll denote multiplication of scalars (e.g. mod p) by *, e.g. a*b;
we'll denote multiplication of a group element P by scalar a by a.P.

We will make use of Shamir threshold secret sharing, described, e.g.
in Handbook of Applied Cryptography [HAC], over the integers mod p.  For a
subset S = {P_1,...,P_t}  of size t, we'll denote the lagrange
multipliers for S by m_1,...m_t (eg. if each P_i has share s_i of
secret x, then m_1*s_1 + m_2*s_2 + ... + m_t*s_t = x.)

We assume that each authority S_i has a publicly known verification
key VK_i and signing key sk_i for a digital signature scheme (Sign,
Verify).  We model network communications as point-to-point with
bounded delay and assume at most t-1 authorities are compromised.
(Without these assumptions, the consensus voting protocol is also
broken)

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.  A security
proof would model this H as a random oracle.

We'll need a distributed threshold key generation algorithm which
works as follows:
    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.  We discuss choices to implement this protocol in section [DKG]

We will also require a noninteractive zero-knowledge "signature of
knowledge" that can be bound to a message m, to prove that two points
P, Q have a common discrete logarithm to bases B and R respectively.
We denote this proof by
   SK { s : s.B = P && s.R = Q } (m)
and discuss its implementation in section [SKDH].

2. Overall Protocol description [CONSENSUS-RANDOM]

The protocol requires that periodically the authorities run the
distributed key generation procedure to produce the threshold public
key P = s.B, and public key shares P_1 = s_1.B, ... , P_n =
s_n.B. This can be done infrequently, since its only purpose is to
limit key exposure.

For the time period starting at time T, the authorities generate the
shared random
value as follows:

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)

Step 2. [Signature Share]

Each authority S_i uses its secret share s_i and signing key sk_i to
generate its signature share SHARE_i as follows:

     SHARE_i = R || Q_i || PROOF_i || Sign_i(R || Q_i || PROOF_i)
     Q_i         = s_i.R
     PROOF_i = SK { s_i : s_i.B == P_i && s_i.R == Q_i }(S_i || T)

Each SHARE_i is appended by S_i to the network consensus document for
time period
T in a separate section.

Step 3. [Validation]

Tor clients locally validate SHARE_i from server S_i for time period T as
follows:
  i.  Verifythe signature using verification key vk_i.
 ii.  Check that R = H("tor-hs-rand-base-point " || T).
iii.  Verify PROOF_i for points (P_i, Q_i) with bases (B,R) .
SHARE_i is considered valid if and only if all three checks succeed.

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]

iii. Compute RAND = m[1].Q[1] + m[2].Q[2] + ... + m[t].Q[t]

Notice that RAND = m[1]*s[1].R + ... + m[t]*s[t].R = x.R

If there are not enough valid shares, the protocol fails; this
indicates that a majority of the directory authorities are faulty or
compromised.  If we wanted a fail-open solution, possibilities include
hashing the
list of valid SHARE values, or taking the hash of the previous
consensus RAND value. [XXX - other options or opinions?]

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

5. References

[CP92] David Chaum, Torben Pryds Pedersen. "Wallet Databases with Observers",
CRYPTO 92, pp 89-105.  http://link.springer.com/chapter/10.1007/3-540-48071-4_7

[CURVE25519] Daniel J. Bernstein. "Curve25519: new Diffie-Hellman
speed records", PKC 2006, pp 207-228.  http://cr.yp.to/papers.html#curve25519

[DS83] D. Dolev and H. Strong. "Authenticated algorithms for Byzantine
agreement", SIAM J. Computing 12(4):656-666, 1983.
http://www.cse.huji.ac.il/~dolev/pubs/authenticated.pdf

[GKKZ11] Juan Garay, Jonathan Katz, Ranjit Kumaresan, Hong-Sheng
Zhou. "Adaptively Secure Broadcast, Revisited", PODC 11, pp 179-186.
http://chess.cs.umd.edu/~jkatz/papers/asb-final.pdf

[HAC] Alfred Manezes, Paul van Oorschot, Scott Vanstone. "Handbook of
Applied Cryptography", CRC Press, 1996.  http://cacr.uwaterloo.ca/hac/

[KG09] Aniket Kate, Ian Goldberg. "Distributed Key Generation for the
Internet", 29th International Conference on Distributed Computing
Systems, June 2009.   https://cs.uwaterloo.ca/~iang/pubs/DKG.pdf

[Ped91] Torben Pryds Pedersen. "Non-interactive and
information-theoretic secure verifiable secret sharing," CRYPTO91.
http://www.cs.huji.ac.il/~ns/Papers/pederson91.pdf

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