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?

  • $\begingroup$ 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. $\endgroup$ – Guut Boy Aug 8 '16 at 12:28

From The Foundation of Garbled Circuits

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.

This example shows that you must restrict your arguments when you refer to the optimality considerations of a garbling scheme. This topic is currently under an intensive research.

  • $\begingroup$ Sure, the special example as you showed above is O(1), however, my point is to ask the existence of such garbling scheme with sublinear offline complexity and it looks impossible, for me, to achieve sublinear offline complexity, but maybe someone else can. $\endgroup$ – CryptoLover Aug 9 '16 at 2:09
  • $\begingroup$ @LinfengZhou (Hey =)) -- you're right. Sublinear offline complexity is impossible, in the sense you mean, for information-theoretic reasons -- if you don't read the entire circuit description, then you cannot correctly compute the function (since you're missing some necessary bit of its description, in general) $\endgroup$ – Daniel Apon Aug 10 '16 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.