Improvements Of Homomorphic Evaluation Of Inverse Square Root And RNS Basis Conversion Algorithm Via RNS-CKKS Scheme With Implementation

Secure machine learning has attracted much attention recently.Inverse square root is widely used in machine learning,such as vector normalization,clustering,etc.So how to calculate the inverse square root securely has become an important issue.Panda proposed an iterative algorithm for homomorphic evaluation of inverse square root using CKKS homomorphic encryption scheme.The initial value of the iteration is selected as two straight lines intersecting at one point,which involves a very expensive homomorphic comparison operation.The RNS variant of CKKS utilizes the Chinese remainder theorem to accelerate operations,while introducing additional errors.RNS basis conversion is an essential operation of RNS-CKKS scheme.The original scheme uses a fast basis conversion algorithm to ensure the operation efficiency,but it sacrifices some precision.Halevi et al.proposed the use of additional floating-point arithmetic to eliminate errors in the RNS basis conversion process,but sacrificed some efficiency.At the same time,floating-point arithmetic itself has some defects such as complex chip design.Our work is divided into two aspects.First of all,We analyze the convergence interval of Newton iterative algorithm to the inverse square root approximation,and then propose two methods for selecting the initial value of the inverse square root Newton iterative algorithm.The initial values obtained by using these two methods can be located in the convergence interval of Newton iterative algorithm.Specifically,we use Taylor expansions and rational functions respectively as initial values,both of which avoid homomorphic comparison operations and significantly improve computational efficiency.The Taylor expansion method greatly reduces the initial value calculation consumption,but appropriately increases the number of Newton iterations.Compared with the Taylor expansion method,the rational function method cost more in the initial value calculation stage but reduces the number of Newton iterations.We conduct our experiment on the SEAL open source library and find that,while reaching the same accuracy,the total number of homomorphic levels consumed by the Taylor expansion method is about 83.3%of the best known results,and the rational function method is about 56.9%.Secondly,we improved the operation for eliminating errors during the RNS base switching process in the RNS-CKKS scheme.For the prime modulus selection method in the RNS-CKKS scheme,we replaced the expensive floating-point division with small integer modulus addition and subtraction,thereby improving the operational efficiency.And we propose an optimal parameter selection method,which can minimize the probability of error occurrence by selecting parameters in this way.We implemented our method on the PALISADE open source library and compared it with the original scheme and Halevi et al.’s method.The experimental results show that our method achieves the same accuracy as Halevi et al.’s method,and higher than the original scheme.The efficiency of our method is appropriately lower than that of the original scheme,but higher than that of Halevi et al.Our method can also be applied to RNSBGV and RNS-BFV schemes,and plays an active role in simplifying chip design.