Millionaires_SHE.ml

(** Yao's millionaires problem: comparing two encrypted integers
    using Somewhat Homomorphic Encryption. *)

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

open SHE

(* Full adder *)

let full_adder a b c =
  (hxor a (hxor b c),
   hxor (hand a b) (hxor (hand a c) (hand b c)))

(* Comparator *)

let rec compare al bl c =
  match al, bl with
  | [], [] -> c
  | a :: al, b :: bl ->
      let (_, c') = full_adder a (hnot b) c in compare al bl c'
  | _, _ -> assert false

(* Decompose an integer in [n] bits *)

let rec bits_of_int n i =
  if n = 0 then [] else (i land 1 = 1) :: bits_of_int (n - 1) (i lsr 1)

open Printf

(* Compare the two integers given on the command line *)

let usage () =
  printf "Usage: ./Millionaires_SHE.exe <32-bit number> <32-bit number>\n";
  exit 2

let _ =
  if Array.length Sys.argv <> 3 then usage();
  let a = int_of_string Sys.argv.(1)
  and b = int_of_string Sys.argv.(2) in
  if not (a >= 0 && a < 1 lsl 32 && b >= 0 && b < 1 lsl 32) then usage();
  let p = keygen() in
  let res =
    compare (List.map (encrypt p) (bits_of_int 32 a))
            (List.map (encrypt p) (bits_of_int 32 b))
            (const true) in
  printf "Noise level: %d.  Max allowed level is %d.\n"
         (noise p res) max_noise;
  let r = decrypt p res in
  printf "%d >= %d: %B\n" a b r