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.

• 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:

1. The encryption and transmission of messages to make them unreadable and unalterable for adversary
2. "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:

1. $M$ is the set of all $N$-bit nonnegative integers
2. $Q_N$ is the set of all 1-1 onto function from $M$ to $M$.
3. $E_a$ is the public key of Alice , generated by choosing a random element from $Q_n$

#### Protocol:

1. Bob picks a $N$-bit integer, and computes private value $k = E_a(x)$.
2. Bob sends Alice the number $k-j+1$.
3. Alice computes privately the values of $y_u = D_a(k-j+u)$ for $u$ = 1,2,...,10.
4. Alice generates a random prime $p$ of $\frac{N}{2}$ bits,and computes $z_u = y_u(mod\ p)$ .