We consider randomized encoding for circuits as a equivalent primitive as the circuit garbling scheme. However, I have a question arised from their syntax, that is, how to compute the output length of randomized encoding?

From the syntax, the encoding algorithm of randomized encoding takes as input the circuit $C$ and an input $x$ and outputs a randomized encoding $\widetilde{C}(x)$, but the circuit garbling scheme handles the circuit $C$ and input $x$ separately, that is, the circuit garbling algorithm takes as input the circuit $C$ and outputs a garbled circuit $\widetilde{C}$ and a garbling key $K$; the input garbling algorithm takes as input the input value $x$ and the garbling key $K$ and then ouptuts a garbled input $\widetilde{x}$

does it mean $|\widetilde{x}|+|\widetilde{C}| = |\widetilde{C}(x)|$? I know that the online complexity of garbling scheme gives a bound on the size of $\widetilde{x}$, but what is the size of the garbled circuit $\widetilde{C}$? Can we implicitly regard it as $poly(1^\lambda, C)$

  • $\begingroup$ Do you have any reference material that you can point out? $\endgroup$ – Maarten Bodewes Aug 4 '16 at 11:10
  • $\begingroup$ @MaartenBodewes Sorry for the lack of materials, you can take the paper "adaptively secure garbled circuits from one way function" as the example. In this paper, the author mainly focus on the online complexity which is the bound on the length of the garbled input, but they didn't show what is the output size of the garbled circuit. I know this is not the main point of this paper but I just want to know the size of the garbled circuit. Maybe I should get into the details of their construction which uses somewhere equivocal encryption $\endgroup$ – CryptoLover Aug 4 '16 at 11:22
  • $\begingroup$ No, that's perfect. It's more to make sure everyone uses the same definitions. Disclaimer: I'm not into garbling myself, I can only vote up... $\endgroup$ – Maarten Bodewes Aug 4 '16 at 11:26
  • $\begingroup$ Possible duplicate of Offline Complexity of the garbling scheme $\endgroup$ – Bush Aug 8 '16 at 19:51
  • $\begingroup$ See my answer at crypto.stackexchange.com/questions/39225/… $\endgroup$ – Bush Aug 8 '16 at 19:52

The size of the randomized encoding (or garbled circuit) produced by a given construction will be specific to that construction. (Indeed, there are major efficiency improvements to GCs/REs that are still being discovered every year.) So, to answer your (own) question, it would require focusing on a particular construction's details to answer fully.

However -- Yes -- it must be the case that any garbled-circuit / RE that is output by any probabilistic polynomial-time $\mathsf{Garble}$ or $\mathsf{Encode}$ procedure has size at most $\mathsf{poly}(1^\lambda, C).$ For the procedure to output something significantly larger, e.g. exponential in $1^\lambda$ and $|C|$, is impossible (in prob. poly time). Moreover, the typical constructions that come to mind -- e.g. Yao's Garbled Circuits and Applebaum-Ishai-Kushilevitz's randomizing polynomials -- have size approximately $O(\lambda\cdot |C|).$ (It's likely that whatever you're looking at is 'loosely in this range,' though schemes close to the state-of-the-art will have various fine-grained differences..)

  • 1
    $\begingroup$ Thanks Daniel! yes, this question is arised from the paper "Adaptively secure garbled circuits from one-way function" that I'm investigating. Actually another reason why I ask this is that I'm imaging that is it possible to use a garbling scheme with sublinear complexity to build succinct (or weakly succinct) functional encryption. However, I know this idea is impossible now. Thanks again for your answer. $\endgroup$ – CryptoLover Aug 10 '16 at 10:09
  • $\begingroup$ Yikes! Personally, I recommend finding a more tractable research question xD (Attacking succinct and weakly succinct functional encryption head-on feels more and more like a complexity-theorist saying they'll tackle P vs NP head-on ;)) $\endgroup$ – Daniel Apon Aug 10 '16 at 10:11

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.