# Offline Complexity of the garbling scheme

The offline complexity of the garbling scheme means the time complexity of the circuit encoding algorithm, that is, $\textrm{GC.Circ}(1^\lambda, C)$, where $C$ is the circuit to be garbled. It's straightforward to see that the offline complexity is $\textrm{poly}(\lambda, C)$.

My question is that whether there exists any optimal offline complexity of circuit encoding algorithm? for example, is it possible that the offline complexity is "sublinear" in the circuit size?

• I don't know of a concrete impossibility result, but it is hard to imagine how we could garble the circuit without 'touching' each gate of the circuit. I.e., at least linear complexity. – Guut Boy Aug 8 '16 at 12:28

A garbling scheme is a five-tuple of algorithms $G=(Gb,En,De,Ev,ev)$. The first of these is probabilistic; the remaining algorithms are deterministic. A string $f$, the original function, describes the function ev$(f,\cdot): \{0, 1\}^n\rightarrow \{0, 1\}^m$ that we want to garble where $n$ and $m$ are the input and output size resp. On input $f$ and a security parameter $k\in \mathbb{N}$, algorithm $Gb$ returns a triple of strings $(F, e, d)\rightarrow Gb(1^k, f)$. String $e$ describes an encoding function, $En(e,\cdot)$, that maps an initial input $x\in\{0, 1\}^n$ to a garbled input $X=En(e, x)$. String $F$ describes a garbled function, $Ev(F,\cdot)$, that maps each garbled input $X$ to a garbled output $Y = Ev(F, X)$. String $d$ describes a decoding function, $De(d,\cdot)$, that maps a garbled output $Y$ to a final output $y = De(d, Y )$.
Thus, taking an FHE $(Gen,Enc,Dec)$ scheme (see this)which takes an encoded input $X=Enc(x)$, applies the function $C$ to it to get $Y=C(X)$ and then decode the output by $y=Dec(Y)$ we get that $y=C(x)=Dec(C(Enc(x))$ (since the scheme is fully homomorphic. In this example the garbling algorithm, the one you denote by $CC.Circ$ just do nothing and its complexity is $O(1)$, which is optimal.