关键词: 全同态加密, 同态比较, 符号函数, 动态多项式, 深度消耗

Abstract: Fully homomorphic encryption extends encryption to computations, allowing ciphertext processing without decryption. Comparative operations, crucial in applications like deep learning, pose a challenge in homomorphic encryption environments restricted to addition and multiplication. Feng et al. (CNS 2023) proposed a comparison method using dynamic polynomial combinations. This paper enhances dynamic polynomial, allowing polynomial fluctuations within (-2,2). It introduces a novel equation system for solving dynamic polynomials and utilizes finite third and fifthdegree polynomials to construct more precise composite polynomials for approximating the sign function. It analyzes the method’s optimality in depth consumption and computational complexity, achieving a 32% reduction in runtime compared to the optimal method in a previous study (CNS 2023). The homomorphic comparison algorithm in this paper, for ε=2-20，α=20 requires only 0.69ms in amortized runtime.

Key words: fully homomorphic encryption, homomorphic comparison, sign function, dynamic polynomial, depth consumption