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.
- 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?
- 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.