Hello.
Adversaries who control a subset of the authorities should not be able to influence the result (except if they control a majority of the authorities; in which case Tor is screwed anyway).
If you're willing to live with that then it should be possible to make a ``perfect'' protocol. I'll attach some notes regarding one potential solution to the end of this email. Perhaps you can see some flaws in this that I can't.
Another idea that has occured to me is that you could make the probability of natural failure tiny, and hence make it significantly easier to identify troublemakers. For instance you could extend the protocol to have each participant select k random onion-routers to be their ``backups''. They could give their contribution (properly encrypted, ofcourse) to each of these backups, then tell the other participants who these backups are. If a participant vanishes during the reveal stages of the protocol you can retrieve their value from their backups instead. This means that for an adversary to back out it needs to shut down both itself and all its backups. If a single directory authority goes down for a short amount of time it's not particularly unusual; on the other hand if a directory authority and all k of its personally selected backups are unreachable that's _very_ unusual, and can't really be attributed to network unreliability alone.
Regards
-----
#METHOD USING SECRET SHARING ##Apologies if the formatting gets mangled or it's a little rough in some parts This is a method of calculating a shared random value that should be secure against cheating as long as the majority (> 50%) of players are honest. That is, it can support a maximum of floor((n-1)/2) collaborating adversaries, where n is the total number of participants in the protocol. It's a mix of bit commitment and secret sharing.
The protocol should involve O(n^2) messages, but since it's designed to be used on only a small number of directory authorities (about 10) and only run once or so per day this isn't a huge issue. That's probably about the same number of messages involved a vanilla bit commitment scheme since it follows the same two phase design.
The method has two phases. In the first phase each participant generates a value, then splits it into n-1 shares using a (t, n-1)-secret-sharing method. They distribute those shares to the other players along with a commitment. The commitment is to protect against attacks where an adversary can select the result; it converts such attacks into a secondary backing out attack. Once all participants have received n-1 shares (one share from each other player) the next phase begins. During this phase they simply distribute all their known shares until all players are able to reconstruct all secrets; at which point they can calculate the shared random as some function of those.
If I haven't made any mistakes this method should prevent any kind of backing out or influencing the result provided that more than 50% of the participants are honest [logic behind this later]. It's not the most efficient algorithm, nor is it [probably] the most secure, but it is fairly simple and if 50% or more of the directory authorities are adversaries then there's likely far larger threats to worry about. Additionally a perfect algorithm that uses this basic form (generate contributions and distribute them to the others) may be impossible (deterministic multi-party fair exchange protocols that don't involve a trusted third party have been proven impossible).
The share combination function could simply be XOR. Provided at least one of the contributions is random the XOR of all contributions together should also be random.
-----BASIC ALGORITHM & NOTATION t = secret sharing threshold = number of shares required to reconstruct a secret. n = number of participants. d = number of collaborating adversary participants.
1. Commit phase. 1.1. Each participant generates or selects a random value to be their contribution (the exact method isn't important here). 1.2. Each participant uses a secret sharing scheme to split their value into n-1 shares. 1.3. Each participant distributes these shares, one to each other participant. 1.3.1. When this is complete each participant will have n-1 shares; 1 share from each other participant. 1.3.2. When a participant has received all n-1 they send a PHASE_COMPLETE message to the others to signify they're ready to begin the revelation phase (these messages should also contain all n-1 received commitments). 1.3.3. When a participant has received all n-1 shares, and additionally has received all n-1 PHASE_COMPLETE messages they begin the revelation phase. TODO: failure process [timeout? Process should NOT continue without the missing shares, it should restart from the beginning. Continuing could allow adversaries to have honest participants excluded by claiming they never sent their shares out. [Fix by sending bundle of all shares, each share encrypted with a different participant's key -> they receive all shares but can only decrypt one]] 2. Revelation phase. 2.1. Each participant sends their whole list of n-1 received shares to the other participants. 2.1.1. When this is complete each participant will have (n-1)*(n-1) shares [not including its own shares, which it of course knows]. 2.2. Using those shares Each participant reconstructs the n-1 secrets belonging to the other participants. 2.3. Each participant calculates the shared random value as some function of all n secrets [n-1 secrets created by the other participants, plus the secret they created themselves].
-----[BACKING OUT ATTACK (during reveal phase)]----- Possible when n-d < t. [num honest < threshold] Not possible when n-d >= t. [num honest >= threshold]
If t = n-1, and d = 2 participant is bad. Then: 1. Commit phase goes normally. 1.1. Each participant generates a secret, splits it into n-1 shares, then distributes one to each other participant. 1.2. Each individual participant now has n-1 shares, 1 share from each secret. 1.3. The d collaborating adversarial participants pool their shares to get (n-1)*d + d*(n-d), all the shares of each adversarial secret and d shares from each honest secret [not enough to reconstruct them]. 2. Reveal phase: 2.1. Honest participants send all their known shares to all the other participants. 2.2. Adversarial participants just wait and listen. 2.3. Honest participants now have (n-d)*(n-1) shares each, n-d shares from each secret. 2.3.1. (n-d) < t, that is (n-2) < (n-1), so honest participants don't have enough shares to reveal the secrets. 2.4. Adversarial participants now have n*(n-1) shares, n-1 shares from each secret [that is, they have all the shares from all secrets]. 2.4.1. This is enough for the adversarial participants to reconstruct all secrets. 2.4.1.1. If the adversaries like the result they give their shares to the honest participants to finalise it. 2.4.1.2. If the adversaries don't like the result they withhold their shares, meaning that the secret is unrecoverable to the honest participants and therefore they have no choice but to calculate a different value.
-----[BACKING OUT ATTACK (during commit phase)]----- Possible when t <= d. [threshold smaller than or equal to the number of adversaries] Not possible when t > d. [threshold larger than number of adversaries]
Say t <= d. Then: 1. Commit phase. 1.1. Each _honest_ participant generates a secret, splits it into n-1 shares, then distributes one to each other participant. 1.2. Adversarial participants just wait to receive shares. 1.3. Once each adversary has received a share from each honest participant they pool their knowledge to get a list of d*(n-d) shares, d shares from each honest participant's secret. 1.4. Since t <= d the adversaries know enough shares to reconstruct each honest participant's secret and therefore calculate the final result before the others. 1.5.1. If the adversaries like the result they give their shares to the honest participants to finalise it. 1.5.2. If the adversaries don't like the result they withhold their shares, meaning that the secret is unrecoverable to the honest participants and therefore they have no choice but to calculate a different value.
-----HOW TO PREVENT BOTH ATTACKS? Remember that d is the maximum number of adversaries we can defend against, and t is the secret sharing threshold. So at what values for t and d are both backing-out attacks prevented?
n-d >= t AND t > d convert to: n > 2d AND d < t <= n - d
n > 2d so n/2 > d [we can only prevent both types of attack if less than half of the participants are adversaries] or floor(n/2) > d, since we're dealing with integers here
so d = floor((n-1)/2) = the maximum possible number of adversaries we can handle while defending against both backing out attacks. Putting this value for d in the equation for t then gives: floor((n-1)/2) < t <= n - floor((n-1)/2)
Example: n = 10 d = 4 4 < t <= 6 t in [5, 6]
n = 11 d = 5 5 < t <= 6 t in [6]
n = 12 d = 5 5 < t <= 7 t in [6, 7]
n = 13 d = 6 6 < t <= 7 t in [7]
...
We'll choose the smaller value for t when more than one is possible. t = d + 1