Multiplicative and Additive Balancing

[lawrencekhlim]

Given a tree of associative operations, say (((a b) c) d), then rebalance the tree to be (a b) (c d). This improves performance because the latter lowers the multiplicative depth by one. One can implement the algorithm provided in this paper: https://eprint.iacr.org/2021/1505.pdf.

This can also be useful for Additive Operations because it means that Additive Operations can be parallelized with better performance.

EDIT: This issue is addressed by #878, see below for more TODOs for a starter project. See also #837 for a distributive property optimization.

[AlexanderViand-Intel]

Sorry, I didn't see this before replying on #837 so I'll just leave a link to my comment there: https://github.com/google/heir/issues/837#issuecomment-2257586402

[lawrencekhlim]

This issue is addressed by PR #878, but there are more improvements that can be done, which are left as future tasks:

• The code currently works at the arith dialect for arith.muli (multiplication) and arith.addi (addition). We should add analysis for which operands are secret (and hence, encrypted) and which operands are not secret, to sort by those types of operands and perform plaintext operations first. This also minimizes the number of encodings needed.
• The code makes an implicit assumption that intermediate operands have the same operation depth as other operands. See comments inside OperationBalancer.cpp for more details for how to improve on this.
• Lastly, the code does not optimize the global depth of operations if there are intermediate operations. What may happen in this case is that reducing the global depth may come at the cost of extra operations are added.