TY - JOUR
T1 - Performance of hierarchical transforms in homomorphic encryption
T2 - a case study on logistic regression inference
AU - Alves, Pedro
AU - Nayara Ortiz, Jheyne
AU - Aranha, Diego F.
PY - 2023/9
Y1 - 2023/9
N2 - 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 discussion 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 performance 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 standalone implementation does not offer the same performances of 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 are 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.
AB - 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 discussion 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 performance 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 standalone implementation does not offer the same performances of 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 are 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.
KW - CKKS
KW - CUDA
KW - DGT
KW - Fully homomorphic encryption
KW - NTT
KW - Polynomial multiplication
KW - Privacy-preserving computing
UR - http://www.scopus.com/inward/record.url?scp=85163138869&partnerID=8YFLogxK
U2 - 10.1007/s13389-023-00325-1
DO - 10.1007/s13389-023-00325-1
M3 - Journal article
SN - 2190-8508
VL - 13
SP - 295
EP - 310
JO - Journal of Cryptographic Engineering
JF - Journal of Cryptographic Engineering
IS - 3
ER -