Suppose that an aging Pirate King knows the location of a secret treasure, and before retiring he intends to share the secret among his five shiftless sons. He wants them to be able to recover the treasure if three or more of them work together, but he also wants to prevent a "splinter group" of one or two from being able to get the treasure on their own. To do this, he plans to split the secret of the location into five "shares," giving one to each son, in such a way that he ensures the following condition. If at any point in the future, at least three of the sons pool their shares of the secret, then they will know enough to recover the treasure. But if only one or two pool their shares, they will not have enough information.posted by AceRock at 3:53 PM on January 17, 2011 [1 favorite]
How to do this? It's not hard to invent ways of creating five clues so that all of them are necessary for finding the treasure. But this would require unanimity among the five sons before the treasure could be found. How can we do it so that cooperation among any three is enough, and cooperation among any two is insufficient?
Like many deep insights, the answer is easy to understand in retrospect. The Pirate King draws a secret circle on the globe (known only to himself) and tells his sons that he's buried the treasure at the exact southernmost point on this circle. He then tells each son a different point on this circle. Three points are enough to uniquely reconstruct a circle, so any three pirates can pool their information, identify the circle, and find the treasure. But for any two pirates, an infinity of circles pass through their two points, and they cannot know which is the one they need for recovering the secret. It's a powerful trick, and broadly applicable; in fact, versions of this secret-sharing scheme form a basic principle of modern data security, discovered by the cryptographer Adi Shamir, where arbitrary data can be encoded using points on a curve, and reconstructed from knowledge of other points on the same curve.
The literature on distributed systems is rich with ideas in this spirit. More generally, the principles of distributed systems give us a way to reason about the difficulties inherent in complex systems built from many interacting parts. And so to the extent that we sometimes are fortunate enough to get the impression of a unified Web, a unified global banking system, or a unified sensory experience, we should think about the myriad challenges involved in keeping these experiences whole.
Serial Killers Non-Serial Killers
Drink Milk 90% 89%
Don't Drink Milk 10% 11%
Now the claim is seen for the more or less trivial thing that it is. But so often just one of those numbers is given, and people assume the rest.« Older What is needed is a realization that power without... | High profile cybercrime resear... Newer »
This thread has been archived and is closed to new comments
posted by AceRock at 12:02 PM on January 17, 2011 [3 favorites]