This repository contains all the code required to reproduce the experiments and regenerate the tables and figures from the paper Decomposition of Large Look-Up Tables for Fast Homomorphic Evaluation, published in TCHES 2026, Volume 3. Additionally, it provides a stand-alone tool to decompose a large LUT into a circuit of smaller LUTs using the technique introduced in the paper.

---

Overview of this Artifact

We provide the raw data files generated by our experiments, as well as decompositions for randomly generated S-boxes. The artifact allows users to regenerate the figures from the paper using these raw data files, and to rerun the experiments to regenerate the data.

The main features of the artifact are:

• Regenerate the plots and tables from the paper using the original raw data.
• Re-run all the experiments to regenerate the data and generate the corresponding plots.
• Benchmark the evaluation of our pre-generated decompositions, as well as the other techniques (classical PBS, Tree-Based Method, and WoP-PBS) on the same LUT sizes.
• Regenerate all the decompositions used in our benchmarks.

Additionally, we provide a stand-alone tool that allows users to generate the decomposition of any user-provided LUT.

---

Installation

The only prerequisites are Python and Rust. Rust can be installed with a single command by following the instructions at:

https://rust-lang.org/tools/install/

Then run:

make install

to install all dependencies.

Alternatively, you can use the provided Docker container:

docker build -t artifact-hlut-tches .
docker run -it \
    -v "$PWD":/artifact \
    artifact-hlut-tches bash

The project directory is bind-mounted into the container, so any figures and data files generated inside the container are automatically saved on the host machine.

---

Quick Reproduction

Reproducing the Plots

To regenerate all figures from the paper using the provided raw data, run:

make plots MODE=paper

The generated figures will be located in figures/paper and should match those in the paper.

Full Reproduction

To reproduce all experiments, run:

make reproduce

This command:

• Runs all benchmarks and experiments to regenerate the raw data files (stored in data/regenerated).
• Regenerates the figures from this data (stored in figures/regenerated).

This reproduction can take some time depending on your hardware. On our computing server, it takes approximately one hour.

Stand-alone Tool

The decomposition generation is not included in the full reproduction script, as it is computationally intensive. Instead, we provide a stand-alone tool to decompose any S-box.

Example:

make decompose S=2 P=3 N=8 GAMMA=1.05 SBOX_FILE=aes.sbox

This command generates a one-bit block decomposition of the AES S-box. The output is written to search/.

S-box file format

Provide the output values, in order, on a single line, separated by spaces. See aes.sbox for an example.

---

Hardware Requirements

Our experiments were run on the following hardware:

• CPU: AMD Ryzen Threadripper PRO 7995WX (96 cores)
• RAM: 500 GB
• OS: Debian GNU/Linux 13

---

Detailed Documentation

Decompositions

We provide the decompositions and S-boxes used in our experiments in:

decompositions/paper

To regenerate the decompositions for all supported sizes, run:

make decompositions

⚠️ This operation is computationally expensive for large sizes. For targeted use, we recommend using the stand-alone tool instead.

---

Plots and Tables

All plots and tables from the paper can be regenerated. The available outputs include:

• Figure 1 — Timing comparison with classical PBS
• Figure 5 — Distribution of matrix ranks $\mathcal{A}$ for varying $n$ and $\gamma$
• Figure 6 — Correlation between the margin from Equation 8 and the full-rank proportion
• Figure 8 — Exhaustive timing comparison with state-of-the-art methods
• Figure 9 — Timing results across output sizes
• Table 1 — Optimal matrix shape parameters
• Table 2 — Number of PBS operations per configuration
• Table 3 — Success rates with and without the encoding-switching optimization
• Table 4 — Timings for failure probability $2^{-40}$
• Table 5 — Timings for failure probability $2^{-128}$

Plots can be generated from either:

• paper (default): the original data used in the paper.
• regenerated: newly generated experimental data.

Run:

MODE=[paper|regenerated] make plots

---

Benchmarks

Four benchmarks are available:

• Our technique
• Tree-Based Method
• WoP-PBS
• Classical PBS (CJP)

Run them individually:

make hlut-full
make tbm
make wopppbs
make cjp

Or run all benchmarks at once:

make bench

For our method, the failure probability can be selected using:

• PERROR=40 → $p_{\mathrm{fail}} = 2^{-40}$ (default)
• PERROR=128 → $p_{\mathrm{fail}} = 2^{-128}$

To reproduce Figure 9 (smaller output sizes), run:

make hlut-partial

---

Experiments

The following experiments can be reproduced. The corresponding plots can then be generated using MODE=regenerated.

Figure 5

make experiments-ranks-distribution

Figure 6

make experiments-correlation-margin-ranks

Table 1

make experiments-shapes

Table 2

make experiments-count-pbs

Table 3

make experiments-encodings

Structure of the repository

• The folder decomposer contains the code that generate the decompositions. It also contains the code for the experiments (except for the benches). The tool is written in Python, with a binding with the gauss_elimination_rs crate that implements a higher performance Gauss algorithm implementation written in Rust.
• bench contains the four implementations we studied in the paper, as well as the code to banch them: our technique (in HLUT-rs), the classical programmable bootstapping (in bench_cjp), the tree-based method (in bench_tree_pbs) and finally the WoP-PBS (in bench_woppbs).
• The folder decompositions/paper contains the decomposition we generated for our experiments and that have been tested during our benchmark. The regenerated decompositions produced by the command make decompositions are stored in decompositions/regenerated. A similar structure is used in the folder data, that contains the results of our experiments and benchmarks.
• The folder figuresis meant to contain the regenerated figures, either from the data of the paper or from the results of the reproduction of the experiments.
• The folder search is used to store the outputs of the stand-alone tool make search.
• Finally, the folder parameters contains the TFHE parameter sets we used in our decompositions, for 40-bits and 128-bits error probabilities.