circuit.go 5.65 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"
7
	"crypto/sha256"
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
8
9
	"encoding/hex"
	"fmt"
Thomas Hoffmann's avatar
Thomas Hoffmann committed
10
11
)

Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
12
13
type Circuit struct {
	numInputs, numWires, k int
Thomas Hoffmann's avatar
Thomas Hoffmann committed
14

Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
15
	G func(a, b []byte, i int) []byte
Thomas Hoffmann's avatar
Thomas Hoffmann committed
16
17

	F *Table
18
19
	E []*Table
	D *Table
Thomas Hoffmann's avatar
Thomas Hoffmann committed
20
21
}

Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
22
23
24
25
26
27
28
29
30
func NewCircuit(numInputs, numWires, k int) (c *Circuit, err error) {
	F, err := NewTable(numWires-numInputs, 4, k*2)
	if err != nil {
		return
	}
	c = &Circuit{
		numInputs: numInputs,
		numWires:  numWires,
		k:         k,
31

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
32
		G: G,
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
33
34
35
36
		F: F,
	}
	return
}
37

Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
38
func (c *Circuit) GarbleBloodCircuit() (err error) {
39
	// 1. Create two random strings for each wire.
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
40
	kTable, err := NewTable(c.numWires, 2, c.k)
41
42
43
44
	if err != nil {
		return
	}
	err = kTable.randomizeTable()
45
46
47
	if err != nil {
		return
	}
Thomas Hoffmann's avatar
Thomas Hoffmann committed
48

Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
49
50
51
52
	// 2. Create a garbled table for all F values (4 for each gate)
	c.F.setRow(0, c.garbleGate(kTable, 0, 3, 6, ORGateWithNot))
	c.F.setRow(1, c.garbleGate(kTable, 1, 4, 7, ORGateWithNot))
	c.F.setRow(2, c.garbleGate(kTable, 2, 5, 8, ORGateWithNot))
53

Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
54
55
	c.F.setRow(3, c.garbleGate(kTable, 6, 7, 9, ANDGate))
	c.F.setRow(4, c.garbleGate(kTable, 8, 9, 10, ANDGate))
56

57
	// Create e
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
58
	c.E = make([]*Table, 2)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
59
60
	c.E[0], _ = NewTable(c.numInputs/2, 2, c.k)
	c.E[0].SetData(kTable.getRows(0, c.numInputs/2))
61

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
62
63
	c.E[1], _ = NewTable(c.numInputs/2, 2, c.k)
	c.E[1].SetData(kTable.getRows(c.numInputs/2, c.numInputs/2))
64
65

	// Create d
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
66
67
	c.D, _ = NewTable(1, 2, c.k)
	c.D.SetData(kTable.getRow(c.numWires - 1))
68

69
	return
Thomas Hoffmann's avatar
Thomas Hoffmann committed
70
}
71

72
73
// Encode x using the e table. If ey == true, we use the second
// half of e, otherwise first half
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
74
func Encode(e *Table, x []bool) (X []byte) {
75
76
77
	X = make([]byte, 0)
	for i, b := range x {
		if b {
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
78
			X = append(X, e.getValue(i, 1)...)
79
		} else {
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
80
			X = append(X, e.getValue(i, 0)...)
81
82
83
84
85
86
87
88
		}
	}
	if len(x)*e.valueLen != len(X) {
		panic("Wrong length of X")
	}
	return
}

89
//Creates a row (C_0^i, C_1^i, C_2^i ,C_3^i) for the garbled table, where
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
90
func (c *Circuit) garbleGate(K *Table, Li, Ri, out int, gateFun func(a, b int) int) []byte {
91
92
	cRow := make([]byte, K.valueLen*8) // because 4 values of double length
	perm := cryptoUtil.Perm(4)         // Random permutation
93
94
95
96

	// for (a,b) in {0,1} x {0,1}
	for a := 0; a <= 1; a++ {
		for b := 0; b <= 1; b++ {
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
97
			left := c.G(K.getValue(Li, a), K.getValue(Ri, b), out)
98
			right := make([]byte, K.valueLen*2)
99

Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
100
			copy(right[:K.valueLen], K.getValue(out, gateFun(a, b)))
101

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
102
103
104
			dst := util.XOR(left, right) // XOR with left as destination.
			fmt.Printf("%s %s %s\n", hex.EncodeToString(left), hex.EncodeToString(right), hex.EncodeToString(dst))

105
106
			// The index to write this value to. This depends in the row permutation.
			rowI := perm[a*2+b] * K.valueLen
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
107
108

			copy(cRow[rowI:rowI+K.valueLen], dst)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
109
110
		}
	}
111
	return cRow
Thomas Hoffmann's avatar
Thomas Hoffmann committed
112
113
}

