Performance of hierarchical transforms in homomorphic encryption: A case study on logistic regression inference

In this work, we describe our efforts to resume the investigation by [BVA18] on the possible advantages of replacing the NTT with the DGT for the implementation of polynomial multiplication in FHE cryptosystems. In particular, we target results claiming that the DGT is more suitable than NTT for GPUs and memory-bounded platforms [BPA+ 21]. A full version of this work was published originally at [AOA22]. To the best of our knowledge, no previous work provided a deep analysis of the advantages of each transform in the context of GPU execution.