circuit.go 5.08 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"
Thomas Hoffmann's avatar
Thomas Hoffmann committed
8
9
)

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

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

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

Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
20
21
22
23
24
25
26
27
28
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,
29

Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
30
31
32
33
		F: F,
	}
	return
}
34

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

Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
46
47
48
49
	// 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))
50

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

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

Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
59
60
	c.E[1], _ = NewTable(c.numInputs, 2, c.k)
	c.E[1].SetData(kTable.getRows(c.numInputs, c.numInputs))
61
62

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

66
	return
Thomas Hoffmann's avatar
Thomas Hoffmann committed
67
}
68

69
70
// 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
71
func Encode(e *Table, x []bool) (X []byte) {
72
73
74
	X = make([]byte, 0)
	for i, b := range x {
		if b {
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
75
			X = append(X, e.getValue(i, 1)...)
76
		} else {
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
77
			X = append(X, e.getValue(i, 0)...)
78
79
80
81
82
83
84
85
		}
	}
	if len(x)*e.valueLen != len(X) {
		panic("Wrong length of X")
	}
	return
}

86
//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
87
func (c *Circuit) garbleGate(K *Table, Li, Ri, out int, gateFun func(a, b int) int) []byte {
88
89
	cRow := make([]byte, K.valueLen*8) // because 4 values of double length
	perm := cryptoUtil.Perm(4)         // Random permutation
90
91
92
93

	// 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
94
			left := c.G(K.getValue(Li, a), K.getValue(Ri, b), out)
95
			right := make([]byte, K.valueLen*2)
96

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

			// 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)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
103
104
		}
	}
105
	return cRow
Thomas Hoffmann's avatar
Thomas Hoffmann committed
106
107
}

108
109
func G(A, B []byte, i int) []byte {
	hash := sha256.New()
Thomas Hoffmann's avatar
Thomas Hoffmann committed
110
	hash.Write(A)
111
112
	hash.Write(B)
	hash.Write([]byte{byte(i)})
Thomas Hoffmann's avatar
Thomas Hoffmann committed
113
114
115
	return hash.Sum(nil)
}

Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
116
117
118
119
120
121
122
123
124
125
func Evaluate(F *Table, x []byte) ([]byte, error) {
	K, err := NewTable(1, len(x)/F.valueLen, F.valueLen*8)
	if err != nil {
		return nil, err
	}
	K.SetData(x)

	// For each circuit gate
	for i := 0; i < len(F.data); i++ {
		// For each C
126
		for j := 0; j < 4; j++ {
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
127
128
			// dst := make([]byte, 2*F.valueLen)
			// util.XOR(dst, K.getValue())
Thomas Hoffmann's avatar
Thomas Hoffmann committed
129
130
		}
	}
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

	// 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
146
147
148
}

func Decode(d [][]byte, Z []byte) bool {
149
	if bytes.Equal(d[0], Z) {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
150
		return false
151
	} else if bytes.Equal(d[1], Z) {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
152
153
154
155
		return true
	}
	//TODO: Error handling
	return false
Thomas Hoffmann's avatar
Thomas Hoffmann committed
156
157
158
159
160
161
}

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

162
163
164
165
166
167
// type Circuit struct {
// 	wires      []int
// 	gates      []Gate
// 	outputWire int
// 	numInput   int
// }
Thomas Hoffmann's avatar
Thomas Hoffmann committed
168

169
170
171
172
173
174
175
// func NewCircuit(numInput int) *Circuit {
// 	return &Circuit{
// 		wires:    make([]int, numInput),
// 		gates:    make([]Gate, 0),
// 		numInput: numInput,
// 	}
// }
Thomas Hoffmann's avatar
Thomas Hoffmann committed
176

177
178
179
// func (c *Circuit) getInputWires(i int) (Li, Ri int) {
// 	return i, c.numInput + i
// }
Thomas Hoffmann's avatar
Thomas Hoffmann committed
180

181
182
183
184
185
186
// 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
// }
187

188
189
190
191
192
// type Gate struct {
// 	Li, Ri    int
// 	i         int
// 	truthfunc func(a, b int) int
// }
Thomas Hoffmann's avatar
Thomas Hoffmann committed
193

194
195
196
197
198
199
200
// 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
201
202
203
204
205
206
207
208
209
210
211
212
213

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

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

214
215
func ORGateWithNot(a, b int) int {
	if ((1 - b) + a) == 0 {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
216
217
218
219
220
221
		return 0
	} else {
		return 1
	}
}

222
223
func ANDGate(a, b int) int {
	return a * b
Thomas Hoffmann's avatar
Thomas Hoffmann committed
224
}