In general the garbling scheme works as follows:

  • $\textrm{Garb}(1^\lambda, C)$: on input the security parameter $\lambda$ in unary and the circuit $C$, it outputs a garbled circuit $\widehat{C}$ and a garbling key $K$

  • $\textrm{Encode}(x, K)$: on input the input value $x$ and the garbling key $K$, it outputs a garbled input $\widehat{x}$

  • $\textrm{Eval}(\widehat{C}, \widehat{x})$ outputs the result of $C(x)$

My question is whether the second algorithm "Encode" is probabilistic or not? I reviewed some papers and most of them indicate it is deterministic, but some of them think it is probabilistic. I'm currently in confusion about this, please give your best illustration why it is probabilistic or deterministic?


I don't know of any Yao-type garbling scheme where Encode is probabilistic. Think about Yao circuits - the encoding is providing the garbled key on the input wire for the associated bit. Note that the garbling is of course probabilistic and must be. However, once the garbling is fixed, the encoding is typically deterministic.

Having said the above, as a way of defining things, it is better to define it as probabilistic. This is due to the fact that although we don't know of any probabilistic way now, it doesn't mean that in the future there won't be. Since any deterministic algorithm is also (vacuously) probabilistic, this is more general.

This can also explain the confusion. As a definition, probabilistic is more general and thus preferable. But, in practice, Yao garbling using deterministic encodings until now.

  • 1
    $\begingroup$ Though wlog, the garbling key K can contain any randomness that Encode needs, no? So it doesn't much matter in this definition. $\endgroup$ Jul 13 '16 at 11:36
  • $\begingroup$ Good point. This is correct. $\endgroup$ Jul 13 '16 at 11:44
  • $\begingroup$ @YehudaLindell I have one more question about the randomness in the garbling key $K$: Can we derandomize the garbling key using PRF? that is $Encode(x, K; PRF(r))$ ? However, usually we define input encoding as a deterministic algorithm so it seems we do not have to derandomize it. This is my question and hopefully you can answer it. $\endgroup$ Aug 6 '16 at 9:37

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.