Boolean circuit: can the output wire of a gate be used by many different gates in the next layer?

Question

There are two typical secure multiparty computation paradigms using boolean circuits, namely garbled circuit and secret-sharing-based boolean computation. It is well-known that garbled circuits can be constructed layer by layer, in which each garbled gate has a fan-in of two and a fan-out of one (i.e., two input wires and one output wire). We have a similar construction in the secret-sharing-based boolean circuits. However, I failed to find any explicit comment whether an output wire of a gate can be used simultaneously by several gates in the next layer. In some available implementations of boolean circuits (e.g., this), no output wire is used more than once.

In my opinion, the reuse of an output wire does not undermine the security of the whole circuit since no information seems to be leaked by observing either the garbled gates or the secret-shared outputs. Am I wrong?

Answer 1

However, I failed to find any explicit comment whether an output wire of a gate can be used simultaneously by several gates in the next layer.

Of course you can do that.

In fact there are examples in the very repository you linked to, e.g. wire 3488 of the AES-128 implementation is used twice.

Answer 2

The other answer is correct in the sense that, yes, it is standard these days for garbled circuits to support high fan-out. But this was not always the case, and there is nothing fundamental about garbled circuits that automatically guarantees this.

The paper Foundations of Garbled Circuits was the first to systematize the notation and terminology of garbled circuits. They explicitly highlight the importance of being precise about the circuit model:

There are several reasons why it is important to cleanly define circuits (which, for many reasons, are not just DAGs). First, there are many “boundary cases” where only conventions can decide if something is or is not a valid circuit.${}^{8}$ The boundary cases matter; we have repeatedly found that degenerate or under-analyzed circuit types materially impact if a garbling scheme is correct.${}^{9}$ Beyond this, a lack of agreement on what a circuit is makes even informal discourse problematic.${}^{10}$

The footnotes in this section are quite illuminating. Footnote 9 especially gives two examples of fan-out being improperly handled in published schemes.

8. For example, can an input wire be an output wire? Can an output wire be an incoming wire to another gate? Can an output wire be used twice in forming the output? Can a wire twice feed a gate? Can constants feed a gate? Can gates compute asymmetric functions like $G(x,y) = \overline{x} \lor y$?

9. For example, the scheme of Naor, Pinkas, and Sumner cannot handle a wire being used twice as an input to another gate (as when making a NOT gate from a NAND), a restriction that is nowhere explicitly said. The scheme of Beaver, Micali, and Rogaway was buggy because of a dependency in gate-labels associated to fan-out $\ge$ 2 gates.

10. For example, is there a single wire emanating from each gate, that one wire connected to all gates it feeds, or is there a separate wire from the output of a gate to each gate it feeds? (For us, it’ll be the first.) These are very different meanings of wire

Since Foundations of Garbled Circuits, fan-out has generally not been a problem. The standard approach is to number the gates, and then include the gate number as a nonce in the cryptographic algorithms used to garble that gate. This ensures that there isn't any unexpected reuse of cryptographic material to garble different gates, even if the input wire labels are used in multiple gates.