circuit.go 6.96 KB
Newer Older
Thomas Hoffmann's avatar
Thomas Hoffmann committed
1
2
3
package garbled

import (
Thomas Hoffmann's avatar
Thomas Hoffmann committed
4
	"bytes"
5
	cryptoUtil "crycomp/internal/crypto/util"
Thomas Hoffmann's avatar
Thomas Hoffmann committed
6
	"crycomp/internal/util"
Thomas Hoffmann's avatar
Thomas Hoffmann committed
7
	"crypto/rand"
8
9
	"crypto/sha256"
	"errors"
Thomas Hoffmann's avatar
Thomas Hoffmann committed
10
	"fmt"
Thomas Hoffmann's avatar
Thomas Hoffmann committed
11
12
)

13
// Table contains the random or encoded strings of bit-length k.
Thomas Hoffmann's avatar
Thomas Hoffmann committed
14
type Table struct {
15
	// data contains the raw byte data this table holds.
Thomas Hoffmann's avatar
Thomas Hoffmann committed
16
	data []byte
17
18
19
20
21
22
23
24
	// rows is the number of rows in data (not length).
	// Normally this is the numbe of wires the table was created for.
	rows int
	// cols is the number of strings in each row. E.g the two input
	// keys (K_0^i, K_1^i)
	cols int
	// valueLen contains the string length (of each value). This is always k/8.
	valueLen int
Thomas Hoffmann's avatar
Thomas Hoffmann committed
25
26
}

27
28
29
30
31
// NewTable returns a new garbled table with n rows and each row containing numValues columns.
// Each value contains k/8 bytes. k must be a multiple of 8.
func NewTable(n, numValues, k int) (t *Table, err error) {
	if k%8 != 0 {
		return nil, errors.New("k must be multiple of 8")
Thomas Hoffmann's avatar
Thomas Hoffmann committed
32
	}
33
34
35
36
37
38
39
	t = &Table{
		data:     make([]byte, n*numValues*k/8),
		rows:     n,
		cols:     numValues,
		valueLen: k / 8,
	}
	return
Thomas Hoffmann's avatar
Thomas Hoffmann committed
40
41
}

42
43
44
// index returns the data index for row i and column j.
func (t *Table) index(r, c int) int {
	return r*t.cols*t.valueLen + c*t.valueLen
Thomas Hoffmann's avatar
Thomas Hoffmann committed
45
46
}

47
48
49
50
51
52
53
54
55
56
57
58
59
60
// // SetValue sets the byte string value at row i and column j.
// func (t *Table) SetValue(r, c int, data []byte) error {
// 	if len(data) != t.valueLen {
// 		return errors.New("data have invalid length")
// 	}
// 	index := t.index(r, c)
// 	copy(t.data[index:index+t.valueLen], data)
// 	return nil
// }

// GetValue returns a byte slice containing the value at row i and column j.
func (t *Table) GetValue(r, c int) []byte {
	index := t.index(r, c)
	return t.data[index : index+t.valueLen]
Thomas Hoffmann's avatar
Thomas Hoffmann committed
61
62
}

63
64
65
func (t *Table) SetRow(r int, data []byte) {
	if len(data) != t.cols*t.valueLen {
		panic("data have invalid length")
Thomas Hoffmann's avatar
Thomas Hoffmann committed
66
	}
67
68
	index := t.index(r, 0)
	copy(t.data[index:index+t.cols*t.valueLen], data)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
69
70
}

