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

摘要： 同态加密方案的比较运算是深度学习等多种应用中常见的操作之一.已有研究专注于同态比较运算，以有效评估同态加密方案.在仅支持加法和乘法运算的同态加密环境中，对数据执行比较操作一直是具有挑战性的非算术任务.对之前(2023 CNS)的动态多项式比较方法进行改进，即多项式波动范围能够落在(-2,2)，找到全新的方程组求解动态多项式.同时利用有限3次和5次多项式构建新的复合多项式，以更加精确和高效地逼近符号函数.分析该近似方法的深度消耗和计算复杂性方面的最优性，在平摊运行时间内(对于ε=2-α，α=20)需要0.69ms，相比之前(2023 CNS)最优方法减少了约32%的运行时间.

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