Consensus Actions in Cipherspace?

dmolnar dmolnar at hcs.harvard.edu
Fri Jan 12 21:23:14 PST 2001




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






More information about the cypherpunks-legacy mailing list