Determine what parts of Vos-Contri-Erkin 24 can be ported to HEIR

Jelle Vos, Mauro Conti, Zekeriya Erkin
_Depth-Aware Arithmetization of Common Primitives in Prime Fields._
https://eprint.iacr.org/2024/1200

They consider the "arithmetization" problem (i.e., converting high-level operations to add/mul for arithmetic FHE) from a very general viewpoint. They consider a more complex cost model than usual, with mul depth and total number of muls (with a little twist: they allow for tracking that squaring is usually cheaper than generic mul). However, afaik, they do not consider that multiplications get cheaper the "further down" they are (i.e., multiplying two fresh ctxts is often more expensive than multiplying a depth-l ctxt, after it's shed around l of its RNS limbs due to rescale/modswitch).

They give arithmetizations for logical operations (i.e., emulating Z_2 in Z_t for t > 2), exponentiations, arbitrary multiplication trees, etc and then show how that applies to optimizing things such as polynomial evaluation, equality checks, comparison, etc.

As an aisde, they also provide a rebalancing algorithm which they claim improves upon the one in EVA Improved (which @lawrencekhlim implemented in #878 as part of #836):

In addition to showing a few nice instances like the ones pictured above, they define/refine an optimization problem (something something changing from MILP to MaxSAT - this is more @j2kun's area of expertise so I must admit I skipped most of that) and produce a pareto front of circuits.
Finally, they briefly talk about how their approach is really only optimal for the operation in isolation, but not if, e.g., a comparison appears halfway "down" an FHE computation, though they provide some heuristics on how to handle this situation.

EDIT: Forgot to mention one of the biggest issue with this style of arithmetization, which is that it doesn't consider packing, i.e., frequently the plaintext moduli are not compatible with (full) CRT packing, and apart from HElib, few things even support such ptxt moduli (because it's often not worth sacrificing packing for slightly better arithmetization)

Start by reading the cited paper and the rebalancing work referenced in #878 and #836. Compare its arithmetization, rebalancing, and packing assumptions with HEIR's existing approach. Done means documenting which techniques are applicable and defining an implementation scope.

Written by the indexing model from the issue text.