# The Encode algorithm of Garbling scheme is probabilistic or deterministic?

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?

• @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. – CryptoLover Aug 6 '16 at 9:37