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
