Circuits

Circuits are basic building block which often use in Scapi, espacially in MPC protocols.

Garbled Circuit refers the case of a circuit which we don’t want the evaluator to know the values in the middle of the circuit evaluation. Meaning, each gate’s output should tell nothing about its actual result. In order to get this goal we garble the circuit. In case of a Boolean circuit, each wire gets two garbled values (which we called “keys”). During the circuit computation, each gate outputs one of its output wire’s garbled values. At the end, the circuit outputs garbled values for each output wire. In order to translate it to a meaningful result, one should call the translate function of the circuit.

All garbled circuits have four main operations:
  1. The garble function that creates the garbled table.
  2. The compute function that computes a result on a garbled circuit on the input which is the keys that were chosen for each input wire.
  3. The verify method is used in the case of a malicious adversary to verify that the garbled circuit created is an honest garbling of the agreed upon non garbled circuit.
  4. The translate method that translates the garbled output which usually is generated by the compute() function into meaningful output (a 0/1 result, rather than the keys outputed by compute).

Create the circuit

The best way to create a circuit is using a file. There are three formats of circuits that are quite similar:

Two-Party Boolean circuit

The format of the circuit file should be as follows.

  1. Number of gates
  2. Number of parties
  3. For each party:
  • Party number
  • Number of inputs for that party
  • A list of integer labels of each of these input wires.
  1. Number of output wires
  2. List of integer labels of each of these output wires.
  3. For each gate:
  • Number of input wires
  • Number of output wires
  • Input wires labels
  • Output Wires labels
  • Truth table (as a 0-1 string).

An example file:

1               // One gate
2               // Two parties
1 1 0           // Party one, has one input wire, labeled "0"
2 1 1           // Party two, has one input wire, labeled "1"
1               // One output wire
2               // The output wire, labeled "2"
2 1 0 1 2 0001  // The first (and only) gate has 2 input wire labeled "0" and "1", one output wire labeled "2" and the truth table is 0001 (AND gate).

Multi-Party Boolean circuit

The format of the circuit file should be as follows.

  1. Number of gates
  2. Number of parties
  3. For each party:
  • Party number
  • Number of inputs for that party
  • A list of integer labels of each of these input wires.
  1. For each party:
  • Party number
  • Number of outputs for that party
  • A list of integer labels of each of these output wires.
  1. For each gate:
  • Number of input wires
  • Number of output wires
  • Input wires labels
  • Output Wires labels
  • Truth table (as a 0-1 string).

An example file:

1               // One gate
2               // Two parties
1 1 0           // Party one, has one input wire, labeled "0"
2 1 1           // Party two, has one input wire, labeled "1"
1 1 0           // Party one has no output wires
2 1 2           // Party two has one output wire, labeled "2"
2 1 0 1 2 0001  // The first (and only) gate has 2 input wire labeled "0" and "1", one output wire labeled "2" and the truth table is 0001 (AND gate).

Multi-Party Arithmetic circuit

The format of the circuit file should be as follows.

  1. Number of gates
  2. Number of parties
  3. For each party:
  • Party number
  • Number of inputs for that party
  • A list of integer labels of each of these input wires.
  1. For each party:
  • Party number
  • Number of outputs for that party
  • A list of integer labels of each of these output wires.
  1. For each gate:
  • Number of input wires
  • Number of output wires
  • Input wires labels
  • Output Wires labels
  • A number that indicates the circuit type, see table below.

The available gates types are listed in the next table:

Gate type Number
ADD 1
MULT 2
SCALAR MULTIPLICATION 5
SUBTRACT 6
SCALAR ADD 7

An example file:

1               // One gate
2               // Two parties
1 1 0           // Party one, has one input wire, labeled "0"
2 1 1           // Party two, has one input wire, labeled "1"
1 1 0           // Party one has no output wires
2 1 2           // Party two has one output wire, labeled "2"
2 1 0 1 2 1     // The first (and only) gate has 2 input wire labeled "0" and "1", one output wire labeled "2" and the gate number is 1 (AND gate).