On Thu, Dec 12, 2013 at 11:11 PM, Nicholas Hopper <[email protected]> wrote: > Your analysis looks correct to me. But what's wrong with using > threshold crypto or secret sharing? Since you're already assuming > some sort of bounded delay synchronization, I think we can eliminate > any advantage in influencing the randomness with one extra round, > using e.g. threshold Elgamal: > > 0. (Periodically, like once per month): authorities derive a shared > Elgamal key pair (x, X = xB) for the group G. (with prime order p) > > 1. each authority publishes a randomly chosen encrypted group element > P_i: (r_iB, r_iX+P_i) along with a proof of knowledge of r_i. (an > easy proof to implement) > > 2. After COMMIT_TIMEOUT: each authority takes all published > ciphertexts (with valid proofs), and publishes a list of ciphertexts > it received. > > 3. After AGREE_TIMEOUT: each authority takes all published, valid > ciphertexts that appear in over half of the previous set of documents, > and adds them componentwise to get an encryption of the sum of the > group elements (sB, sX+Q). Each authority publishes this ciphertext > plus its decryption share of this ciphertext with a proof of correct > decryption. (this is also a pretty straightforward proof to > implement) > > [ here s is the sum of the scalars r_i, Q is the sum of the group elements > P_i ] > > 4. After REVEAL_TIMEOUT: each authority combines the valid decryption > shares to get a random group element Q, and publishes a signed > document containing the decryption shares and Q.
Kang pointed out to me in private email that *this* protocol doesn't avoid the need for some sort of consensus about what was sent by other authorities at each time period. This can be solved but it gets messy. I started a separate thread that describes a solution that doesn't have this issue. ------------------------------------------------------------------------ Nicholas Hopper Associate Professor, Computer Science & Engineering, University of Minnesota Visiting Research Director, The Tor Project ------------------------------------------------------------------------ _______________________________________________ tor-dev mailing list [email protected] https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
