FINAL全同态加密方案的自举优化技术

来源：电子与信息学报杂志2025年第7期北京时间：

作者：赵秀凤, 吴蒙, 宋巍涛

单位：信息工程大学密码工程学院 郑州 450001

摘要：自举是实现全同态加密的有效方法，同时也是影响全同态加密效率的关键环节。FINAL方案是2022年亚密会提出的全同态密码方案，比TFHE方案自举速度快28%，可以进行高效的同态布尔运算。自举主要包括盲旋转算法和密钥转换算法。针对盲旋转算法，该文提出累加器压缩方法，即对基于容错学习(LWE)的加密方案的密钥生成引入块二进制分布，利用块二进制密钥特性，使得密钥的每个分块只需进行1次外积运算，减少盲旋转算法所需的外积数量。针对密钥转换算法，给出了密钥复用技术，即在生成NGS密钥时复用LWE密钥且复用部分不参与密钥转换的密钥生成，减小了密钥转换密钥规模，进而减少密钥转换算法运算次数，提高了密钥转换算法的效率。分析表明，在安全性相当的情况下，优化的FINAL方案自举所需要执行的外积数量和快速傅里叶变换的数量分别由610和3 940减少到305和1 970，数量上优化50%。密钥转换密钥规模由11 264减少到4 554，密钥转换中标量乘法以及标量加法的运算次数大约由13.8×106减少到5.6×106，密钥转换的密钥规模和计算开销均优化约60%。

关键词：全同态加密, FINAL, 自举, 盲旋转, 密钥转换

基金资助：国家密码科学基金(2025NCSF02044)，先进计算与智能工程(国家级)实验室基金(2023-LYJJ-01-002)