### Optimization of Homomorphic Comparison Algorithm on RNS-CKKS Scheme

Eunsang Lee, Joon-Woo Lee, Young-Sik Kim, and Jong-Seon No

##### Abstract

Since the sign function can be used to implement the comparison operation, max function, and rectified linear unit (ReLU) function, several studies have been conducted to efficiently evaluate the sign function in the Cheon-Kim-Kim-Song (CKKS) scheme, one of the most promising fully homomorphic encryption schemes. Recently, Lee et al. (IEEE Trans. Depend. Sec. Comp.) proposed a practically optimal approximation method of sign function on the CKKS scheme using a composition of minimax approximate polynomials. However, homomorphic comparison, max function, and ReLU function algorithms that use this approximation method have not yet been successfully implemented on the residue number system variant CKKS (RNS-CKKS) scheme, and the sets of degrees of the component polynomials used by the algorithms are not optimized for the RNS-CKKS scheme. In this paper, we propose the optimized homomorphic comparison, max function, and ReLU function algorithms on the RNS-CKKS scheme using a composition of minimax approximate polynomials for the first time. We propose a fast algorithm for inverse minimax approximation error, a subroutine required to find the optimal set of degrees of component polynomials. This proposed algorithm makes it possible to find the optimal set of degrees of component polynomials with higher degrees than the previous study. In addition, we propose a method to find the degrees of component polynomials optimized for the RNS-CKKS scheme using the proposed algorithm for inverse minimax approximation error. We successfully implement the homomorphic comparison, max function, and ReLU function algorithms on the RNS-CKKS scheme with a low comparison failure rate ($< 2^{-15}$) and provide the various parameter sets according to the precision parameter $\alpha$. We reduce the depth consumption of the homomorphic comparison, max function, and ReLU function algorithms by one depth for several $\alpha$. In addition, the numerical analysis demonstrates that the proposed homomorphic comparison, max function, and ReLU function algorithms reduce running time by 6%, 7%, and 6% on average compared with the previous best-performing algorithms, respectively.

Available format(s)
Publication info
Preprint. Minor revision.
Keywords
Cheon-Kim-Kim-Song (CKKS) schemefully homomorphic encryption (FHE)homomorphic comparison operationminimax approximate polynomialRemez algorithm
Contact author(s)
eslee3209 @ ccl snu ac kr
shaeunsang @ snu ac kr
History
Short URL
https://ia.cr/2021/1215

CC BY

BibTeX

@misc{cryptoeprint:2021/1215,
author = {Eunsang Lee and Joon-Woo Lee and Young-Sik Kim and Jong-Seon No},
title = {Optimization of Homomorphic Comparison Algorithm on RNS-CKKS Scheme},
howpublished = {Cryptology ePrint Archive, Paper 2021/1215},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1215}},
url = {https://eprint.iacr.org/2021/1215}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.