circuit.go 4.79 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"
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
5
	"crycomp/internal/crypto/util"
6
	"crypto/sha256"
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
7
	"errors"
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
8
	"fmt"
Thomas Hoffmann's avatar
Thomas Hoffmann committed
9
10
)

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

Anders Jensen Løvig's avatar
Builder    
Anders Jensen Løvig committed
15
16
	gates []*gate

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

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

Anders Jensen Løvig's avatar
Builder    
Anders Jensen Løvig committed
24
25
26
27
28
29
func NewCircuit(numInputs, numWires, k int, gates []*gate) (c *Circuit, err error) {
	if k%8 != 0 {
		return nil, errors.New("k must be multiple of 8")
	}
	numNonInputs := numWires - numInputs
	F, err := NewTable(numNonInputs, 4, k*2)
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
30
31
32
33
34
35
36
	if err != nil {
		return
	}
	c = &Circuit{
		numInputs: numInputs,
		numWires:  numWires,
		k:         k,
37

Anders Jensen Løvig's avatar
Builder    
Anders Jensen Løvig committed
38
39
		gates: gates,

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
40
		G: G,
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
41
42
43
44
		F: F,
	}
	return
}
45

Anders Jensen Løvig's avatar
Builder    
Anders Jensen Løvig committed
46
func (c *Circuit) Garble() (err error) {
47
	// 1. Create two random strings for each wire.
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
48
	kTable, err := NewTable(c.numWires, 2, c.k)
49
50
51
52
	if err != nil {
		return
	}
	err = kTable.randomizeTable()
53
54
55
	if err != nil {
		return
	}
Thomas Hoffmann's avatar
Thomas Hoffmann committed
56

Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
57
	// 2. Create a garbled table for all F values (4 for each gate)
Anders Jensen Løvig's avatar
Builder    
Anders Jensen Løvig committed
58
59
60
61
62
63
64
	for i, gate := range c.gates {
		c.F.setRow(i, c.garbleGate(kTable, 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))
65

Anders Jensen Løvig's avatar
Builder    
Anders Jensen Løvig committed
66
67
	// c.F.setRow(3, c.garbleGate(kTable, 6, 7, 9, ANDGate))
	// c.F.setRow(4, c.garbleGate(kTable, 8, 9, 10, ANDGate))
68

69
	// Create e
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
70
	c.E = make([]*Table, 2)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
71
72
73
74
	c.E[0], err = NewTable(c.numInputs/2, 2, c.k)
	if err != nil {
		return
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
75
	c.E[0].SetData(kTable.getRows(0, c.numInputs/2))
76

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
77
78
79
80
	c.E[1], err = NewTable(c.numInputs/2, 2, c.k)
	if err != nil {
		return
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
81
	c.E[1].SetData(kTable.getRows(c.numInputs/2, c.numInputs/2))
82
83

	// Create d
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
84
85
86
87
	c.D, err = NewTable(1, 2, c.k)
	if err != nil {
		return
	}
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
88
	c.D.SetData(kTable.getRow(c.numWires - 1))
89
	return
Thomas Hoffmann's avatar
Thomas Hoffmann committed
90
}
91

92
93
// 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
94
func Encode(e *Table, x []bool) (X []byte) {
95
96
97
	X = make([]byte, 0)
	for i, b := range x {
		if b {
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
98
			X = append(X, e.getValue(i, 1)...)
99
		} else {
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
100
			X = append(X, e.getValue(i, 0)...)
101
102
103
104
105
106
107
108
		}
	}
	if len(x)*e.valueLen != len(X) {
		panic("Wrong length of X")
	}
	return
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
109
110
111
112
113
114
115
116
117
118
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")
	}
}

119
//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
Builder    
Anders Jensen Løvig committed
120
func (c *Circuit) garbleGate(K *Table, gate *gate) []byte {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
121
	cRow := make([]byte, 4*2*K.valueLen) // because 4 values of double length
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
122
	perm := util.Perm(4)                 // Random permutation
123
124
125
126

	// 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
Builder    
Anders Jensen Løvig committed
127
			left := c.G(K.getValue(gate.left, a), K.getValue(gate.right, b), gate.out)
128
			right := make([]byte, K.valueLen*2)
129

Anders Jensen Løvig's avatar
Builder    
Anders Jensen Løvig committed
130
131
132
133
134
135
			c := 0
			if gate.fun(a == 1, b == 1) {
				c = 1
			}

			copy(right[:K.valueLen], K.getValue(gate.out, c))
136

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
137
138
			dst := util.XOR(left, right) // XOR with left as destination.

139
			// The index to write this value to. This depends in the row permutation.
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
140
141
			rowI := perm[a*2+b] * 2 * K.valueLen
			copy(cRow[rowI:rowI+2*K.valueLen], dst)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
142
143
		}
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
144

145
	return cRow
Thomas Hoffmann's avatar
Thomas Hoffmann committed
146
147
}

148
149
func G(A, B []byte, i int) []byte {
	hash := sha256.New()
Thomas Hoffmann's avatar
Thomas Hoffmann committed
150
	hash.Write(A)
151
152
	hash.Write(B)
	hash.Write([]byte{byte(i)})
Thomas Hoffmann's avatar
Thomas Hoffmann committed
153
154
155
	return hash.Sum(nil)
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
156
157
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
158
159
160
	if err != nil {
		return nil, err
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
161
162
	copy(K.data[:len(x)], x)

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
163
	zeroes := make([]byte, K.valueLen)
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
164
165

	// For each circuit gate
Anders Jensen Løvig's avatar
Builder    
Anders Jensen Løvig committed
166
	for i, gate := range c.gates {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
167
		success := false
168
		for j := 0; j < 4; j++ {
Anders Jensen Løvig's avatar
Builder    
Anders Jensen Løvig committed
169
			left := c.G(K.getValue(0, gate.left), K.getValue(0, gate.right), gate.out)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
170
171
172
			right := c.F.getValue(i, j)
			dst := util.XOR(left, right)

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
173
174
175
176
177
178
179
180
			if bytes.Equal(zeroes, dst[K.valueLen:]) {
				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
181
182
		}
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
183

Anders Jensen Løvig's avatar
Builder    
Anders Jensen Løvig committed
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
	// for i := 0; i < c.F.rows; i++ {
	// 	// For each C
	// 	success := false
	// 	for j := 0; j < 4; j++ {
	// 		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)

	// 		if bytes.Equal(zeroes, dst[K.valueLen:]) {
	// 			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)
	// 	}
	// }

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
203
	return K.getValue(0, c.numWires-1), nil
Thomas Hoffmann's avatar
Thomas Hoffmann committed
204
205
}

Thomas Hoffmann's avatar
Thomas Hoffmann committed
206
207
208
////////////////////////////////////////////////////////////////
// GATES
////////////////////////////////////////////////////////////////