Millionaires_GMW.ml

(** Yao's millionaires problem: comparing two encrypted integers
    using MPC with the GMW Boolean sharing schema. *)

(* Copyright Xavier Leroy.  License: GPL 2 or later *)

open Printf
open GMW

(* The full adder. *)

let full_adder a b cin =
  let t = xor a b in
  let s = xor t cin in
  let u = and_ t cin in
  let v = and_ a b in
  let cout = or_ u v in
  (s, cout)

(* N-bit comparator *)

let rec comparator al bl cin =
  match al, bl with
  | [], [] -> cin
  | a :: al, b :: bl ->
      let (s, cout) = full_adder a (not b) cin in
      comparator al bl cout
  | _, _ ->
      assert false

(* Share a secret [n] (an integer of size [nbits]) with the other
   participant.  Return two lists of shared Booleans, one with
   the shares of participant #1's secret, the other with
   the shares of participant #2's secret. *)

let rec share_bits nbits n =
  if nbits <= 0 then ([], []) else begin
    let (a, b) = share (n land 1 = 1) in
    let (al, bl) = share_bits (nbits - 1) (n lsr 1) in
    (a :: al, b :: bl)
  end

(* Yao's problem.  Each participant shares its secret wealth
   and learns who is the wealthier. *)

let yao's_problem my_wealth =
  let (al, bl) = share_bits 40 my_wealth in
  Multiparty.log "Shared my secret wealth %d\n" my_wealth;
  let res = reveal (comparator al bl true_) in
  Multiparty.log "Participant #%d is wealthier\n" (if res then 1 else 2)

let _ =
  if Multiparty.num_participants() < 3
  || Array.length Sys.argv <> 3 then begin
      if Multiparty.self() = 0 then
        printf "Usage: mpirun -np 3 ./Millionaires_GMW.exe <wealth 1> <wealth 2>\n";
      exit 2
  end;
  let wealth1 = int_of_string Sys.argv.(1)
  and wealth2 = int_of_string Sys.argv.(2) in
  begin match Multiparty.self() with
  | 1 -> yao's_problem wealth1
  | 2 -> yao's_problem wealth2
  | _ -> ()
  end;
  Multiparty.barrier()