main.go 7.81 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
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
	"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
)

// 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},
}

// Params contains the global protocol paramteres that are shared between Dealer, Alice and Bob.
type Params struct {
	n    int
	nPow int // pow(2, n)
}

// NewParams returns a new Params struct with n and precomputed 2^n (pow(2, n)).
func NewParams(n int) *Params {
	return &Params{
		n:    n,
		nPow: int(math.Pow(2, float64(n))),
	}
}

// mod computes the modulo a%n but handles negative arguments correctly.
func mod(a, n int) int {
	return (a%n + n) % n
}

55
56
57
58
59
60
61
62
63
64
func Int2Bools(x, bits int) []bool {
	var output = make([]bool,0)
	var tmp = 0
	for i := bits-1; i >= 0; i-- {
		tmp = int(math.Exp2(float64(i)))
		output = append(output,(x & tmp) / tmp == 1)
	}
	return output
}

65
type Party struct {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
66
67
	rand *rand.Rand
	vals []bool
68
69
70
71
72
73
74

	in  chan bool
	out chan bool
}

func InitParty(rand *rand.Rand, in, out chan bool) *Party {
	return &Party{
Thomas Hoffmann's avatar
Thomas Hoffmann committed
75
76
77
78
		rand: rand,
		vals: make([]bool, 0),
		in:   in,
		out:  out,
79
80
81
82
83
84
	}
}
func (a *Party) Input(x bool) int {
	xb := a.rand.Intn(2) == 1
	xa := x != xb // x XOR xb

Thomas Hoffmann's avatar
Thomas Hoffmann committed
85
	a.vals = append(a.vals, xa)
86
	a.out <- xb //Send to other party
Thomas Hoffmann's avatar
Thomas Hoffmann committed
87
	return len(a.vals) - 1
88
89
90
}

func (a *Party) Receive() int {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
91
92
	a.vals = append(a.vals, <-a.in)
	return len(a.vals) - 1
93
94
95
}

func (a *Party) Send(wire int) {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
96
	a.out <- a.vals[wire]
97
98
}

Thomas Hoffmann's avatar
Thomas Hoffmann committed
99
100
101
func (a *Party) Combine(xwire, ywire int) int {
	a.vals = append(a.vals, a.vals[xwire] && a.vals[ywire])
	return len(a.vals) - 1
102
103
104
}

func (a *Party) XORC(xwire int, c bool, mode bool) int {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
105
	var xa = a.vals[xwire]
106
	if mode { //Only one party is supposed to do the XOR
Thomas Hoffmann's avatar
Thomas Hoffmann committed
107
		a.vals = append(a.vals, xa != c)
108
	} else {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
109
		a.vals = append(a.vals, xa)
110
	}
Thomas Hoffmann's avatar
Thomas Hoffmann committed
111
	return len(a.vals) - 1
112
113
}
func (a *Party) ANDC(xwire int, c bool) int {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
114
115
116
	var xa = a.vals[xwire]
	a.vals = append(a.vals, xa && c)
	return len(a.vals) - 1
117
118
119
}

func (a *Party) XOR2W(xwire, ywire int) int {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
120
121
122
123
	var xa, xb = a.vals[xwire], a.vals[ywire]
	a.vals = append(a.vals, xa != xb)
	return len(a.vals) - 1
}
124

Thomas Hoffmann's avatar
Thomas Hoffmann committed
125
126
127
type Protocol struct {
	rand *rand.Rand
	A, B *Party
128
129
}

Thomas Hoffmann's avatar
Thomas Hoffmann committed
130
131
func (P *Protocol) AND(xwire, ywire int) int {
	var rand, A, B = P.rand, 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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
	//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]
	var idx_d1, _ = A.XOR2W(xwire, idx_u), B.XOR2W(xwire, idx_u)

	//3. compute [e] = [y] XOR [v]
	var idx_e1, _ = A.XOR2W(ywire, idx_v), B.XOR2W(ywire, idx_v)

	//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
	var idx_d, _ = A.XOR2W(idx_d1, idx_d2), B.XOR2W(idx_d1, idx_d2)
	var idx_e, _ = A.XOR2W(idx_e1, idx_e2), B.XOR2W(idx_e1, idx_e2)

	//6b. Compute [z]-parts
	var idx_z1, _ = A.ANDC(xwire, A.vals[idx_e]), B.ANDC(xwire, B.vals[idx_e])
	var idx_z2, _ = A.ANDC(ywire, A.vals[idx_d]), B.ANDC(ywire, B.vals[idx_d])
	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)
	var idx_z, _ = A.XOR2W(idx_z5, idx_z3), B.XOR2W(idx_z5, idx_z3)
	return idx_z
}

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
}

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

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)
		output = append(output, A.vals[idx_outA])
	}
	if B_Learns {
		var idx_B = A.Receive()
		var idx_outB = A.XOR2W(wire, idx_B)
		output = append(output, B.vals[idx_outB])
	}
	return output
