circuit.go 5.66 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
	"errors"
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
9
	"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
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
89
90
91
92
93
94
95
96
97
98
func Decode(d *Table, Z []byte) (bool, error) {
	if bytes.Equal(d.getValue(0, 0), Z) {
		return false, nil
	} else if bytes.Equal(d.getValue(0, 1), Z) {
		return true, nil
	} else {
		return false, errors.New("failed to decode")
	}
}

99
//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
100
func (c *Circuit) garbleGate(K *Table, Li, Ri, out int, gateFun func(a, b int) int) []byte {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
101
102
	cRow := make([]byte, 4*2*K.valueLen) // because 4 values of double length
	perm := cryptoUtil.Perm(4)           // Random permutation
103
104
105
106

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

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

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

115
			// The index to write this value to. This depends in the row permutation.
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
116
117
			rowI := perm[a*2+b] * 2 * K.valueLen
			copy(cRow[rowI:rowI+2*K.valueLen], dst)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
118
119
		}
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
120

121
	return cRow
Thomas Hoffmann's avatar
Thomas Hoffmann committed
122
123
}

124
125
func G(A, B []byte, i int) []byte {
	hash := sha256.New()
Thomas Hoffmann's avatar
Thomas Hoffmann committed
126
	hash.Write(A)
127
128
	hash.Write(B)
	hash.Write([]byte{byte(i)})
Thomas Hoffmann's avatar
Thomas Hoffmann committed
129
130
131
	return hash.Sum(nil)
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
132
133
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
134
135
136
	if err != nil {
		return nil, err
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
137
138
139
140
141
142
	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}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
143
	zeroes := make([]byte, K.valueLen)
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
144
145

	// For each circuit gate
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
146
	for i := 0; i < c.F.rows; i++ {
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
147
		// For each C
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
148
		success := false
149
		for j := 0; j < 4; j++ {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
150
151
152
153
154
			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)

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
155
156
157
158
159
160
161
162
163
			if bytes.Equal(zeroes, dst[K.valueLen:]) {
				// fmt.Printf("%s %s %s\n", hex.EncodeToString(left), hex.EncodeToString(right), hex.EncodeToString(dst))
				K.setValue(0, i+c.numInputs, dst[:K.valueLen])
				success = true
				break
			}
		}
		if !success {
			return nil, fmt.Errorf("failed to evaluate circuit layer %d", i)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
164
165
		}
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
166
	return K.getValue(0, c.numWires-1), nil
Thomas Hoffmann's avatar
Thomas Hoffmann committed
167
168
}

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

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

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

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

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

202
203
204
205
206
207
// 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
// }
208

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

215
216
217
218
219
220
221
// 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
222
223
224
225
226
227
228
229
230
231
232
233
234

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

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

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

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