Vector Component-Wise Modular Multiplications in FHEW/AP & TFHE/GINX Bootstrapping

FHE Questions
1

Hi, there!
Does anyone know why the numbers of “vector component-wise modular multiplications” for FHEW/AP & TFHE/GINX bootstrapping estimated in https://dl.acm.org/doi/pdf/10.1145/3474366.3486924 would be the numbers marked in the figure below?

Suppose that in this case, the “vector component-wise modular multiplications” is defined as the multiplication of two Ring-LWE ciphertexts. (in evaluation format)

Besides, the matrix size in a Ring-GSW ciphertext is (2*d_g)*2, so what I supposed for the estimated number is 4*(1-(1/B_r))*n*d_r*d_g and 4*n*|U|*d_g (the monomial multiplications are not calculated in TFHE/GINX case).

I also traced the code in the function AddToAccCGGI but still not figure out the reason for the difference between my estimated numbers and the marked numbers.

image

2

Hi @Shiuan,

You are correct. These are typos in the paper (note that these expressions were not used in the complexity analysis/comparison). For FHEW/AP, there should be an extra factor of 2. Same for TFHE/GINX. So your expressions are accurate. Thanks for pointing this out.

1 Like