234
235
}

Thomas Hoffmann's avatar
Thomas Hoffmann committed
236
237
238
239
240
241
242
243
244
245
func InitProtocol(seed int64) *Protocol {
	var rand = rand.New(rand.NewSource(seed))
	var a2b = make(chan bool, 1) //Directional non-blocking channels
	var b2a = make(chan bool, 1)
	return &Protocol{
		rand: rand,
		A:    InitParty(rand, b2a, a2b),
		B:    InitParty(rand, a2b, b2a),
	}
}
246

Thomas Hoffmann's avatar
Thomas Hoffmann committed
247
248
249
func (P *Protocol) RunProtocol(x, y []bool) bool {
	//alice := P.A
	//bob := P.B
250

Thomas Hoffmann's avatar
Thomas Hoffmann committed
251
252
253
	if len(x) != len(y) {
		return false
	}
254
	//Input round
Thomas Hoffmann's avatar
Thomas Hoffmann committed
255
256
257
	var idx_s, _ = P.Input(x[0], y[0])
	var idx_A, _ = P.Input(x[1], y[1])
	var idx_B, _ = P.Input(x[2], y[2])
258

Thomas Hoffmann's avatar
Thomas Hoffmann committed
259
260
261
	//Compute f(x,y) = (x_sign 	OR NOT y_sign) 	AND
	// (x_A 	OR NOT y_A) 	AND
	// (x_B 	OR NOT y_B)
262

Thomas Hoffmann's avatar
Thomas Hoffmann committed
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
	//a. Compute (x_sign OR NOT y_sign) = NOT (NOT x_sign AND y_sign)
	//var idx_f1 = alice.XORC(idx_s, true , true) //compute NOT x_sign
	var idx_f1 = P.NOT(idx_s)
	idx_f1 = P.AND(idx_f1, idx_s) // NOT x_sign AND y_sign
	idx_f1 = P.NOT(idx_f1)        //NOT (NOT x_sign AND y_sign)

	//b. Compute (x_A OR NOT y_A) = NOT (NOT x_A AND y_A)
	var idx_f2 = P.NOT(idx_A)     //compute NOT x_A
	idx_f2 = P.AND(idx_f2, idx_A) // NOT x_A AND y_A
	idx_f2 = P.NOT(idx_f2)        //NOT (NOT x_A AND y_A)

	//c. Compute (x_B OR NOT y_B) = NOT (NOT x_B AND y_B)
	var idx_f3 = P.NOT(idx_B)     //compute NOT x_B
	idx_f3 = P.AND(idx_f3, idx_B) // NOT x_B AND y_B
	idx_f3 = P.NOT(idx_f3)        //NOT (NOT x_B AND y_B)

	//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)
	return output[0]
284
285
286
}

func main() {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
287
	var p = InitProtocol(1)
288
289
	var bloodA, BloodB = BloodType_ABn, BloodType_ABp
	x, y := Int2Bools(bloodA,3), Int2Bools(BloodB,3)//[]bool{false, false, false}, []bool{true, true, true}
Thomas Hoffmann's avatar
Thomas Hoffmann committed
290
	z := p.RunProtocol(x, y)
291
	if z == BloodTable[bloodA][BloodB] {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
292
293
294
		fmt.Println("Protocol succeded")
		fmt.Println(z)
	} else {
295
		fmt.Printf("Protocol failed, output was %t, but should be %t", z, BloodTable[bloodA][BloodB])
Thomas Hoffmann's avatar
Thomas Hoffmann committed
296
	}
297
}
Thomas Hoffmann's avatar
Thomas Hoffmann committed
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313

// 0 - 0 - 1
// 0 - 1 - 0
// 1 - 0 - 1
// 1 - 1 - 1

// 0 - 0 - 1
// 0 - 1 - 0
// 1 - 0 - 1
// 1 - 1 - 1

// NOT (NOT x AND Y)
// 0 - 0 - 0
// 0 - 1 - 1
// 1 - 0 - 0
// 1 - 1 - 0