Efficient Lookup Tables for Carry Handling in TFHE

Code and scripts for the paper: Efficient Lookup Tables for Carry Handling in TFHE

Setup mean compensation implementation in the TFHE-rs library:

• Clone the TFHE-rs library: git clone https://github.com/zama-ai/tfhe-rs.git ; cd tfhe-rs
• Switch to the correct version (V1.1.0): git checkout 2cd16ac70af19308e7a4578083b4e2e3730964ca
• Copy the patch file and apply it to the repo: git apply ../dont_be_mean.patch

Setup parameter estimation script:

• Clone the lattice estimator by Albrecht et al.: cd parameterEstimation ; git clone https://github.com/malb/lattice-estimator.git
• Switch to the correct version: cd lattice-estimator ; git checkout 14a362513c9197dd959bc72428425abe0309779a ; cd ..
• Run the parameter estimation script using sage: sage -python parameterTest.py
• Change fixed parameters N, k (polynomial size and GLWE size) within the find_parameters function
• Change optimization requirements (security, error probability, usage of mean compensation) in the main function
• security_cache.pkl caches all security estimates that were generated before to accelerate the program. Remove this file and run parameterTest.py to rerun all lattice security estimates.

Setup for benchmarks:

• After cloning TFHE-rs and applying the Mean Compensation patch file, you can follow these steps to rerun all benchmarks from the paper. This patch file also contains the code for the optimizations.
• Copy the patch file and apply it to the repo: git apply setup_bench.patch
• Enter the folder with the TFHE-rs library: cd tfhe-rs
• For every benchmark run, first uncomment the correct parameter set for the scenario in tfhe-rs/tfhe/src/shortint/parameters/v1_1/classic/gaussian/p_fail_2_minus_128/ks_pbs.rs between line 319 and 432.
• Run 'make bench_integer' to benchmark the three-operand group state combination.
• Run 'make bench_integer' after copy-pasting the contents of the file tfhe-rs/tfhe/src/integer/server_key/radix_parallel/add_old.rs into tfhe-rs/tfhe/src/integer/server_key/radix_parallel/add.rs to benchmark the two-operand group state combination.
• Run 'make bench_shortint' to benchmark the single-bootstrap message and carry extraction. Uncomment the desired version for the extraction in tfhe-rs/tfhe/src/shortint/server_key/mod.rs between lines 1095 and 1234.
• Run 'make bench_shortint' to benchmark a single bootstrap with the currently selected parameter set.
• Run 'make test_altered_lut' to test the correctness of the three-operand group state combination, using the test case in tfhe-rs/tfhe/src/integer/server_key/radix_parallel/tests_unsigned/altered_lut_test.rs. This test also writes the PBS counts to output.txt, which was used to make the graphs in output.py.
• Run 'make test_double_extract' to test the correctness of the double extraction, using the test case in tfhe-rs/tfhe/src/integer/server_key/radix_parallel/tests_unsigned/double_extract_test.rs.

Setup single-bootstrap message and carry extract:

• After cloning TFHE-rs and applying the Mean Compensation patch file, you can follow these steps to enable single-bootstrap message and carry extraction.
• Copy the patch file and apply it to the repo: git apply double_extract.patch

Setup three-operand group state combination:

• After cloning TFHE-rs and applying the Mean Compensation patch file, you can follow these steps to enable three-operand group state combination.
• Copy the patch file and apply it to the repo: git apply three_operand_HS.patch