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:

  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)$ .