[tor-dev] On the security of a commit-and-reveal solution for #8244
Nicholas Hopper
hopper at cs.umn.edu
Fri Jan 10 16:36:01 UTC 2014
On Thu, Dec 12, 2013 at 11:11 PM, Nicholas Hopper <hopper at 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:
>
> 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
------------------------------------------------------------------------
More information about the tor-dev
mailing list