Full Description

Garbling. The garbling algorithm $\mathsf{Garble}(\mathsf{C})$ is described as follows.

• Let $\mathsf{CircuitInputs}(\mathsf{C})$, $\mathsf{CircuitOutputs}(\mathsf{C})$ be the set of input and output wires of $\mathsf{C}$, respectively. Given a non-input wire $i$, let $(a,b)\leftarrow \mathsf{InputWires}(\mathsf{C},i)$ denote the two input wires $a,b$ of $i$ associated to an $\mathsf{AND}$ or $\mathsf{XOR}$ gate. Let $a\leftarrow \mathsf{InputsWires}(\mathsf{C},i)$ denote the input wire $a$ of $i$ associated to an $\mathsf{INV}$ gate. The garbler maintains three sets $E$,$D$ and $T$. The garbler also maintains a $\mathsf{counter}$ initiated as $0$.

• Choose a secret global 128-bit string $\Delta$ uniformly, and set $\mathsf{LSB}(\Delta )=1$. Let $P=X\oplus \Delta$ be the label of public bit $1$, where $X$ is chosen uniformly at random. Note that $P$ will be sent to the evaluator.

• For $i\in \mathsf{CircuitInputs}(\mathsf{C})$, do the following.

  • Choose $128$-bit $X_i^0$ uniformly at random, and set $X_i^1=X_i^0\oplus \Delta$.
  • Let $e_i=X_i^0$ and insert it to $E$.

• For any non-input wire $i$, do the following.

  • If the gate associated to $i$ is a $\mathsf{XOR}$ gate.
    • Let $(a,b)\leftarrow \mathsf{GateInputs}(\mathsf{C},i)$.
    • Compute $X_i^0=X_a^0\oplus X_b^0$ and $X_i^1=X_i^0\oplus \Delta$.
  • If the gate associated to $i$ is an $\mathsf{INV}$ gate.
    • Let $a\leftarrow \mathsf{GateInputs}(\mathsf{C},i)$,
    • Compute $X_i^0=X_a^0\oplus P$ and $X_i^1=X_i^0\oplus \Delta$.
  • If the gate associated to $i$ is an $\mathsf{AND}$ gate.
    • let $(a,b)\leftarrow \mathsf{GateInputs}(\mathsf{C},i)$,
    • Let $p_a=\mathsf{LSB}(X_a^0)$, $p_b=\mathsf{LSB}(X_b^0)$.
    • Compute the first half gate:
    • Let $T_G=\mathsf{H}(\mathsf{counter},X_a^0)\oplus \mathsf{H}(\mathsf{counter},X_a^1)\oplus (p_b\cdot \Delta )$.
    • Let $X_G^0=\mathsf{H}(\mathsf{counter},X_a^0)\oplus (p_a\cdot T_G)$.
    • $\mathsf{counter}=\mathsf{counter}+1$.
    • Compute the second half gate:
    • Let $T_E=\mathsf{H}(\mathsf{counter},X_b^0)\oplus \mathsf{H}(\mathsf{counter},X_b^1)\oplus X_a^0$.
    • Let $X_E^0=\mathsf{H}(\mathsf{counter},X_b^0)\oplus p_b\cdot (T_E\oplus X_a^0)$
    • Let $X_i^0=X_G^0\oplus X_E^0$, $X_i^1=X_i^0\oplus \Delta$ and insert the garbled gate $(T_G,T_E)$ to $T$.
    • $\mathsf{counter}=\mathsf{counter}+1$.

• For $i\in \mathsf{CircuitOutputs}(\mathsf{C})$, do the following.

  • Compute $d_i=\mathsf{LSB}(X_i^0)$.
  • Insert $d_i$ into $D$.

• The garbler outputs $(G,E,D)$.

Input Encoding. Given $E=(e_1,\dots ,e_{\ell })$, the garbler encodes the input $(x_1,\dots ,x_{\ell })\in {\{0,1\}}^{\ell }$ as follows.

• For all $1\le i\le \ell$, compute $X_i=e_i\oplus x_i\Delta$
• Outputs $X=(X_1,\dots ,X_{\ell })$.

Evaluating. The evaluating algorithm $\mathsf{Eval}(\mathsf{C})$ is described as follows.

• The evaluator takes as input the garbled circuit $T$ and the encoded inputs $X$.

• The evaluator obtains the input labels $(X_1,\dots ,X_{\ell })$ from $X$ and initiates $\mathsf{counter}=0$.

• For any non-input wire $i$, do the following.

  • If the gate associated to $i$ is a $\mathsf{XOR}$ gate.
    • Let $(a,b)\leftarrow \mathsf{GateInputs}(\mathsf{C},i)$.
    • Compute $X_i=X_a\oplus X_b$.
  • If the gate associated to $i$ is an $\mathsf{INV}$ gate.
    • Let $a\leftarrow \mathsf{GateInputs}(\mathsf{C},i)$,
    • Compute $X_i=X_a\oplus P$.
  • If the gate associated to $i$ is an $\mathsf{AND}$ gate.
    • Let $(a,b)\leftarrow \mathsf{GateInputs}(\mathsf{C},i)$,
    • Let $s_a=\mathsf{LSB}(X_a)$, $s_b=\mathsf{LSB}(X_b)$.
    • Parse $T_i$ as $(T_G,T_E)$.
    • Compute $X_G=\mathsf{H}(\mathsf{counter},X_a)\oplus s_a\cdot T_G$.
    • $\mathsf{counter}=\mathsf{counter}+1$.
    • Compute $X_E=\mathsf{H}(\mathsf{counter},X_b)\oplus s_b(T_E\oplus X_a)$.
    • Let $X_i=X_G\oplus X_E$.

• For $i\in \mathsf{CircuitOutputs}(\mathsf{C})$, do the following.

  • Let $Y_i=X_i$.
  • Outputs $Y$, the set of $Y_i$.

Output Decoding. Given $Y$ and $D$, the evaluator decodes the labels into outputs as follows.

• For any $i$, compute $y_i=d_i\oplus \mathsf{LSB}(Y_i)$.
• Outputs all $y_i$.