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 So in particular you can build an F() which reconstructs a database from shares x1,x2,...xn and then runs a query on the database. Only the results of the query are output; the theorems tell you that the shares stay secret. "So is it practical?" The answer is NO. These protocols tell you how to secure multiparty compute a function gate by gate. With nontrivial computational overhead and communication per gate. But, hey, at least it's possible! -David