circuit.go

package garbled

import (
	"bytes"
	"crycomp/internal/crypto/util"
	"crypto/sha256"
	"errors"
	"fmt"
)

type Circuit struct {
	numInputs, numWires, k int

	G func(a, b []byte, i int) []byte

	F *Table
	E []*Table
	D *Table
}

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,

		G: G,
		F: F,
	}
	return
}

func (c *Circuit) GarbleBloodCircuit() (err error) {
	// 1. Create two random strings for each wire.
	kTable, err := NewTable(c.numWires, 2, c.k)
	if err != nil {
		return
	}
	err = kTable.randomizeTable()
	if err != nil {
		return
	}

	// 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))

	c.F.setRow(3, c.garbleGate(kTable, 6, 7, 9, ANDGate))
	c.F.setRow(4, c.garbleGate(kTable, 8, 9, 10, ANDGate))

	// Create e
	c.E = make([]*Table, 2)
	c.E[0], err = NewTable(c.numInputs/2, 2, c.k)
	if err != nil {
		return
	}
	c.E[0].SetData(kTable.getRows(0, c.numInputs/2))

	c.E[1], err = NewTable(c.numInputs/2, 2, c.k)
	if err != nil {
		return
	}
	c.E[1].SetData(kTable.getRows(c.numInputs/2, c.numInputs/2))

	// Create d
	c.D, err = NewTable(1, 2, c.k)
	if err != nil {
		return
	}
	c.D.SetData(kTable.getRow(c.numWires - 1))

	return
}

// Encode x using the e table. If ey == true, we use the second
// half of e, otherwise first half
func Encode(e *Table, x []bool) (X []byte) {
	X = make([]byte, 0)
	for i, b := range x {
		if b {
			X = append(X, e.getValue(i, 1)...)
		} else {
			X = append(X, e.getValue(i, 0)...)
		}
	}
	if len(x)*e.valueLen != len(X) {
		panic("Wrong length of X")
	}
	return
}

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")
	}
}

//Creates a row (C_0^i, C_1^i, C_2^i ,C_3^i) for the garbled table, where
func (c *Circuit) garbleGate(K *Table, Li, Ri, out int, gateFun func(a, b int) int) []byte {
	cRow := make([]byte, 4*2*K.valueLen) // because 4 values of double length
	perm := util.Perm(4)                 // Random permutation

	// for (a,b) in {0,1} x {0,1}
	for a := 0; a <= 1; a++ {
		for b := 0; b <= 1; b++ {
			left := c.G(K.getValue(Li, a), K.getValue(Ri, b), out)
			right := make([]byte, K.valueLen*2)

			copy(right[:K.valueLen], K.getValue(out, gateFun(a, b)))

			dst := util.XOR(left, right) // XOR with left as destination.

			// The index to write this value to. This depends in the row permutation.
			rowI := perm[a*2+b] * 2 * K.valueLen
			copy(cRow[rowI:rowI+2*K.valueLen], dst)
		}
	}

	return cRow
}

func G(A, B []byte, i int) []byte {
	hash := sha256.New()
	hash.Write(A)
	hash.Write(B)
	hash.Write([]byte{byte(i)})
	return hash.Sum(nil)
}

func (c *Circuit) Evaluate(x []byte) ([]byte, error) {
	K, err := NewTable(1, c.numWires, c.k)
	if err != nil {
		return nil, err
	}
	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)

	// For each circuit gate
	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)
		}
	}

	return K.getValue(0, c.numWires-1), nil
}

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

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

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

func ANDGate(a, b int) int {
	return a * b
}