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

Tue Feb 11 23:01:00 UTC 2014

Hello.
As part of my undergraduate thesis I wrote up the protocol suggested here.
I figured someone might find it useful so I've attached a PDF version
of it to this email.
Feel free to use it for any purpose.

On Sat, Jan 11, 2014 at 3:08 AM, Nicholas Hopper <hopper at cs.umn.edu> wrote:
> 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
> ------------------------------------------------------------------------
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: nonce.hopper.pdf
Type: application/pdf
Size: 242800 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20140212/c3b819fe/attachment-0001.pdf>