main.go 7.87 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
39
// EncodeBloodType return x as a slice containing the binary representation.
func EncodeBloodType(x, bits 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 := bits - 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
46
47
48
	}
	return output
}

49
type Party struct {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
50
	stack []bool
51
52
53
54
55

	in  chan bool
	out chan bool
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
56
func InitParty(in, out chan bool) *Party {
57
	return &Party{
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
58
59
60
		stack: make([]bool, 0),
		in:    in,
		out:   out,
61
62
63
	}
}
func (a *Party) Input(x bool) int {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
64
	xb := rand.Intn(2) == 1
65
66
	xa := x != xb // x XOR xb

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
67
	a.stack = append(a.stack, xa)
68
	a.out <- xb //Send to other party
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
69
	return len(a.stack) - 1
70
71
72
}

func (a *Party) Receive() int {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
73
74
	a.stack = append(a.stack, <-a.in)
	return len(a.stack) - 1
75
76
77
}

func (a *Party) Send(wire int) {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
78
	a.out <- a.stack[wire]
79
80
}

Thomas Hoffmann's avatar
Thomas Hoffmann committed
81
func (a *Party) Combine(xwire, ywire int) int {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
82
83
	a.stack = append(a.stack, a.stack[xwire] && a.stack[ywire])
	return len(a.stack) - 1
84
85
86
}

func (a *Party) XORC(xwire int, c bool, mode bool) int {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
87
	var xa = a.stack[xwire]
88
	if mode { //Only one party is supposed to do the XOR
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
89
		a.stack = append(a.stack, xa != c)
90
	} else {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
91
		a.stack = append(a.stack, xa)
92
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
93
	return len(a.stack) - 1
94
95
}
func (a *Party) ANDC(xwire int, c bool) int {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
96
97
98
	var xa = a.stack[xwire]
	a.stack = append(a.stack, xa && c)
	return len(a.stack) - 1
99
100
101
}

func (a *Party) XOR2W(xwire, ywire int) int {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
102
103
104
	var xa, xb = a.stack[xwire], a.stack[ywire]
	a.stack = append(a.stack, xa != xb)
	return len(a.stack) - 1
Thomas Hoffmann's avatar
Thomas Hoffmann committed
105
}
106

Thomas Hoffmann's avatar
Thomas Hoffmann committed
107
type Protocol struct {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
108
109
	A *Party
	B *Party
110
111
}

Thomas Hoffmann's avatar
Thomas Hoffmann committed
112
func (P *Protocol) AND(xwire, ywire int) int {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
113
	A, B := P.A, P.B
114
115
116
117
118
119
120
121
122
123
124
	//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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
	//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
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
157
158
	var idx_z1, _ = A.ANDC(xwire, A.stack[idx_e]), B.ANDC(xwire, B.stack[idx_e])
	var idx_z2, _ = A.ANDC(ywire, A.stack[idx_d]), B.ANDC(ywire, B.stack[idx_d])
Thomas Hoffmann's avatar
Thomas Hoffmann committed
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
	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 {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
192
193
194
	i := P.A.XORC(xwire, true, true)
	_ = P.B.XORC(xwire, true, false)
	return i
Thomas Hoffmann's avatar
Thomas Hoffmann committed
195
196
197
198
199
200
201
202
203
204
205
206
207
208
}

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
209
		output = append(output, A.stack[idx_outA])
Thomas Hoffmann's avatar
Thomas Hoffmann committed
210
211
212
213
	}
	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
214
		output = append(output, B.stack[idx_outB])
Thomas Hoffmann's avatar
Thomas Hoffmann committed
215
216
	}
	return output
217
218
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
219
func NewProtocol() *Protocol {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
220
221
222
	var a2b = make(chan bool, 1) //Directional non-blocking channels
	var b2a = make(chan bool, 1)
	return &Protocol{
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
223
224
		A: InitParty(b2a, a2b),
		B: InitParty(a2b, b2a),
Thomas Hoffmann's avatar
Thomas Hoffmann committed
225
226
	}
}
227

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
// 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
// blood type and y being Bob's blood type. The encodings must have length 3,
// where index 2 indiciates blood sign, index 1 indicates if bloods has A and
// index 0 indicates if blood have B.
//
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
247
	}
248

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
249
250
251
252
	//Input round
	idx_s, _ := P.Input(x[0], y[0])
	idx_A, _ := P.Input(x[1], y[1])
	idx_B, _ := P.Input(x[2], y[2])
253

Thomas Hoffmann's avatar
Thomas Hoffmann committed
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
	//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)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
274
	return output[0], nil
275
276
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
277
func RunProtocol(x, y int) (bool, error) {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
278
279
	protocol := NewProtocol()

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
280
281
	encodingX := EncodeBloodType(x, 3)
	encodingY := EncodeBloodType(y, 3)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
282
283
284
285

	return protocol.Run(encodingX, encodingY)
}

286
func main() {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
287
	bloodA, bloodB := BloodType_ABn, BloodType_ABp
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
288
	z, err := RunProtocol(bloodA, bloodB)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
289

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
290
291
292
	if err != nil {
		fmt.Println("Protocol failed: ", err)
	} else if z == BloodTable[bloodA][bloodB] {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
293
294
		fmt.Println("Protocol succeded")
	} else {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
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
}