114
115
func G(A, B []byte, i int) []byte {
	hash := sha256.New()
Thomas Hoffmann's avatar
Thomas Hoffmann committed
116
	hash.Write(A)
117
118
	hash.Write(B)
	hash.Write([]byte{byte(i)})
Thomas Hoffmann's avatar
Thomas Hoffmann committed
119
120
121
	return hash.Sum(nil)
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
122
123
func (c *Circuit) Evaluate(x []byte) ([]byte, error) {
	K, err := NewTable(1, c.numWires, c.k)
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
124
125
126
	if err != nil {
		return nil, err
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
127
128
129
130
131
132
133
134
135
	copy(K.data[:len(x)], x)

	Li := []int{0, 1, 2, 6, 8}
	Ri := []int{3, 4, 5, 7, 9}
	Oi := []int{6, 7, 8, 9, 10}

	// zeroes := make([]byte, K.valueLen)

	fmt.Println(c.F.valueLen)
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
136
137

	// For each circuit gate
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
138
	for i := 0; i < c.F.rows; i++ {
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
139
		// For each C
140
		for j := 0; j < 4; j++ {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
141
142
143
144
145
146
147
148
			left := c.G(K.getValue(0, Li[i]), K.getValue(0, Ri[i]), Oi[i])
			right := c.F.getValue(i, j)

			dst := util.XOR(left, right)
			fmt.Printf("%s %s %s\n", hex.EncodeToString(left), hex.EncodeToString(right), hex.EncodeToString(dst))

			// fmt.Printf(len(left))

Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
149
150
			// dst := make([]byte, 2*F.valueLen)
			// util.XOR(dst, K.getValue())
Thomas Hoffmann's avatar
Thomas Hoffmann committed
151
152
		}
	}
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

	// var K = x
	// var res []byte
	// for i := 0; i < 3; i++ {
	// 	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)) {
	// 			K = append(K, res[:16])
	// 			break
	// 		}
	// 	}
	// 	return nil, fmt.Errorf("Aborted while evaluating the garbled circuit, no match was found")
	// }
	// return K[len(K)-1], nil
	return nil, nil
Thomas Hoffmann's avatar
Thomas Hoffmann committed
168
169
170
}

func Decode(d [][]byte, Z []byte) bool {
171
	if bytes.Equal(d[0], Z) {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
172
		return false
173
	} else if bytes.Equal(d[1], Z) {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
174
175
176
177
		return true
	}
	//TODO: Error handling
	return false
Thomas Hoffmann's avatar
Thomas Hoffmann committed
178
179
180
181
182
183
}

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

184
185
186
187
188
189
// type Circuit struct {
// 	wires      []int
// 	gates      []Gate
// 	outputWire int
// 	numInput   int
// }
Thomas Hoffmann's avatar
Thomas Hoffmann committed
190

191
192
193
194
195
196
197
// func NewCircuit(numInput int) *Circuit {
// 	return &Circuit{
// 		wires:    make([]int, numInput),
// 		gates:    make([]Gate, 0),
// 		numInput: numInput,
// 	}
// }
Thomas Hoffmann's avatar
Thomas Hoffmann committed
198

199
200
201
// func (c *Circuit) getInputWires(i int) (Li, Ri int) {
// 	return i, c.numInput + i
// }
Thomas Hoffmann's avatar
Thomas Hoffmann committed
202

203
204
205
206
207
208
// func (c *Circuit) AddGate(Li, Ri int, f func(a, b int) int) *Gate {
// 	c.wires = append(c.wires, 0)
// 	g := newGate(Li, Ri, len(c.wires)-1, f)
// 	c.gates = append(c.gates, *g)
// 	return g
// }
209

210
211
212
213
214
// type Gate struct {
// 	Li, Ri    int
// 	i         int
// 	truthfunc func(a, b int) int
// }
Thomas Hoffmann's avatar
Thomas Hoffmann committed
215

216
217
218
219
220
221
222
// func newGate(Li, Ri, i int, f func(a, b int) int) (g *Gate) {
// 	g.Li = Li
// 	g.Ri = Ri
// 	g.i = i
// 	g.truthfunc = f
// 	return
// }
Thomas Hoffmann's avatar
Thomas Hoffmann committed
223
224
225
226
227
228
229
230
231
232
233
234
235

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

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

236
237
func ORGateWithNot(a, b int) int {
	if ((1 - b) + a) == 0 {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
238
239
240
241
242
243
		return 0
	} else {
		return 1
	}
}

244
245
func ANDGate(a, b int) int {
	return a * b
Thomas Hoffmann's avatar
Thomas Hoffmann committed
246
}