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