International Association for Cryptologic Research

International Association
for Cryptologic Research

Transactions on Cryptographic Hardware and Embedded Systems 2025

Faster amortized bootstrapping using the incomplete NTT for free


README

Faster amortized bootstrapping using the incomplete NTT for free

Thales B. Paiva, Gabrielle de Micheli, Syed Mahbub Hafiz, Marcos A. Simplicio Jr, and Bahattin Yildiz.
"Faster amortized bootstrapping using the incomplete NTT for free."
IACR Transactions on Cryptographic Hardware and Embedded Systems (2025/4).

The paper is also available in the IACR ePrint: https://eprint.iacr.org/2025/696.pdf

This repository contains the code and data for our paper.
The code is largely based on the code provided by Guimarães, Pereira and Van Leeuwen (2023).

Guimarães, Antonio, Hilder VL Pereira, and Barry Van Leeuwen. "Amortized bootstrapping
revisited: Simpler, asymptotically-faster, implemented." International Conference on the
Theory and Application of Cryptology and Information Security. Singapore: Springer
Nature Singapore, 2023.

Our changes were done specifically to introduce the homomorphic incomplete NTT into
their code, together with the embedding of the base multiplication as described in our
paper.
This required us to make change the following files:

To enable the testing for multiple parameters, we refactored their main_amortized.cpp version, obtaining the file main_amortized_csv.cpp.
This generates an executable that takes multiple parameters and outputs a CSV
with information such as bootstrapping time and DFR, that was used in our paper.
This is the main entry point to our code.

Furthermore, we also used OpenMP to parallelize some trivially parallel sections.
IMPORTANT: For the performance, we used single-threaded experiments
(i.e. running export OMP_NUM_THREADS=1 before calling running the program).
This is important to make them comparable to the other schemes.

Setup

To be able to run all experiments, we recommend using a setup with at
least 128 GB of RAM.
Important: The code is x86-specific.
We also recommend running on an Intel x86 processor supporting AVX2/AVX512
to get the best the best performance from the Intel HEXL library.

We tested our code in the following setup:

$ grep "model name" /proc/cpuinfo | head -n1
model name  : Intel(R) Xeon(R) Platinum 8260 CPU @ 2.40GHz
$ grep  MemTotal /proc/meminfo
MemTotal:       262718148 kB
$ uname -a
Linux 5.15.0-72-generic #79~20.04.1-Ubuntu SMP Thu Apr 20 22:12:07 UTC 2023 x86_64 x86_64 x86_64 GNU/Linux
$ cmake --version | head -n 1
cmake version 3.16.3

Compiling and running the code

To compile:

$ make hexl
$ make

This will generate an executable main_amortized with the following usage:

$ ./main_amortized
Usage: ./main_amortized <prime_p> <n_message_bits> <N> <NTT_INCOMPLETENESS> <INTT_QUADRATIC_LEVEL> <l> <p_star_size> <key_hw>

Reproducing our results

We include a simple shell script to reproduce our results.
You can run it with the following command line.

$ ./scripts/run_amortized_bootstrap_experiments.sh results_file.csv

Expected running time: This takes roughly 4.5 hours to run on a
single-thread.

Important: From this output, you should be able to build a file results_file.csv somewhat similar to results/results.csv.
The values won't be equal, because the encryption uses true randomness from the OS.
Furthermore, results/results.csv contains 10 runs for each parameter set for us to be able to get a more accurate estimate on the bootstrapping time, while results_file.csv is generated using 1 run for each parameter set.

The file results_file.csv can be generated by setting N_BATCHES=10 inside
./scripts/run_amortized_bootstrap_experiments.sh.
This will take a long time: 10 x 4.5 = 450 hours to run on a
single-thread.
It will result in a CSV file like this:

$ head results/results.csv
modulus_p,NTT_INCOMPLETENESS,INTT_QUADRATIC_LEVEL,N,l,bit_size,p_start_size,key_hw,N_prime,n_message_bits,std_err,dfr,OMP_NUM_THREADS,bootstrapping_time_ms
12289,4,6,1024,3,49,24,256,32768,8,0.000000,0.000000,1,1257850.9200
7681,4,6,1024,3,49,24,256,16384,8,0.031250,0.000977,1,615660.2310
7937,4,6,1024,3,49,24,256,16384,8,0.031250,0.000977,1,598705.0620
16001,4,6,1024,3,49,24,256,32768,8,0.000000,0.000000,1,1348756.4580
7681,4,6,2048,3,49,27,52,16384,8,0.000000,0.000000,1,1762879.4800
7937,4,6,2048,3,49,27,52,16384,8,0.000000,0.000000,1,1834858.4790
12289,4,6,2048,3,49,27,52,32768,8,0.000000,0.000000,1,3850488.1510
15361,4,6,2048,3,49,27,52,32768,8,0.000000,0.000000,1,3962857.0540
12289,4,6,1024,3,49,24,256,32768,8,0.000000,0.000000,1,1284641.2710
...
...
...

Original performance of GPVL:
In the current state of our repo, there is no way to run the exact original algorithm
by Guimarães et al.. Therefore, you will have to download it and run it separately.
However, since the running time of the algorithm severely depends
on p and INTT_QUADRATIC_LEVEL, not in NTT_INCOMPLETENESS, we remark that
the numbers observed for their prime p = 12289 should not differ much from
what we get in these lines:

12289,4,6,1024,3,49,24,256,32768,8,0.000000,0.000000,1,1257850.9200
12289,4,6,2048,3,49,27,52,32768,8,0.000000,0.000000,1,3850488.1510

Implementation of the two-part inverse incomplete NTT

The core operations of our two-part incomplete NTT are on file
amortized_boostrap_general.cpp.
This required largely refactoring the source code file from Guimarães
et al., which, we copy in the repo to allow for an easy comparison
(their version can be seen in amortized_boostrap_ORIGINAL_GPVL.cpp)

To explore how we implement the two-part inverse incomplete NTT, we recommend
you start by function _intt_rlwe_two_parts_matrix, where the functions
performing each part are clearly marked.

void _intt_rlwe_two_parts_matrix(RNSc_RLWE * tv, RNS_GSW * p, uint64_t * in_consts,
                           RNSc_half_GSW * acc, uint64_t n,
                           RNS_RLWE_KS_Key * aut_ksk,
                           RNS_RLWE_KS_Key * priv_ksk){

  const uint64_t Q = p[0]->samples[0]->b->Q;

  uint64_t ws[n];
  uint64_t ws_inverse[n];
  uint64_t root_of_unity = intel::hexl::MinimalPrimitiveRoot((2 * n) >> NTT_INCOMPLETENESS, Q);
  calcRootsOfUnit(ws, root_of_unity, Q, n);
  calcRootsOfUnit(ws_inverse, intel::hexl::InverseMod(root_of_unity, Q), Q, n);

  fprintf(stderr, "Part 1 of the INTT (n = %ld, NTT_INCOMPLETENESS = %d).\n", n, NTT_INCOMPLETENESS);
  fflush(stderr);
  MEASURE_TIME("", 1, "   -> ", {
  intt_negacyclic_part1_quadratic(p, in_consts, acc, ws, n, n, aut_ksk, priv_ksk);
  })

  fprintf(stderr, "Part 2 of the INTT\n");
  fflush(stderr);
  MEASURE_TIME("", 1, "   -> ", {
  intt_negacyclic_part2_quadratic_rnsc_rlwe(tv, p, ws, n, n, aut_ksk, priv_ksk);
  })
}

Starting from there, one can then explore our implementation of the two parts
below in more depth:

License

This project is licensed under the Apache License, Version 2.0

It includes code from:

This repository introduces the following modifications by LG Electronics, Inc. 2025: