Heuristic for mapping Boolean circuit to TFHE functional bootstrapping

This repository contains the code used in paper A fast heuristic for mapping Boolean circuits to functional bootstrapping.

How to run the experiments

Preliminaries

Install the required python packages and go to the experiments directory:

pip3 install -r requirements.txt
cd experiments

Clone concrete library and patch it to support non power-of-two parameters:

git clone https://github.com/zama-ai/concrete.git -b nightly-2024.04.17
(cd concrete; git apply ../concrete.patch)

Note

A working Rust installation is required to compile concrete

Run the benchmarks

Install abc and libreadline (required to compile abc) libraries. abc is used to transform benchmarks to XAG (Xor-And Graph) circuits.

apt install libreadline-dev
bash install_abc.sh

Use the following script to execute all the benchmarks (it should take less than 24h 😄):

bash run_benchmarks.sh

The script creates a Makefile for each benchmark suite (epfl, iscas85, etc.). The targets in the makefile are the calls of the mapping heuristic with specific parameters. The output of each makefile execution is streamed to a log file (outputs/epfl.log for EPFL benchmarks, etc.). Use tail -f outputs/epfl.log to follow benchmark executions.

As example, in the EPFL benchmarking makefile (generated by gen_makefile_epfl.bash) the target (outputs/epfl/adder_15_search.fbs) will execute the "search" flavor of the mapping heuristic (../fbs_mapper/map_circuit.py --mapper search) on circuit benchmarks/epfl/arithmetic/adder.blif with functional bootstrapping size 15. The respective makefile lines:

...
outputs/epfl/adder_15_search.fbs outputs/epfl/adder_15_search.lbf outputs/epfl/adder_15_search.log: benchmarks/epfl/arithmetic/adder.blif | outputs/epfl
        python3 ../fbs_mapper/map_circuit.py benchmarks/epfl/arithmetic/adder.blif --fbs_size 15 --mapper search --output outputs/epfl/adder_15_search.fbs --output_lbf outputs/epfl/adder_15_search.lbf > outputs/epfl/adder_15_search.log 2>&1
...

Analyse results

The following script will interpret the mapping results obtained after the benchmarks execution and generate tables (latex code) and figures used in the paper.

cd outputs
python3 ../analyse_results.py

Note

The script analyse_results.py only outputs raw latex code (e.g. only latex table content is generated without table floats instructions)