Distributed computing

Spy Border puzzle (McCarthy/Rabin)

• Spies go across border.
• When they return, they don’t want to be shot so they want to give a password.
• Spies are clever and professional but border guards have been known to have loose tongues, so conventional password might get leaked.
• What to do? (Hint: one-way functions)

Courier Problem

• Capture a courier and you may change history (e.g., Hannibal and his brother Mago).
• So want to send n couriers with parts of a message. If majority of couriers arrive, then can reconstruct message. Any minority reveal nothing.
• How to do this? (Hint: start with three couriers.
• Hint 2: polynomial of degree 2 can be determined by three points.)

Assuring honesty in SETI-at-home

• I want a site to execute a function f on x1, x2, …, xn.
• How do I know it’s doing so?
• Possibility: Compute some of the values e.g. f(xi) and f(xj), and send those too. Ask to be told i and j.
• Still some possibility of cheating, e.g. once those two indices are found, could give guesses for other f(xk)s.

Better Solution

• Also send some value y such that for NO j is it the case that y = f(xj). (Don’t tell of course)
• Now the function producer must state that y is not the result of f on any input.
• Function producer could guess this, but then risks getting caught.
• Ref: Radu Sion