Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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