On Thu, Dec 12, 2013 at 11:11 PM, Nicholas Hopper hopper@cs.umn.edu 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:
- (Periodically, like once per month): authorities derive a shared
Elgamal key pair (x, X = xB) for the group G. (with prime order p)
- 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)
- After COMMIT_TIMEOUT: each authority takes all published
ciphertexts (with valid proofs), and publishes a list of ciphertexts it received.
- 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 ]
- 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 ------------------------------------------------------------------------