[tor-dev] On the security of a commit-and-reveal solution for #8244

[Nicholas Hopper]

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
------------------------------------------------------------------------