How to determine the layers of a circuit?

Question

In many cryptographic applications like Multiparty Computation (MPC) or Fully Homomorphic Encryption (FHE), you consider a function $f$ described by a circuit over some algebraic structure, typically a field.

Now, it's very typical that the complexity of the algorithm heavily depends on the depth of the circuit, and not necessarily on its size. For instance, this is the case in Lattice-based FHE, in which low-depth is required in order to perform the bootstrapping, or in some non-constant round MPC protocols where the number of rounds depends on the depth of the circuit.

Given the above, I have two questions.

1. Given a circuit for $f$, how can we optimize to get a "shallower" circuit for the same $f$? Are there any tools/algorithms available for this purpose?
2. Suppose the circuit for $f$ if given as a list of gates, where each gate points to the gate or gates corresponding to its input. How can we determine the layers of the circuit from such representation? Are there any tools/algorithms for this as well?

The second point is particularly relevant for MPC, in which the communication for the gates in the same layer can be parallelized, providing a big improvement.

Thanks!

Answer 1

Given a circuit for f, how can we optimize to get a "shallower" circuit for the same f? Are there any tools/algorithms available for this purpose?

Researchers have already identified this is a relevant problem for MPC and FHE, where low-depth circuits make a big performance difference. Some works in this direction include [BDKK+18] and [BHWK16], and digging through their reference will reveal more work in that direction.

Some of the techniques in this area include adapting some optimization tools from circuit synthesis in the electrical engineering domain, and there are some other hand-crafted optimizations as well.

Suppose the circuit for f if given as a list of gates, where each gate points to the gate or gates corresponding to its input. How can we determine the layers of the circuit from such representation? Are there any tools/algorithms for this as well?

I know of two ways of achieving this.

Greedy algorithm

One that is very intuitive works as follows, at a high level. Take the input nodes and compute all the addition gates you can compute from these nodes without stumbling upon a multiplication gate. Then compute the multiplication gates that only depend on any of the gates found above (including the input gates). These gates have depth 1.

Then compute all the addition gates that depend on any of all the previous gates, and then compute the multiplication gates that depend only on the gates found up to this point. These have depth 2. This iteration is continued until all gates have been processed.

Using dynamic programming

This approach is considered in [KSS13]. To each edge $v_{ij}$ going from gate $g_i$ to gate $g_j$, assign a weight of $0$ if $g_j$ is an addition gate, and assign a weight of $-1$ if $g_j$ is a multiplication gate. Then, it is easy to see that the depth of a gate becomes the (negative of the) shortest distance from the gate to any of the input nodes. This can be computed via dynamic programming algorithms like Dijkstra algorithm.

---

• [BDKK+18] HyCC: Compilation of Hybrid Protocols for Practical Secure Computation (link)
• [BHWK16] Compiling Low Depth Circuits for Practical Secure Computation (link)
• [KSS13] An architecture for practical actively secure MPC with dishonest majority (link)

Answer 2

For many instances, the depth of the circuit is related directly to the arity of the logical gates from which is is built, or the arity of the subprotocols on which it depends. Considering the calculation of a protocol to find the product of an arbitrarily large set of values of magnitude $n$, and the existence of a binary multiplication protocol, meaning two inputs and one output, the depth of the circuit will require a circuit of multiplication gates of depth $\lceil \log_2 n \rceil$. In situations, such as this one there are algebraic means by which this may be transformed into a constant rounds operation, but this is only beneficial in most cases beyond a certain threshold of $n$. One result illustrating this technique for specifically constant rounds unbounded-fan-in multiplications is the work of Bar Ilan and Beaver here.

Answer 3

For question 2, I suspect this might be equivalent to a topological sorting algorithm, modified to keep track of the "depth" (i.e. the layer index) of the gates. It can be done in $O(n + m)$ time, where $n$ is the number of gates and $m$ is the number of wires.