Distributive Property Optimization

[lawrencekhlim]

Given a tree of operations, say (ab + ac), reduce the number of operations by using the distributive property to obtain (a * (b + c)). Note that this provides the same error growth (we think, anyway) while eliminating one multiplication operation, decreasing the number of computations.

Another example, (ac + ad + b c + b d), it can be optimized into (a (c + d) + b (c + d)) and then even (a + b) * (c + d). The former has 4 multiplications and 4 additions while the latter only has 2 additions and 1 multiplication.

As far as I know, this has not been implemented as an optimization in homomorphic encryption compilers (but it may have already been explored by the broader compilers community).

See related issue for operation balancing #836.

[AlexanderViand-Intel]

I think some of the early compilers[^1][^2] looked at these kinds of rewrites, mostly from the perspective of reducing multiplicative depth rather than just number of multiplications, though. We evaluated a bunch of them in our compiler SoK[^3] (see Figure 2, where A/B/C/D are basically different flavors of this) and while there is some impact, it's pretty small. That doesn't mean we shouldn't do rewrites like this, but I do think they should only be tackled after things like ciphertext maintenance optimizations (these are so powerful because decreasing the parameters by, e.g., one RNS limb or dropping the degree from $2^k$ to $2^{k-1}$ makes every homomorphic operation in the program noticeably faster). Maybe we could realize this via a custom FHE-friendly canonicalization pass, which we switch to just before we distribute-generic, that implements a few of these as patterns?

[^1]: Carpov, S. et al. 2018. A Multi-start Heuristic for Multiplicative Depth Minimization of Boolean Circuits. Combinatorial Algorithms (2018), 275–286. [^2]: Aubry, P. et al. 2020. Faster Homomorphic Encryption is not Enough: Improved Heuristic for Multiplicative Depth Minimization of Boolean Circuits. Topics in Cryptology – CT-RSA 2020 (2020), 345–363. [^3]: Viand, A. et al. 2021. SoK: Fully Homomorphic Encryption Compilers. 2021 IEEE Symposium on Security and Privacy (SP) (May 2021), 1092–1108.

[asraa]

but I do think they should only be tackled after things like ciphertext maintenance optimizations

The intention here is to write some rewrite patterns for the intern project before doing larger optimizations, so I don't think we should hold off until we get optimizations that might result in parameter size reduction :)

We currently have the lazy relin pass in progress, and then we can also start working on a noise analysis pass that can reduce parameter sizing as well.

[AlexanderViand-Intel]

The intention here is to write some rewrite patterns for the intern project before doing larger optimizations, so I don't think we should hold off until we get optimizations that might result in parameter size reduction :)

I see! This should make for a nice "warm up" optimization then 👍