There are a bunch of papers do research on resizable garbled circuits. But I wonder why garbled circuits cannot be reused?

For example, the constructor constructs a garbled circuit of "AND" like this:

$E_{K_{u}^0}(E_{K_{v}^0}(K_{w}^0))$, $E_{K_{u}^0}(E_{K_{v}^1}(K_{w}^0))$, $E_{K_{u}^1}(E_{K_{v}^0}(K_{w}^0))$, $E_{K_{u}^1}(E_{K_{v}^1}(K_{w}^1))$

Then he sends this garbled circuit and $K_{v}^0$, $K_{v}^1$ to the evaluator.

Every time, he wants to evaluate the garbled circuit with an input $b\in\{0,1\}$, he just sends $K_{u}^b$ to the evaluator.

Other than letting the evaluator know that he may have the same input in different evaluations, I cannot think of other revealed information.


1 Answer 1


One of the security guarantees of garbled circuits is that the evaluator doesn't learn anything about the circuit beyond the output on the given input. Executing more than one input string will break this property. For instance, if you allow him to evaluate two inputs, $0^n$ and $1^n$, then he can "mix and match" bits on each gate to determine what kind of gate it is. An AND gate will have three outputs which are the same, but an XOR will only have two, etc. Additionally, by doing this mix and match, he will be able to calculate the output value of the circuit on new inputs which you have not directly given to him. Combining these two advantages, it is also very likely that the will be able to recreate some or all of the bits of the input by tracing the circuit, since he learns the final output in plaintext.

  • $\begingroup$ Beside Yao's garbled circuit can't be reused. My question is it allow to assign different keys each time when garbled circuit is executed or keys are fixed $\endgroup$
    – Infinity
    Jan 27, 2017 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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