Garbled circuit

A garbling scheme turns a Boolean circuit $f$ into a garbled circuit $F$, an encoding key that maps each input $x$ to a garbled input $X$, and decoding information $d$, so that evaluating $F$ on $X$ and decoding gives $f(x)$ while $(F,X,d)$ reveals nothing else about $x$. The syntax and security notions below are those of BHR12.

Syntax

A garbling scheme is a tuple of efficient algorithms $\mathcal{G}=(\mathsf{Garble},\mathsf{Encode},\mathsf{Eval},\mathsf{Decode})$ for Boolean circuits $f:\{0,1{\}}^m\to \{0,1{\}}^k$:

• $\mathsf{Garble}(1^{\lambda },f)\to (F,e,d)$, a randomized algorithm outputting a garbled circuit $F$, an encoding key $e$ and decoding information $d$.
• $\mathsf{Encode}(e,x)\to X$, a deterministic algorithm mapping $x\in \{0,1{\}}^m$ to a garbled input $X$.
• $\mathsf{Eval}(F,X)\to Y$, a deterministic algorithm outputting a garbled output $Y$.
• $\mathsf{Decode}(d,Y)\to y$, a deterministic algorithm outputting $y\in \{0,1{\}}^k$ or $\perp$.

The scheme is projective: the encoding key is a list of label pairs $e=(X_i^0,X_i^1{)}_{i\in [m]}$, and $\mathsf{Encode}(e,x)=(X_i^{x_i}{)}_{i\in [m]}$, so the garbled input of $x$ consists of one label per input bit.

Properties

Correctness

$\mathcal{G}$ is correct if for all $\lambda$, all circuits $f:\{0,1{\}}^m\to \{0,1{\}}^k$, all $x\in \{0,1{\}}^m$ and all $(F,e,d)$ output by $\mathsf{Garble}(1^{\lambda },f)$,

$$\mathsf{Decode}(d,\mathsf{Eval}(F,\mathsf{Encode}(e,x)))=f(x).$$

Privacy

The adversary chooses a circuit and an input; in world $0$ it receives the garbled circuit, the garbled input and the decoding information, and in world $1$ a simulator’s output computed from $f$ and $f(x)$ alone.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{prv}}_{\calG,\calA,\Sim}(\secpar)$}
\begin{algorithmic}
\State $b \getsr \bits$
\State $(f, x, \stA) \gets \calA(1^\secpar)$
\Comment{$f : \bits^m \to \bits^k$ a circuit, $x \in \bits^m$}
\State $(F, e, d) \gets \mathsf{Garble}(1^\secpar, f)$; $X := \mathsf{Encode}(e, x)$
\State $\mathit{out}_0 := (F, X, d)$
\State $\mathit{out}_1 \gets \Sim(1^\secpar, f, f(x))$
\State $b' \gets \calA(\stA, \mathit{out}_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A garbling scheme $\mathcal{G}$ is private if there is an efficient $\mathcal{S}$ such that for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathcal{G},\mathcal{A},\mathcal{S}}^{\mathrm{prv}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathcal{G},\mathcal{A},\mathcal{S}}^{\mathrm{prv}}(\lambda )=1\right]-1\right|$$

is negligible. A garbled circuit scheme here is a correct, projective and private garbling scheme.

Variations

Privacy relative to side information

BHR12 parameterize privacy by a side-information function $\Phi$: the simulator receives $\Phi (f)$ and $f(x)$ in place of $f$ and $f(x)$. With $\Phi (f)$ the topology of $f$, which omits the function each gate computes, the garbled circuit also hides $f$ beyond its topology — BHR12. A simulator for $\Phi$ computable from $f$ is a simulator for the notion above, applied to $\Phi (f)$ — standard.

Obliviousness and authenticity

Obliviousness asks that $(F,X)$, without $d$, be simulatable from the side information alone, so that the evaluator learns nothing about $f(x)$; authenticity asks that no efficient adversary given $(F,X)$ output a garbled output $Y\ne \mathsf{Eval}(F,X)$ with $\mathsf{Decode}(d,Y)\ne \perp$. They serve private and verifiable outsourcing of computation — BHR12.

Other results

• Any PRF gives a private projective garbling scheme (PRF ⇒ garbled circuits) — BHR12; its garbled table has four ciphertexts per gate — standard.
• XOR gates need no garbled table and no cryptographic operation (free XOR), in the random oracle model — KS08. With half gates, AND gates take two ciphertexts and XOR gates stay free, which is optimal among linear garbling schemes, a class that covers all known practical techniques — ZRE15. Slicing wire labels in half brings AND gates to $1.5\lambda +5$ bits with free XOR, from a circular correlation-robust hash — RR21.
• A garbling scheme and OT give two-party computation secure against semi-honest adversaries (Yao’s protocol) — Yao86, LP09.

Participates in

Builds on Garbled circuit

• GC + OT ⇒ Semi-honest 2PC (Yao)

Produces Garbled circuit

• PRF ⇒ Garbled circuits (BHR)