Reference : 《Protocol for Secure Computations》, From Andrew C, Yao In 1982
MPC, which means Multi-Party Computation.
Introduction
One sentence to introduce this problem: Two millionaires want to find out who is richer Without leak any additional information about each other's wealth.
This article's structure:
- A precise formulation of Millionaires' problem
Three ways to solve this problem
- By using OWF (One-way function,which is the base of private-key cryptography, )
- discuss the problem about the scale (how many bits) of the communication between two parties and methods to prevent participates from cheating.
- Study the problem "What cannot be accomplished with OWF".
Precise Formulation of Millionaires' problem
The OWF's two kinds of applications when it was proposed:
- The encryption and transmission of messages to make them unreadable and unalterable for adversary
- "Mental poker"
Deterministic Computations
Solution for Millionaires' Problem
Background:
Alice has $i$ millions and Bob has $j$ millions, where $1< i, \ j<10$.
Some Notations:
- $M$ is the set of all $N$-bit nonnegative integers
- $Q_N$ is the set of all 1-1 onto function from $M$ to $M$.
- $E_a$ is the public key of Alice , generated by choosing a random element from $Q_n$
Protocol:
- Bob picks a $N$-bit integer, and computes private value $k = E_a(x)$.
- Bob sends Alice the number $k-j+1$.
- Alice computes privately the values of $y_u = D_a(k-j+u)$ for $u$ = 1,2,...,10.
- Alice generates a random prime $p$ of $\frac{N}{2}$ bits,and computes $z_u = y_u(mod\ p)$ .