## Explain it like I’m Five: The Socialist Millionaire Problem and Secure Multi-Party Computation

Last week, I talked about interesting concepts in computer science. Most of the resulting discussion revolved around the halting problem, but one person asked for clarification about Yao’s Millionaires’ Problem. What is it? How does secure multi-party computation allow you to solve it? Why is the solution on Wikipedia so complicated?

So, this week, I’m going to explain how to solve millionaire-style problems without resorting to any sort of cryptography.

### The Problem: Socialist Millionaires

Two employees, Alice and Bob, want to know if they are being paid fair wages. They do the same amount of work at the same level of quality, but they suspect that their employer might be taking advantage of one of them.

The easiest way to determine if they make the same amount of money per hour is for both to say “I make X dollars per hour”. Unfortunately, although Alice and Bob trust each other, they are very private about their income. They consider it a huge social faux pas to reveal how much money you make. The possibility of common knowledge of who makes more money is just… too uncomfortably awkward to bear.

Not only do Alice and Bob refuse to reveal how much money they make, to each other or a trusted third party, but they’re a bit technophobic and refuse to enter the information into a computer for fear of it being logged.

How can they find out if they’re being paid fairly, without risking an awkward situation and without using computers? With locked suggestion boxes, of course!

### The Solution: Use Locked Suggestions Boxes

Suppose Alice and Bob each might be making either 10, 20, 30, or 40 $/hour. We’ll arbitrarily say that Alice makes 30$/hour and Bob makes 20$/hour.

- Bob goes to an office supply store and buys four lockable suggestion boxes (with different matching keys). He labels the four boxes as 10$, 20$, 30$, and 40$.
- Bob discards all of the keys except the key for the 20$ box (because that’s how much he makes per hour).
- Bob gives the locked suggestion boxes to Alice. In private, Alice puts a slip of paper saying ‘yes’ into the 30$ box (because that’s how much she makes per hour). She puts slips of paper saying ‘no’ into the other boxes.
- Alice gives the boxes back to Bob. In private, Bob uses his key to unlock the 20$ box and get the slip of paper inside.
- Bob sees that the slip of paper says ‘no’, meaning Alice doesn’t make 20$/hour like he does. He tells Alice they don’t make the same amount of money.
- Bob now knows that Alice doesn’t make 20$/hour, but hasn’t learned if she makes 10, 30, or 40 $/hour. Similarly, Alice now knows Bob doesn’t make 30$/hour, but hasn’t learned if he makes 10, 20, or 40 $/hour.

### Oblivious Transfer

The technical term for what Alice and Bob did in the previous example is oblivious transfer. Alice *transferred* many messages to Bob, but is *oblivious* to which single message Bob received. Alice sent an answer for every possible amount of money Bob might make, but Bob only received the answer corresponding to how much money he actually makes.

Note that there’s a certain amount of trust required for this to work. If Bob is going to lie and pretend he makes 30$/hour, there’s no way to detect the problem. There are also other ways to cheat, but they can mostly be detected or prevented by adding complications to the solution. For example, Bob can show Alice the slip he pulled out, to prove he’s not just lying about the outcome. I don’t want to dig too deep into the details of what types of cheating you can prevent… suffice it to say that it goes very deep.

If Bob and Alice were using computers, instead of physical items, they would have used public key cryptography instead of locked suggestions boxes. This makes the computer protocols harder to understand, but removes a lot of corner cases inherent in the physical protocol. It’s much easier to prevent Alice from secretly marking the slips of paper saying ‘no’, so she can determine which box Bob opened, for example.

### Summary

You can perform oblivious transfers without computers, using locked suggestions boxes.

The ability to do oblivious transfers is the basis for performing any secure multi-party computation.

—

### Discuss on Reddit, Hacker News

—

## 2 Responses to “Explain it like I’m Five: The Socialist Millionaire Problem and Secure Multi-Party Computation”

Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

## Archive

