On Fri, Nov 22, 2013 at 9:55 AM, George Kadianakis desnacked@riseup.net wrote:
(This message has been sitting in my drafts for a week or so, because I fear that it might make no sense. Today I cleaned it up and decided to post it.)
Hello Nick and Elly,
we were recently discussing various commit-and-reveal schemes to accomplish the unpredictability of HSDir positions in the hash ring.
This is a thread to better coordinate on this subject. The corresponding trac ticket number is 8244.
I left our IRC discussion with two conclusions in mind:
a) The simple approach of a commit-and-reveal protocol can not be entirely secure since an adversary could choose not to reveal his value (abort) which would allow him to influence the final result.
b) Proper protocols that achieve this goal are ugly, both in elegance and in the number of rounds. This is basically the Byzantine agreement problem which has ugly solutions and funny impossibility results.
We started thinking of how disastrous a commit-and-reveal scheme could be for our specific use case, and we decided that it's worth thinkihng more about before moving to other heavyweight protocols.
(re-posting this reply to tor-dev at George's request)
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.