main.go 8.15 KB
Newer Older
1
2
3
package main

import (
Thomas Hoffmann's avatar
Thomas Hoffmann committed
4
	"fmt"
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
	"math"
	"math/rand"
)

// Enumeration of blood types. The 'n'-suffix means negative and 'p'-suffix means positive.
const (
	BloodType_On  = 0
	BloodType_Op  = 1
	BloodType_An  = 2
	BloodType_Ap  = 3
	BloodType_Bn  = 4
	BloodType_Bp  = 5
	BloodType_ABn = 6
	BloodType_ABp = 7
)

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
21
22
var BloodNames []string = []string{"O-", "O+", "A-", "A+", "B-", "B+", "AB-", "AB+"}

23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// BloodTable contains the blood type compatibility truth table. Rows are the
// recipient's blood type and the columns are the donor's blood type.
//
// The table contains bools, since we compute a boolean function. Duh!
var BloodTable = [][]bool{
	{true, false, false, false, false, false, false, false},
	{true, true, false, false, false, false, false, false},
	{true, false, true, false, false, false, false, false},
	{true, true, true, true, false, false, false, false},
	{true, false, false, false, true, false, false, false},
	{true, true, false, false, true, true, false, false},
	{true, false, true, false, true, false, true, false},
	{true, true, true, true, true, true, true, true},
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
38
// Int2Bools return x as a slice containing the binary representation.
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
39
func Int2Bools(x, n int) []bool {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
40
41
	output := make([]bool, 0)
	tmp := 0
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
42
	for i := n - 1; i >= 0; i-- {
43
		tmp = int(math.Exp2(float64(i)))
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
44
		output = append(output, (x&tmp)/tmp == 1)
45
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
46
47
48
49
50
51
52
53

	// Reverse: Needed in protocol
	for i := 0; i < n/2; i++ {
		temp := output[i]
		output[i] = output[n-i-1]
		output[n-i-1] = temp
	}

54
55
56
	return output
}

57
type Party struct {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
58
	wires []bool
59
60
61
62
63

	in  chan bool
	out chan bool
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
64
func NewParty(in, out chan bool) *Party {
65
	return &Party{
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
66
		wires: make([]bool, 0),
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
67
68
		in:    in,
		out:   out,
69
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
70

71
}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
72
73
74
75
76
77
78

// Push v to the wires and return the index of the pushed value.
func (p *Party) Push(v bool) int {
	p.wires = append(p.wires, v)
	return len(p.wires) - 1
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
79
// Input samples a random value xb, computes xa = x XOR xb and sends xb to the
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
80
// other party.
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
81
func (p *Party) Input(x bool) int {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
82
	xb := rand.Intn(2) == 1
83
84
	xa := x != xb // x XOR xb

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
85
86
	p.out <- xb //Send to other party
	return p.Push(xa)
87
88
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
89
func (p *Party) Receive() int {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
90
	return p.Push(<-p.in)
91
92
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
93
94
func (p *Party) Send(wire int) {
	p.out <- p.wires[wire]
95
96
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
97
98
func (p *Party) Combine(xwire, ywire int) int {
	return p.Push(p.wires[xwire] && p.wires[ywire])
99
100
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
101
func (p *Party) XORC(xwire int, c bool, mode bool) int {
102
	if mode { //Only one party is supposed to do the XOR
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
103
		return p.Push(p.wires[xwire] != c)
104
	} else {
105
		return p.Push(p.wires[xwire])
106
107
	}
}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
108
109
func (p *Party) ANDC(xwire int, c bool) int {
	return p.Push(p.wires[xwire] && c)
110
111
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
112
113
func (p *Party) XOR2W(xwire, ywire int) int {
	return p.Push(p.wires[xwire] != p.wires[ywire])
Thomas Hoffmann's avatar
Thomas Hoffmann committed
114
}
115

Anders Jensen Løvig's avatar
Dealer    
Anders Jensen Løvig committed
116
type Dealer struct {
117
118
}

Anders Jensen Løvig's avatar
Dealer    
Anders Jensen Løvig committed
119
120
func NewDealer() *Dealer {
	return &Dealer{}
121
122
}

Anders Jensen Løvig's avatar
Dealer    
Anders Jensen Løvig committed
123
func (d *Dealer) Deal() (bool, bool, bool, bool, bool, bool) {
124
125
126
127
128
129
130
131
132
133
	u := rand.Intn(2) == 1
	ua := rand.Intn(2) == 1
	ub := u != ua // x XOR xb
	v := rand.Intn(2) == 1
	va := rand.Intn(2) == 1
	vb := v != va // x XOR xb
	w := u && v
	wa := rand.Intn(2) == 1
	wb := w != wa

Anders Jensen Løvig's avatar
Dealer    
Anders Jensen Løvig committed
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
	return ua, ub, va, vb, wa, wb
}

type Protocol struct {
	A *Party
	B *Party

	Dealer *Dealer
}

func NewProtocol() *Protocol {
	a2b := make(chan bool, 1) //Directional non-blocking channels
	b2a := make(chan bool, 1)
	return &Protocol{
		A:      NewParty(b2a, a2b),
		B:      NewParty(a2b, b2a),
		Dealer: NewDealer(),
	}
}

func (p *Protocol) AND(xwire, ywire int) int {
	A, B := p.A, p.B
	//1a. Generate [u], [v] and [w]
	ua, ub, va, vb, wa, wb := p.Dealer.Deal()

Thomas Hoffmann's avatar
Thomas Hoffmann committed
159
160
161
	//1b. send shares to parties
	A.in <- ua
	B.in <- ub
162
	idx_u, _ := A.Receive(), B.Receive()
Thomas Hoffmann's avatar
Thomas Hoffmann committed
163
164
	A.in <- va
	B.in <- vb
165
	idx_v, _ := A.Receive(), B.Receive()
Thomas Hoffmann's avatar
Thomas Hoffmann committed
166
167
	A.in <- wa
	B.in <- wb
168
	idx_w, _ := A.Receive(), B.Receive()
Thomas Hoffmann's avatar
Thomas Hoffmann committed
169
170

	//2 compute [d] = [x] XOR [u]
Anders Jensen Løvig's avatar
Dealer    
Anders Jensen Løvig committed
171
	idx_d1 := p.XOR2W(xwire, idx_u) //A.XOR2W(xwire, idx_u), B.XOR2W(xwire, idx_u)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
172
173

	//3. compute [e] = [y] XOR [v]
Anders Jensen Løvig's avatar
Dealer    
Anders Jensen Løvig committed
174
	idx_e1 := p.XOR2W(ywire, idx_v) //A.XOR2W(ywire, idx_v), B.XOR2W(ywire, idx_v)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
175
176
177
178

	//4. Open d
	A.Send(idx_d1)
	B.Send(idx_d1)
179
	idx_d2, _ := A.Receive(), B.Receive()
Thomas Hoffmann's avatar
Thomas Hoffmann committed
180
181
182
183

	//5. Open e
	A.Send(idx_e1)
	B.Send(idx_e1)
184
	idx_e2, _ := A.Receive(), B.Receive()
Thomas Hoffmann's avatar
Thomas Hoffmann committed
185
186

	//6a. Compute d and e
Anders Jensen Løvig's avatar
Dealer    
Anders Jensen Løvig committed
187
188
	idx_d := p.XOR2W(idx_d1, idx_d2) //A.XOR2W(idx_d1, idx_d2), B.XOR2W(idx_d1, idx_d2)
	idx_e := p.XOR2W(idx_e1, idx_e2) //A.XOR2W(idx_e1, idx_e2), B.XOR2W(idx_e1, idx_e2)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
189
190

	//6b. Compute [z]-parts
191
192
193
	idx_z1, _ := A.ANDC(xwire, A.wires[idx_e]), B.ANDC(xwire, B.wires[idx_e])
	idx_z2, _ := A.ANDC(ywire, A.wires[idx_d]), B.ANDC(ywire, B.wires[idx_d])
	idx_z3, _ := A.Combine(idx_e, idx_d), B.Combine(idx_e, idx_d)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
194
195

	//6c. Compute [z]
196
197
198
	idx_z4, _ := A.XOR2W(idx_w, idx_z1), B.XOR2W(idx_w, idx_z1)
	idx_z5, _ := A.XOR2W(idx_z4, idx_z2), B.XOR2W(idx_z4, idx_z2)
	idx_z, _ := A.XORC(idx_z5, A.wires[idx_z3], true), B.XORC(idx_z5, B.wires[idx_z3], false)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
199
200
201
	return idx_z
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
202
// Input the x bit to
Thomas Hoffmann's avatar
Thomas Hoffmann committed
203
func (P *Protocol) Input(x, y bool) (int, int) {
204
	idx1 := P.A.Input(x)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
205
206
	P.B.Receive()
	P.B.Input(y)
207
	idx2 := P.A.Receive()
Thomas Hoffmann's avatar
Thomas Hoffmann committed
208
209
210
211
	return idx1, idx2
}

func (P *Protocol) XORC(wire int, c bool) int {
212
	idx, _ := P.A.XORC(wire, c, true), P.B.XORC(wire, c, false)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
213
214
215
216
	return idx
}

func (P *Protocol) ANDC(wire int, c bool) int {
217
	idx, _ := P.A.ANDC(wire, c), P.B.ANDC(wire, c)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
218
219
220
221
	return idx
}

func (P *Protocol) XOR2W(xwire, ywire int) int {
222
	idx, _ := P.A.XOR2W(xwire, ywire), P.B.XOR2W(xwire, ywire)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
223
224
225
	return idx
}

Thomas Hoffmann's avatar
Thomas Hoffmann committed
226
227
//Only 1 share should be flipped
//NOT A == A XOR 1
Thomas Hoffmann's avatar
Thomas Hoffmann committed
228
func (P *Protocol) NOT(xwire int) int {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
229
230
231
	i := P.A.XORC(xwire, true, true)
	_ = P.B.XORC(xwire, true, false)
	return i
Thomas Hoffmann's avatar
Thomas Hoffmann committed
232
233
234
}

func (P *Protocol) Output(wire int, A_Learns, B_Learns bool) []bool {
235
236
	A, B := P.A, P.B
	output := make([]bool, 0)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
237
238
239
240
241
242
243
	if A_Learns {
		B.Send(wire)
	}
	if B_Learns {
		A.Send(wire)
	}
	if A_Learns {
244
245
		idx_A := A.Receive()
		idx_outA := A.XOR2W(wire, idx_A)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
246
		output = append(output, A.wires[idx_outA])
Thomas Hoffmann's avatar
Thomas Hoffmann committed
247
248
	}
	if B_Learns {
249
250
		idx_B := B.Receive()
		idx_outB := B.XOR2W(wire, idx_B)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
251
		output = append(output, B.wires[idx_outB])
Thomas Hoffmann's avatar
Thomas Hoffmann committed
252
253
	}
	return output
254
255
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
256
257
258
259
260
261
262
263
264
// Run the protocol for blood type compatibility using a passive secure BeDOZa
// protocol.
//
// The function computed is the following:
// 		f(x,y) = (x_sign OR NOT y_sign) AND
// 				 (x_A 	 OR NOT y_A)    AND
// 				 (x_B 	 OR NOT y_B)
//
// The inputs are the binary encoding of the blood types, with x being Alice's
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
265
266
267
268
269
// blood type and y being Bob's blood type. The encodings must have the form
//
// 		index 0: sign of blood type
//			  1: blood as A
//			  2: blood as B
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
270
271
272
273
274
275
276
//
func (P *Protocol) Run(x, y []bool) (bool, error) {
	if lenX := len(x); lenX != 3 {
		return false, fmt.Errorf("length of x-encoding must be 3, was %d", lenX)
	}
	if lenY := len(y); lenY != 3 {
		return false, fmt.Errorf("length of y-encoding must be 3, was %d", lenY)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
277
	}
278
279

	// Input Round
Thomas Hoffmann's avatar
Thomas Hoffmann committed
280
281
282
283
	idx_xS, idx_yS := P.Input(x[2], y[2])
	idx_xA, idx_yA := P.Input(x[1], y[1])
	idx_xB, idx_yB := P.Input(x[0], y[0])

284
285
	// 3 Rounds to compute (x OR not y)
	// Round 1: (OR Gate) Compute first NOT
Thomas Hoffmann's avatar
Thomas Hoffmann committed
286
287
288
289
	idx_1a := P.NOT(idx_xS)
	idx_1b := P.NOT(idx_xA)
	idx_1c := P.NOT(idx_xB)

290
291
292
293
	// Round 2: (OR Gate) Compute AND
	idx_2a := P.AND(idx_1a, idx_yS)
	idx_2b := P.AND(idx_1b, idx_yA)
	idx_2c := P.AND(idx_1c, idx_yB)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
294

295
	// Round 3: (OR Gate) Compute last NOT
Thomas Hoffmann's avatar
Thomas Hoffmann committed
296
297
298
299
	idx_3a := P.NOT(idx_2a)
	idx_3b := P.NOT(idx_2b)
	idx_3c := P.NOT(idx_2c)

300
301
302
	// 2 Rounds to compute ANDs (depend on eachother)
	// Round 4: Compute first AND
	idx_4 := P.AND(idx_3a, idx_3b)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
303

304
305
	// Round 5: Compute second AND
	idx_f := P.AND(idx_4, idx_3c)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
306

307
	// Output Round
Thomas Hoffmann's avatar
Thomas Hoffmann committed
308
	output := P.Output(idx_f, true, false)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
309
	return output[0], nil
310
311
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
312
func RunProtocol(x, y int) (bool, error) {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
313
314
315
316
	protocol := NewProtocol()

	encodingX := Int2Bools(x, 3)
	encodingY := Int2Bools(y, 3)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
317

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
318
319
320
	return protocol.Run(encodingX, encodingY)
}

321
func main() {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
322
	bloodA, bloodB := BloodType_ABn, BloodType_ABp
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
323
	z, err := RunProtocol(bloodA, bloodB)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
324

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
325
326
327
	if err != nil {
		fmt.Println("Protocol failed: ", err)
	} else if z == BloodTable[bloodA][bloodB] {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
328
329
		fmt.Println("Protocol succeded")
	} else {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
330
		fmt.Printf("Protocol failed, output was %t, but should be %t", z, BloodTable[bloodA][bloodB])
Thomas Hoffmann's avatar
Thomas Hoffmann committed
331
	}
332
}