circuit.go 4.32 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
12
type Circuit struct {
	numInputs, numWires, k int
Thomas Hoffmann's avatar
Thomas Hoffmann committed
13

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

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

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

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

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

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

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

56
	// Create e
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
57
	c.E = make([]*Table, 2)
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
58
59
60
61
	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
62
	c.E[0].SetData(kTable.getRows(0, c.numInputs/2))
63

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
64
65
66
67
	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
68
	c.E[1].SetData(kTable.getRows(c.numInputs/2, c.numInputs/2))
69
70

	// Create d
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
71
72
73
74
	c.D, err = NewTable(1, 2, c.k)
	if err != nil {
		return
	}
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
75
	c.D.SetData(kTable.getRow(c.numWires - 1))
76

77
	return
Thomas Hoffmann's avatar
Thomas Hoffmann committed
78
}
79

80
81
// 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
82
func Encode(e *Table, x []bool) (X []byte) {
83
84
85
	X = make([]byte, 0)
	for i, b := range x {
		if b {
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
86
			X = append(X, e.getValue(i, 1)...)
87
		} else {
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
88
			X = append(X, e.getValue(i, 0)...)
89
90
91
92
93
94
95
96
		}
	}
	if len(x)*e.valueLen != len(X) {
		panic("Wrong length of X")
	}
	return
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
97
98
99
100
101
102
103
104
105
106
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")
	}
}

107
//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
108
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
109
	cRow := make([]byte, 4*2*K.valueLen) // because 4 values of double length
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
110
	perm := util.Perm(4)                 // Random permutation
111
112
113
114

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

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

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

122
			// The index to write this value to. This depends in the row permutation.
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
123
124
			rowI := perm[a*2+b] * 2 * K.valueLen
			copy(cRow[rowI:rowI+2*K.valueLen], dst)
Thomas Hoffmann's avatar
Thomas Hoffmann committed
125
126
		}
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
127

128
	return cRow
Thomas Hoffmann's avatar
Thomas Hoffmann committed
129
130
}

131
132
func G(A, B []byte, i int) []byte {
	hash := sha256.New()
Thomas Hoffmann's avatar
Thomas Hoffmann committed
133
	hash.Write(A)
134
135
	hash.Write(B)
	hash.Write([]byte{byte(i)})
Thomas Hoffmann's avatar
Thomas Hoffmann committed
136
137
138
	return hash.Sum(nil)
}

Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
139
140
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
141
142
143
	if err != nil {
		return nil, err
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
144
145
146
147
148
149
	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
150
	zeroes := make([]byte, K.valueLen)
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
151
152

	// For each circuit gate
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
153
	for i := 0; i < c.F.rows; i++ {
Anders Jensen Løvig's avatar
Stuff    
Anders Jensen Løvig committed
154
		// For each C
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
155
		success := false
156
		for j := 0; j < 4; j++ {
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
157
158
159
160
			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
161
162
163
164
165
166
167
168
			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
169
170
		}
	}
Anders Jensen Løvig's avatar
Anders Jensen Løvig committed
171

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

Thomas Hoffmann's avatar
Thomas Hoffmann committed
175
176
177
178
179
180
181
182
183
184
185
186
////////////////////////////////////////////////////////////////
// GATES
////////////////////////////////////////////////////////////////

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

187
188
func ORGateWithNot(a, b int) int {
	if ((1 - b) + a) == 0 {
Thomas Hoffmann's avatar
Thomas Hoffmann committed
189
190
191
192
193
194
		return 0
	} else {
		return 1
	}
}

195
196
func ANDGate(a, b int) int {
	return a * b
Thomas Hoffmann's avatar
Thomas Hoffmann committed
197
}