71
72
73
func (t *Table) GetRow(r int) []byte {
	index := t.index(r, 0)
	return t.data[index : index+t.cols*t.valueLen]
Thomas Hoffmann's avatar
Thomas Hoffmann committed
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
// func (t *Table) SetValueOld(data []byte, i, s int) {
// 	valStart := i*t.valueLen + s*t.valueLen
// 	copy(t.data[valStart:valStart+t.valueLen], data)
// }

// func (t *Table) GetValueOld(i, s int) []byte {
// 	valStart := i*t.valueLen + s*t.valueLen
// 	return t.data[valStart : valStart+t.valueLen]
// }

// func (t *Table) SetRowOld(data [][]byte, i int) {
// 	for j, val := range data {
// 		t.SetValueOld(val, i, j)
// 	}
// }

// func (t *Table) GetRowOld(i int) [][]byte {
// 	values := make([][]byte, 0)
// 	for j := 0; j < t.cols; j++ {
// 		values = append(values, t.GetValueOld(i, j))
// 	}
// 	return values
// }

Thomas Hoffmann's avatar
Thomas Hoffmann committed
100
func (t *Table) getKFirstValues(numInputWire int) [][][]byte {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
101
102
	values := make([][][]byte, 0)
	for i := 0; i < numInputWire; i++ {
103
		// values = append(values, t.GetRowOld(i))
Thomas Hoffmann's avatar
Thomas Hoffmann committed
104
105
106
107
	}
	return values
}

Thomas Hoffmann's avatar
Thomas Hoffmann committed
108
func (t *Table) randomizeTable() {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
109
110
111
112
113
114
115
116
117
	rand.Read(t.data)
}

type GCircuit struct {
	F *Table
	E [][][]byte
	D [][]byte
}

118
119
120
121
122
123
type Protocol struct {
	G func(a, b []byte, i int) []byte
}

func NewGarbBloodCircuit() (c *GCircuit, err error) {
	p := Protocol{G}
Thomas Hoffmann's avatar
Thomas Hoffmann committed
124
125

	numInput := 6
126
	numWires := 11 // Includes numInput
Thomas Hoffmann's avatar
Thomas Hoffmann committed
127
	k_bits := 128
128
129
130
131
132
133

	// 1. Create two random strings for each wire.
	K, err := NewTable(numWires, 2, k_bits)
	if err != nil {
		return
	}
Thomas Hoffmann's avatar
Thomas Hoffmann committed
134
	K.randomizeTable()
Thomas Hoffmann's avatar
Thomas Hoffmann committed
135

136
137
138
139
	// 2. Create a garbled table for all C values (4 for each gate)
	C, err := NewTable(numWires-numInput, 4, k_bits*2)
	if err != nil {
		return
Thomas Hoffmann's avatar
Thomas Hoffmann committed
140
141
	}

142
143
144
145
146
147
148
149
150
151
152
153
	// // 1st layer are OR-gates with b input being NOT
	C.SetRow(0, p.garbleGate(K, 0, 3, 6, ORGateWithNot))
	C.SetRow(1, p.garbleGate(K, 1, 4, 7, ORGateWithNot))
	C.SetRow(2, p.garbleGate(K, 2, 5, 8, ORGateWithNot))

	C.SetRow(3, p.garbleGate(K, 6, 7, 9, ANDGate))
	C.SetRow(4, p.garbleGate(K, 8, 9, 10, ANDGate))

	c = &GCircuit{
		F: C,
		E: K.getKFirstValues(numInput),
		// D: K.GetRowOld(numWires),
Thomas Hoffmann's avatar
Thomas Hoffmann committed
154
	}
155
	return
Thomas Hoffmann's avatar
Thomas Hoffmann committed
156
}
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

//Creates a row (C_0^i, C_1^i, C_2^i ,C_3^i) for the garbled table, where
func (p *Protocol) garbleGate(K *Table, Li, Ri, out int, c func(a, b int) int) (cRow []byte) {
	cRow = make([]byte, K.valueLen*4)
	// Random permutation
	perm := cryptoUtil.Perm(4)

	// for (a,b) in {0,1} x {0,1}
	for a := 0; a <= 1; a++ {
		for b := 0; b <= 1; b++ {
			left := p.G(K.GetValue(Li, a), K.GetValue(Ri, b), out)
			right := make([]byte, K.valueLen*2)
			copy(right[:K.valueLen], K.GetValue(out, c(a, b)))
			// right = append(right, make([]byte, 16)...)

			// The index to write this value to. This depends in the row permutation.
			rowI := perm[a*2+b] * K.valueLen

			util.XOR(left, left, right) // XOR with left as destination.
			copy(cRow[rowI:rowI+K.valueLen], left)
			// cRow[rowI : rowI+K.valueLen] =
			// cVals[a*2+b] = util.XOR(left, right)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
179
180
181
182
183
		}
	}
	return
}

184
185
func G(A, B []byte, i int) []byte {
	hash := sha256.New()
Thomas Hoffmann's avatar
Thomas Hoffmann committed
186
	hash.Write(A)
187
	hash.Write(append(B, byte(i)))
Thomas Hoffmann's avatar
Thomas Hoffmann committed
188
189
190
	return hash.Sum(nil)
}

191
func Enc(e [][][]byte, x []bool) (X [][]byte) {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
192
193
194
195
196
197
198
199
200
201
202
	X = make([][]byte, 0)
	for i, val := range x {
		if val {
			X = append(X, e[i][1])
		} else {
			X = append(X, e[i][0])
		}
	}
	return
}

203
func Eval(C *Table, X [][]byte) ([]byte, error) {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
204
205
206
	var K = X
	var res []byte
	for i := 0; i < 3; i++ {
207
208
209
		for j := 0; j < 4; j++ {
			// res = util.XOR(G(K[i], K[i+3], i), C.GetValueOld(i, j))
			if bytes.Equal(res[16:], make([]byte, 16)) {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
210
211
212
213
				K = append(K, res[:16])
				break
			}
		}
Thomas Hoffmann's avatar
Thomas Hoffmann committed
214
		return nil, fmt.Errorf("Aborted while evaluating the garbled circuit, no match was found")
Thomas Hoffmann's avatar
Thomas Hoffmann committed
215
	}
Thomas Hoffmann's avatar
Thomas Hoffmann committed
216
	return K[len(K)-1], nil
Thomas Hoffmann's avatar
Thomas Hoffmann committed
217
218
219
}

func Decode(d [][]byte, Z []byte) bool {
220
	if bytes.Equal(d[0], Z) {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
221
		return false
222
	} else if bytes.Equal(d[1], Z) {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
223
224
225
226
		return true
	}
	//TODO: Error handling
	return false
Thomas Hoffmann's avatar
Thomas Hoffmann committed
227
228
229
230
231
232
233
}

////////////////////////////////////////////////////////////////
// Circuit
////////////////////////////////////////////////////////////////

type Circuit struct {
234
235
	wires      []int
	gates      []Gate
Thomas Hoffmann's avatar
Thomas Hoffmann committed
236
	outputWire int
237
	numInput   int
Thomas Hoffmann's avatar
Thomas Hoffmann committed
238
239
240
241
}

func NewCircuit(numInput int) *Circuit {
	return &Circuit{
242
243
244
		wires:    make([]int, numInput),
		gates:    make([]Gate, 0),
		numInput: numInput,
Thomas Hoffmann's avatar
Thomas Hoffmann committed
245
246
247
248
	}
}

func (c *Circuit) getInputWires(i int) (Li, Ri int) {
249
	return i, c.numInput + i
Thomas Hoffmann's avatar
Thomas Hoffmann committed
250
251
}

252
func (c *Circuit) AddGate(Li, Ri int, f func(a, b int) int) *Gate {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
253
	c.wires = append(c.wires, 0)
254
	g := newGate(Li, Ri, len(c.wires)-1, f)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
255
256
257
	c.gates = append(c.gates, *g)
	return g
}
258

Thomas Hoffmann's avatar
Thomas Hoffmann committed
259
type Gate struct {
260
261
262
	Li, Ri    int
	i         int
	truthfunc func(a, b int) int
Thomas Hoffmann's avatar
Thomas Hoffmann committed
263
264
}

265
func newGate(Li, Ri, i int, f func(a, b int) int) (g *Gate) {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
	g.Li = Li
	g.Ri = Ri
	g.i = i
	g.truthfunc = f
	return
}

////////////////////////////////////////////////////////////////
// GATES
////////////////////////////////////////////////////////////////

func ORGate(a, b int) int {
	if a+b != 0 {
		return 1
	} else {
		return 0
	}
}

285
286
func ORGateWithNot(a, b int) int {
	if ((1 - b) + a) == 0 {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
287
288
289
290
291
292
		return 0
	} else {
		return 1
	}
}

293
294
func ANDGate(a, b int) int {
	return a * b
Thomas Hoffmann's avatar
Thomas Hoffmann committed
295
}