secure-computing/lib/GMW.ml at main · xavierleroy/secure-computing · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
(** MPC with two participants and Boolean gates,
    following Goldreich, Micali, Wigderson 1987 *)

(* Copyright Xavier Leroy.
   License: LGPL 2.1 or later with OCaml LGPL Linking Exception *)

open Printf

type value = bool
type share = bool

let rng =
  Cryptokit.Random.(pseudo_rng (string secure_rng 32))

let random_bool () =
  let s = Cryptokit.Random.(string rng 1) in
  (String.get_uint8 s 0) land 1 = 1

(* Sharings of [false] and [true].
   [ [false] ] is [ false, false ].
   [ [true]  ] is [ true,  false ]. *)

let false_ = false

let true_ = Multiparty.self() = 1

(* Local Boolean operations *)

let xor (x: bool) (y: bool) =
  x <> y

let not (x: bool) =
  xor x true_

(* Participant 0 sends a sharing of [b] to participants 1 and 2 *)

let send (b: bool) =
  match Multiparty.self() with
  | 0 ->
      let m = random_bool() in
      Multiparty.send 1 m;
      Multiparty.send 2 (xor b m)
  | _ ->
      assert false

(* Participants 1 and 2 receive a share from participant 0 *)

let receive () : bool =
  match Multiparty.self() with
  | 1 | 2 ->
      (Multiparty.receive 0 : bool)
  | _ ->
      assert false

(* Participant 1 shares b1 with participant 2,
   while participant 2 shares b2 with participant 1.
   The return value is a pair (share of b1, share of b2). *)

let share (b: bool) : bool * bool =
  let m = random_bool() in
  match Multiparty.self() with
  | 1 ->
      Multiparty.send 2 m;
      let b' : bool = Multiparty.receive 2 in
      (xor b m, b')
  | 2 ->
      let b' : bool = Multiparty.receive 1 in
      Multiparty.send 1 m;
      (b', xor b m)
  | _ ->
      assert false

(* Participants 1 and 2 put their shares of [b] in common,
   so that they both learn the value of [b]. *)

let reveal (b: bool) : bool =
  match Multiparty.self() with
  | 1 ->
      Multiparty.send 2 b;
      let b' = Multiparty.receive 2 in
      xor b b'
  | 2 ->
      let b' = Multiparty.receive 1 in
      Multiparty.send 1 b;
      xor b b'
  | _ ->
      assert false

(* Non-linear gates *)

let line (x: bool) (y: bool) =
  (if x then 1 else 0) + (if y then 2 else 0)

let get_line truth_table (x: bool) (y: bool) =
  truth_table.(line x y)

let gate truth_table (x: bool) (y: bool) =
  match Multiparty.self() with
  | 1 ->
      let z = random_bool () in
      (* Provide all possible values of z' as a function of x' and y' *)
      OT4.provide_bool ~requester:2
        (* x' = 0 y' = 0 *) (xor z (get_line truth_table x y))
        (* x' = 1 y' = 0 *) (xor z (get_line truth_table (not x) y))
        (* x' = 0 y' = 1 *) (xor z (get_line truth_table x (not y)))
        (* x' = 1 y' = 1 *) (xor z (get_line truth_table (not x) (not y)));
      (* Our share of the result is z *)
      z
  | 2 ->
      OT4.request_bool ~provider:1 (line x y)
  | _ ->
      assert false

let and_ = gate [| false; false; false; true |]
let or_  = gate [| false; true; true; true |]
let nand = gate [| true; true; true; false |]
let nor  = gate [| true; false; false; false |]