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@xxxxxxxxxx> 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@xxxxxxxxxxxxxxxxxxxx
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Attachment:
nonce.hopper.pdf
Description: Adobe PDF document
_______________________________________________ tor-dev mailing list tor-dev@xxxxxxxxxxxxxxxxxxxx https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev