google / google/heir

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

Open
#1,104 0 comments 0 reactions 0 assignees View on GitHub
research synthesis
Dominant language
MLIR
Stars
906
Forks
171
Avg merge
4d 12h
Merged PRs (30d)
32

Description

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

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.