Investigate optimizations from "A fast heuristic for mapping Boolean circuits to functional bootstrapping"

[asraa]

https://eprint.iacr.org/2024/1204

This paper talks about an incremental gate merge technique to map a boolean circuit to a low number of functional bootstrapping. The heuristics uses a fixed max bootstrapping size. The technique heavily utilizes negacyclic bootstraps to reduce the max plaintext size needed to represent the merged gates and also non-power-of-two plaintext size (which will increase noise).

Some things they don't do:

• Incorporate multi-output PBS optimizations
• Multi-threading (HEIR can help - it codegens parallel code!)
• Execute (not simulate) results (HEIR can help!)
• Incorporate heuristics line gates with high fan-outs to be more likely to bootstrap to save # of total bootstraps
• Booleanizing arithmetic programs or high level programs (HEIR can help!)

If this pass was integrated into HEIR via an MLIR Pass after Yosys booleanization, then we should be able to codegen tfhe-rs (using the lower level core crypto API) or other code to execute the results.

cc @ssmiler