Paper 2022/099

Performance of Hierarchical Transforms in Homomorphic Encryption: A case study on Logistic Regression inference

Pedro Geraldo M. R. Alves, Jheyne N. Ortiz, and Diego F. Aranha


Recent works challenged the Number-Theoretic Transform (NTT) as the most efficient method for polynomial multiplication in GPU implementations of Fully Homomorphic Encryption schemes such as CKKS and BFV. In particular, these works argue that the Discrete Galois Transform (DGT) is a better candidate for this particular case. However, these claims were never rigorously validated, and only intuition was used to argue in favor of each transform. This work brings some light on the dis- cussion by developing similar CUDA implementations of the CKKS cryptosystem, differing only in the underlying transform and related data structure. We ran several experiments and collected perfor- mance metrics in different contexts, ranging from the basic direct comparison between the transforms to measuring the impact of each one on the inference phase of the logistic regression algorithm. Our observations suggest that, despite some specific polynomial ring configurations, the DGT in a stan- dalone implementation does not offer the same performance as the NTT. However, when we consider the entire cryptosystem, we noticed that the effects of the higher arithmetic density of the DGT on other parts of the implementation is substantial, implying a considerable performance improvement of up to 15% on the homomorphic multiplication. Furthermore, this speedup is consistent when we consider a more complex application, indicating that the DGT suits better the target architecture.

Available format(s)
Publication info
Preprint. MINOR revision.
NTTDGTFully Homomorphic EncryptionCKKSCUDAPolynomial multiplicationPrivacy-preserving computing
Contact author(s)
pedro alves @ ic unicamp br
jheyne ortiz @ ic unicamp br
dfaranha @ cs au dk
2022-01-31: received
Short URL
Creative Commons Attribution


      author = {Pedro Geraldo M.  R.  Alves and Jheyne N.  Ortiz and Diego F.  Aranha},
      title = {Performance of Hierarchical Transforms in Homomorphic Encryption: A case study on Logistic Regression inference},
      howpublished = {Cryptology ePrint Archive, Paper 2022/099},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.