[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[tor-dev] A threshold signature-based proposal for a shared RNG
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