- strilanc
- What Quantum Computers Do Faster, with Caveats
- Naming Things: Fail-Useful
- Detecting Simple Cycles Forming, Faster
- Third Party Bit Commitment
- Angular Velocity is Simple
- Collection Equality is Hard
- Deadlocks in Practice: Don’t Hold Locks While Notifying
- Brute Force Parallelization
- A Year’s Worth of Opinions about Objective-C
- Referencing Substrings Faster, without Leaking Memory
- Not Crying Over Old Code
- Exploring Universal Ternary Gates
- Impractical Experiments #2: Securing Peer to Peer Fog of War against Map Hacks
- Achieving Exponential Slowdown by Enumerating Twice
- Using Immortality to Kill Accidental Callback Cycles
- Cancellation Tokens (and Collapsing Futures) for Objective-C
- Visualizing the Eigenvectors of a Rotation
- Collapsing Futures in Objective-C
- Bug Hunting #1: Garbled Audio from End to End
- Impractical Experiments #1: Representing Numbers as Polynomials
- Implementing Quantum Pseudo-Telepathy
- Turn On Your Damn Warnings
- Big-O Made Trivial
- Unfathomable Bugs #7: The Broken Oven
- Solomonoff’s Mad Scientist
- Yearly Blogging Roundup #1
- What isn’t a Monad
- Searching a Sorted Matrix Faster
- How to Read Nested Ternary Operators
- Making Sublime Text 2 Jump to the Correct Line with Unity on OS X
- My Bug, My Bad #4: Reading Concurrently
- Whole API Testing with Reflection
- Optimizing a Parser Combinator into a memcpy
- Don’t Treat Paths Like Strings
- Breaking a Toy Hash Function
- Counting Iterators Lazily
- Unfathomable Bugs #6: Pretend Precision
- My Bug, My Bad #3: Accidentally Attacking WarCraft 3
- Collapsing Types vs Monads (followup)
- Collapsing Futures: Easy to Use, Hard to Represent
- Eventual Exceptions vs Programming in a Minimal Functional Style
- The Mystery of Flunf
- Explain it like I’m Five: The Socialist Millionaire Problem and Secure Multi-Party Computation
- Computer Science Blows My Mind
- A visit to Execution Labs in Montréal
- Transmuting Dice, Conserving Entropy
- Rule of Thumb: Ask for the Clock
- Rule of Thumb: Use Purposefully Weakened Methods
- Rule of thumb: Preconditions Should be Checked Explicitly
- Intersecting Linked Lists Faster
- Mouse Path Smoothing for Jack Lumber
- My Bug, My Bad #2: Sunk by Float
- Repeat Yourself Differently
- Grover’s Quantum Search Algorithm
- Followup to Non-Nullable Types vs C#
- Optimizing Just in Time with Expression Trees
- When One-Way Latency Doesn’t Matter
- Determining exactly if/when/where a moving line intersected a moving point
- Emulating Actors in C# with Async/Await
- Making an immutable queue with guaranteed constant time operations
- Improving Checked Exceptions
- Perishable Collections: The Benefits of Removal-by-Lifetime
- Decoupling shared control
- Decoupling inlined UI code
- Linq to Collections: Beyond IEnumerable<T>
- Publish your .Net library as a NuGet package
- When null is not enough: an option type for C#
- Unfathomable Bugs #5: Readonly or not
- Minkowski sums: examples
- My Bug, My Bad #1: Fractal Spheres
- Working around the brittle UI Virtualization in Windows 8
- Encapsulating Angles
- Unfathomable Bugs #4: Keys that aren’t
- How would I even use a monad (in C#)?
- Useful/Interesting Methods #1: Observable.WhenEach
- Unfathomable Bugs #3: Stringing you along
- Anonymous Implementation Classes – A Design Pattern for C#
- Tasks for ActionScript 3 – Improving on Event-Driven Programming
- Minkowski sums and differences
- Non-Nullable Types vs C#: Fixing the Billion Dollar Mistake
- Unfathomable Bugs #2: Slashing Out
- Script templates and base classes
- Unity font extraction
- Abusing “Phantom Types” to Encode List Lengths Into Their Type
- Constructive Criticism of the Reactive Extensions API
- Quaternions part 3
- Quaternions part 2
- Quaternions part 1
- Unfathomable Bugs #1: You can have things! You can have things IN things! You can have …
- Coroutines – More than you want to know
- Asset Bundle Helper
- The Visual Studio goes away
- .Net’s time traveling StopWatch
- Introducing Catalyst

Still not getting it… how does it prevent MIM attack?

Suppose a third guy “Mallory” hijacked the 4 boxes in the middle, replaced the four boxes with his own four boxes from office supply store with keys, give to Alice. Alice thought it was from Bob, put the yes slip into the $30 box, give it back to “Mallory”, “Mallory” will now know Alice makes $30/hr.

Then relay the information back to Bob’s boxes.. it’s true, “Mallory” will never know what Bob makes, but “Mallory” did hijack at least one piece of important information?

I’m not sure why Alice or Bob would let the boxes alone… but really there are even simpler attacks, like subtly marking the pages. Just keep in mind it’s meant as a pedagogic example, not a bullet proof system with all contingencies accounted for.