At 12:23 AM 1/13/01 -0500, dmolnar wrote:
On Fri, 12 Jan 2001, David Honig wrote:
(Thinking out loud) Maybe the actions require access to a distributed N-of-M database? How do you prevent someone from reusing the reconstructed database? Or uncooperatives refusing to update their slice of the DB?
One way to address this problem is to use secret sharing. Everyone gets a share. Only a certain threshold need to cooperate to reconstruct. Everyone's secret counts the same, so in order to deny service you need to have fewer than threshold non-cooperatives.
You never reconstruct the database in one place. Instead, you figure out a clever way to do a distributed query on the database shares, such that at the end of the protocol, out pops the result. There are plausibility results due to Ben-Or, Goldwasser, Goldreich, Wigderson, and others about this under the name "secure multiparty computation." Briefly, if you can express a boolean F function with n inputs, then n parties can get together and evaluate F(x1,x2,...,xn) such that
* everyone learns the output * no one learns anything about an xi not their own
Suppose the action to be voted on is an update of the distributed DB [1]. How do you enforce an *update* on the shares? Wouldn't that require the cooperation of all shareholders? I would think that enough noncooperative shareholders could fork off their own group, diverging from the point where they didn't update their shares. [1] For instance, the DB could be the list of members, the action could be to add or drop a member. Also, some group actions might compromise the DB itself, and so it seems to me that you'd often need a trusted server which accepts votes on its actions. Though I realize this implies a central point of attack/control (the Napster problem).