main.go 8.06 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 {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
105
		return 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

Thomas Hoffmann's avatar
Thomas Hoffmann committed
116
type Protocol struct {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
117
118
	A *Party
	B *Party
119
120
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
121
122
123
124
125
126
127
func NewProtocol() *Protocol {
	var a2b = make(chan bool, 1) //Directional non-blocking channels
	var b2a = make(chan bool, 1)
	return &Protocol{
		A: NewParty(b2a, a2b),
		B: NewParty(a2b, b2a),
	}
128
129
}

Thomas Hoffmann's avatar
Thomas Hoffmann committed
130
func (P *Protocol) AND(xwire, ywire int) int {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
131
	A, B := P.A, P.B
132
133
134
135
136
137
138
139
140
141
142
	//1a. Generate [u], [v] and [w]
	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

Thomas Hoffmann's avatar
Thomas Hoffmann committed
143
144
145
146
147
148
149
150
151
152
153
154
	//1b. send shares to parties
	A.in <- ua
	B.in <- ub
	var idx_u, _ = A.Receive(), B.Receive()
	A.in <- va
	B.in <- vb
	var idx_v, _ = A.Receive(), B.Receive()
	A.in <- wa
	B.in <- wb
	var idx_w, _ = A.Receive(), B.Receive()

	//2 compute [d] = [x] XOR [u]
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
155
	var idx_d1 = P.XOR2W(xwire, idx_u) //A.XOR2W(xwire, idx_u), B.XOR2W(xwire, idx_u)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
156
157

	//3. compute [e] = [y] XOR [v]
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
158
	var idx_e1 = P.XOR2W(ywire, idx_v) //A.XOR2W(ywire, idx_v), B.XOR2W(ywire, idx_v)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
159
160
161
162
163
164
165
166
167
168
169
170

	//4. Open d
	A.Send(idx_d1)
	B.Send(idx_d1)
	var idx_d2, _ = A.Receive(), B.Receive()

	//5. Open e
	A.Send(idx_e1)
	B.Send(idx_e1)
	var idx_e2, _ = A.Receive(), B.Receive()

	//6a. Compute d and e
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
171
172
	var idx_d = P.XOR2W(idx_d1, idx_d2) //A.XOR2W(idx_d1, idx_d2), B.XOR2W(idx_d1, idx_d2)
	var 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
173
174

	//6b. Compute [z]-parts
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
175
176
	var idx_z1, _ = A.ANDC(xwire, A.wires[idx_e]), B.ANDC(xwire, B.wires[idx_e])
	var idx_z2, _ = A.ANDC(ywire, A.wires[idx_d]), B.ANDC(ywire, B.wires[idx_d])
Thomas Hoffmann's avatar
Thomas Hoffmann committed
177
178
179
180
181
	var idx_z3, _ = A.Combine(idx_e, idx_d), B.Combine(idx_e, idx_d)

	//6c. Compute [z]
	var idx_z4, _ = A.XOR2W(idx_w, idx_z1), B.XOR2W(idx_w, idx_z1)
	var idx_z5, _ = A.XOR2W(idx_z4, idx_z2), B.XOR2W(idx_z4, idx_z2)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
182
	var 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
183
184
185
	return idx_z
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
186
// Input the x bit to
Thomas Hoffmann's avatar
Thomas Hoffmann committed
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
func (P *Protocol) Input(x, y bool) (int, int) {
	var idx1 = P.A.Input(x)
	P.B.Receive()
	P.B.Input(y)
	var idx2 = P.A.Receive()
	return idx1, idx2
}

func (P *Protocol) XORC(wire int, c bool) int {
	var idx, _ = P.A.XORC(wire, c, true), P.B.XORC(wire, c, false)
	return idx
}

func (P *Protocol) ANDC(wire int, c bool) int {
	var idx, _ = P.A.ANDC(wire, c), P.B.ANDC(wire, c)
	return idx
}

func (P *Protocol) XOR2W(xwire, ywire int) int {
	var idx, _ = P.A.XOR2W(xwire, ywire), P.B.XOR2W(xwire, ywire)
	return idx
}

Thomas Hoffmann's avatar
Thomas Hoffmann committed
210
211
//Only 1 share should be flipped
//NOT A == A XOR 1
Thomas Hoffmann's avatar
Thomas Hoffmann committed
212
func (P *Protocol) NOT(xwire int) int {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
213
214
215
	i := P.A.XORC(xwire, true, true)
	_ = P.B.XORC(xwire, true, false)
	return i
Thomas Hoffmann's avatar
Thomas Hoffmann committed
216
217
218
219
220
221
222
223
224
225
226
227
228
229
}

func (P *Protocol) Output(wire int, A_Learns, B_Learns bool) []bool {
	var A, B = P.A, P.B
	var output = make([]bool, 0)
	if A_Learns {
		B.Send(wire)
	}
	if B_Learns {
		A.Send(wire)
	}
	if A_Learns {
		var idx_A = A.Receive()
		var idx_outA = A.XOR2W(wire, idx_A)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
230
		output = append(output, A.wires[idx_outA])
Thomas Hoffmann's avatar
Thomas Hoffmann committed
231
232
233
234
	}
	if B_Learns {
		var idx_B = A.Receive()
		var idx_outB = A.XOR2W(wire, idx_B)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
235
		output = append(output, B.wires[idx_outB])
Thomas Hoffmann's avatar
Thomas Hoffmann committed
236
237
	}
	return output
238
239
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
240
241
242
243
244
245
246
247
248
// 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
249
250
251
252
253
// 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
254
255
256
257
258
259
260
//
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
261
	}
262
	//Input round
Thomas Hoffmann's avatar
Thomas Hoffmann committed
263
	var idx_xS, idx_yS = P.Input(x[2], y[2])
Thomas Hoffmann's avatar
Thomas Hoffmann committed
264
	var idx_xA, idx_yA = P.Input(x[1], y[1])
Thomas Hoffmann's avatar
Thomas Hoffmann committed
265
	var idx_xB, idx_yB = P.Input(x[0], y[0])
266

Thomas Hoffmann's avatar
Thomas Hoffmann committed
267
	//a. Compute (x_sign OR NOT y_sign) = NOT (NOT x_sign AND y_sign)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
268
269
	var idx_f1 = P.NOT(idx_xS)
	idx_f1 = P.AND(idx_f1, idx_yS) // NOT x_sign AND y_sign
Thomas Hoffmann's avatar
Thomas Hoffmann committed
270
	idx_f1 = P.NOT(idx_f1)         //NOT (NOT x_sign AND y_sign)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
271
272

	//b. Compute (x_A OR NOT y_A) = NOT (NOT x_A AND y_A)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
273
274
	var idx_f2 = P.NOT(idx_xA)     //compute NOT x_A
	idx_f2 = P.AND(idx_f2, idx_yA) // NOT x_A AND y_A
Thomas Hoffmann's avatar
Thomas Hoffmann committed
275
	idx_f2 = P.NOT(idx_f2)         //NOT (NOT x_A AND y_A)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
276
277

	//c. Compute (x_B OR NOT y_B) = NOT (NOT x_B AND y_B)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
278
279
	var idx_f3 = P.NOT(idx_xB)     //compute NOT x_B
	idx_f3 = P.AND(idx_f3, idx_yB) // NOT x_B AND y_B
Thomas Hoffmann's avatar
Thomas Hoffmann committed
280
	idx_f3 = P.NOT(idx_f3)         //NOT (NOT x_B AND y_B)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
281
282
283
284
285

	//d. Compute f(x,y)
	var idx_f = P.AND(idx_f1, idx_f2)
	idx_f = P.AND(idx_f, idx_f3)
	var output = P.Output(idx_f, true, false)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
286
	return output[0], nil
287
288
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
289
func RunProtocol(x, y int) (bool, error) {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
290
291
292
293
	protocol := NewProtocol()

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

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
295
296
297
	return protocol.Run(encodingX, encodingY)
}

298
func main() {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
299
	bloodA, bloodB := BloodType_ABn, BloodType_ABp
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
300
	z, err := RunProtocol(bloodA, bloodB)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
301

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
302
303
304
	if err != nil {
		fmt.Println("Protocol failed: ", err)
	} else if z == BloodTable[bloodA][bloodB] {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
305
306
		fmt.Println("Protocol succeded")
	} else {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
307
		fmt.Printf("Protocol failed, output was %t, but should be %t", z, BloodTable[bloodA][bloodB])
Thomas Hoffmann's avatar
Thomas Hoffmann committed
308
	}
309
}