基于RLWR的同态加密方案的密钥切换技术

doi:10.3969/j.issn.1671-1122.2025.12.011

信息网络安全 ›› 2025, Vol. 25 ›› Issue (12): 1961-1974.doi: 10.3969/j.issn.1671-1122.2025.12.011

基于RLWR的同态加密方案的密钥切换技术

秦思滢¹(), 孙兵¹^,², 付绍静²^,³, 唐小妹²^,⁴

1.国防科技大学理学院，长沙 410073
2.国防科技大学密码研究中心，长沙 410073
3.国防科技大学计算机学院，长沙 410073
4.国防科技大学电子科学学院，长沙 410073

收稿日期:2025-09-11 出版日期:2025-12-10 发布日期:2026-01-06
通讯作者: 秦思滢 E-mail:2608285657@qq.com
作者简介:秦思滢（2001—），女，安徽，硕士研究生，主要研究方向为全同态加密|孙兵（1981—），男，江苏，教授，博士，主要研究方向为密码分析|付绍静（1984—），男，江西，教授，博士，CCF会员，主要研究方向为密码学、区块链|唐小妹（1982—），女，江苏，教授，博士，主要研究方向为卫星导航
基金资助:
国家自然科学基金(62032009)

Key Switching for Somewhat Homomorphic Encryption Based on RLWR

QIN Siying¹(), SUN Bing¹^,², FU Shaojing²^,³, TANG Xiaomei²^,⁴

1. School of Science, National University of Defense Technology, Changsha 410073, China
2. Cryptography Research Center, National University of Defense Technology, Changsha 410073, China
3. School of Computer of Science, National University of Defense Technology, Changsha 410073, China
4. School of Electronic Science and Technology, National University of Defense Technology, Changsha 410073, China

Received:2025-09-11 Online:2025-12-10 Published:2026-01-06
Contact: QIN Siying E-mail:2608285657@qq.com

摘要/Abstract

摘要：

当前，基于RLWR的全同态加密方案中，密钥切换技术的系统性研究仍显匮乏。现有工作主要集中于密文相乘后导致的维数扩张问题，即通过密钥切换恢复密文维数，对于旋转及其他操作所需的密钥切换方案仍缺乏系统性研究。文章针对RLWR-SHE方案的结构特点，对密钥切换技术进行了系统研究。文章改进了经典密钥切换方案，使其适配RLWR-SHE的同态运算需求。针对该方案引入的噪声较大问题，文章根据当前主流的降噪思路，即系数分解法、模数扩展法以及两者的结合来改进密钥切换方案。通过对不同方案引入的误差进行理论分析与比较发现，系数分解法与模数扩展法的结合（即混合型密钥切换方案）的噪声控制效果最优，但其计算复杂度与维度扩展略有增加。文章为RLWR-SHE提供了更灵活的密钥切换方案，用户可根据实际需求（如误差范围或效率要求）选择适配方案。

关键词: 全同态加密, RLWR, 密钥切换, 噪声分析

Abstract:

Currently, systematic research on key switching techniques in homomorphic encryption schemes based on RLWR remains relatively scarce. Existing work primarily focuses on the dimension expansion issue resulting from ciphertext multiplication, where key switching is used to restore the ciphertext dimension. However, there is still a lack of systematic investigation into key switching schemes required for operations such as rotation. This paper conducted a systematic study of key switching techniques by leveraging the structural characteristics of the RLWR-SHE scheme. The classical key switching scheme was improved to adapt it to the homomorphic computation requirements of RLWR-SHE. To address the issue of significant noise introduced by this scheme, this paper modify the key switching approach based on mainstream noise reduction strategies, namely the coefficient decomposition technique, modulus extension method, and their combination. Through theoretical analysis and comparison of the errors associated with different schemes, the hybrid key switching approach, which combined coefficient decomposition and modulus extension, offered the best noise control. However, it slightly increased computational complexity and dimension expansion. This study provides more flexible key switching options for RLWR-SHE, allowing users to select an appropriate scheme based on practical requirements such as error tolerance or efficiency demands.

Key words: fully homomorphic encryption, RLWR, key switching, noise analysis

中图分类号:

TP309

秦思滢, 孙兵, 付绍静, 唐小妹. 基于RLWR的同态加密方案的密钥切换技术[J]. 信息网络安全, 2025, 25(12): 1961-1974.

QIN Siying, SUN Bing, FU Shaojing, TANG Xiaomei. Key Switching for Somewhat Homomorphic Encryption Based on RLWR[J]. Netinfo Security, 2025, 25(12): 1961-1974.

图/表 2

表1

表2

参考文献 32

[1]	RIVEST R L, ADLEMAN L, DEAOUZOS M L. On Data Banks and Privacy Homomorphism[J]. Foundations of Secure Computation, 1978, 4(11): 169-180.
[2]	GENTRY C. Fully Homomorphic Encryption Using Ideal Lattices[C]// ACM. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. New York: ACM, 2009: 169-178.
[3]	BRAKERSKI Z, VAIKUNTANATHAN V. Efficient Fully Homomorphic Encryption from (Standard) LWE[J]. SIAM Journal on Computing, 2014, 43(2): 831-871. doi: 10.1137/120868669 URL
[4]	GENTRY C, SAHAI A, WATERS B. Homomorphic Encryption from Learning with Errors:Conceptually-Simpler, Asymptotically-Faster, Attribute-Based[C]// Springer. Advances in Cryptology- CRYPTO 2013. Heidelberg: Springer, 2013: 75-92.
[5]	BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V. (Leveled) Fully Homomorphic Encryption without Bootstrapping[C]// ACM. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. New York: ACM, 2012: 309-325.
[6]	HU Mingxing, YE Qing, TANG Yongli. Efficient Batch Identity-Based Fully Homomorphic Encryption Scheme in the Standard Model[J]. IET Information Security, 2018, 12(6): 475-483. doi: 10.1049/ise2.v12.6 URL
[7]	BENARROCH D, BRAKERSKI Z, LEPOINT T. FHE over the Integers: Decomposed and Batched in the Post-Quantum Regime[C]// Springer. IACR International Workshop on Public Key Cryptography. Heidelberg: Springer, 2017: 271-301.
[8]	BRAKERSKI Z, VAIKUNTANATHAN V. Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages[C]// Springer. Advances in Cryptology- CRYPTO 2011. Heidelberg: Springer, 2011: 505-524.
[9]	FAN Junfeng, VERCAUTEREN F. Somewhat Practical Fully Homomorphic Encryption[EB/OL]. (2012-05-11)[2025-08-28]. https://dblp.org/rec/journals/iacr/FanV12. html.
[10]	GENTRY C, HALEVI S, SMART N P. Homomorphic Evaluation of the AES Circuit[C]// Springer. Advances in Cryptology- CRYPTO 2012. Heidelberg: Springer, 2012: 850-867.
[11]	GENTRY C, HALEVI S, SMART N P. Better Bootstrapping in Fully Homomorphic Encryption[C]// Springer. Public Key Cryptography- PKC 2012. Heidelberg: Springer, 2012: 1-16.
[12]	GENTRY C, HALEVI S, SMART N P. Fully Homomorphic Encryption with Polylog Overhead[C]// Springer. Advances in Cryptology- EUROCRYPT 2012. Heidelberg: Springer, 2012: 465-482.
[13]	DUCAS L, MICCIANCIO D. FHEW: Bootstrapping Homomorphic Encryption in Less than a Second[C]// Springer. Advances in Cryptology - EUROCRYPT 2015. Heidelberg: Springer, 2015: 617-640.
[14]	CHILLOTTI I, GAMA N, GEORGIEVA M, et al. TFHE: Fast Fully Homomorphic Encryption over the Torus[J]. Journal of Cryptology, 2020, 33(1): 34-91. doi: 10.1007/s00145-019-09319-x
[15]	CHEON J H, KIM A, KIM M, et al. Homomorphic Encryption for Arithmetic of Approximate Numbers[C]// Springer. Advances in Cryptology- ASIACRYPT 2017. Heidelberg: Springer, 2017: 409-437.
[16]	MICCIANCIO D, WALTER M. Gaussian Sampling over the Integers:Efficient, Generic, Constant-Time[C]// Springer. Advances in Cryptology- CRYPTO 2017. Heidelberg: Springer, 2017: 455-485.
[17]	BANERJEE A, PEIKERT C, ROSEN A. Pseudorandom Functions and Lattices[C]// Springer. Advances in Cryptology- EUROCRYPT 2012. Heidelberg: Springer, 2012: 719-737.
[18]	ALWEN J, KRENN S, PIETRZAK K, et al. Learning with Rounding, Revisited[C]// Springer. Advances in Cryptology- CRYPTO 2013. Heidelberg: Springer, 2013: 57-74.
[19]	BOGDANOV A, GUO Siyao, MASNY D, et al. On the Hardness of Learning with Rounding over Small Modulus[C]// Springer. Theory of Cryptography. Heidelberg: Springer, 2016: 209-224.
[20]	ALPERIN-SHERIFF J, APON D. Dimension-Preserving Reductions from LWE to LWR[EB/OL]. (2016-06-06)[2025-08-28]. https://ia.cr/2016/589.
[21]	COSTACHE A, SMART N P. Homomorphic Encryption without Gaussian Noise[EB/OL]. (2017-02-23)[2025-08-28]. https://ia.cr/2017/163.
[22]	LUO Fucai, WANG Fuqun, WANG Kunpeng, et al. Fully Homomorphic Encryption Based on the Ring Learning with Rounding Problem[J]. IET Information Security, 2019, 13(6): 639-648. doi: 10.1049/iet-ifs.2018.5427
[23]	GENTRY C, PEIKERT C, VAIKUNTANATHAN V. Trapdoors for Hard Lattices and New Cryptographic Constructions[C]// ACM. Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. New York: ACM, 2008: 197-206.
[24]	BOLBOCEANU M, COSTACHE A, HALES E, et al. Designs for Practical SHE Schemes Based on Ring-LWR[EB/OL]. (2024-06-17)[2025-08-28]. https://ia.cr/2024/960.
[25]	KIM A, POLYAKOV Y, ZUCCA V. Revisiting Homomorphic Encryption Schemes for Finite Fields[C]// Springer. Advances in Cryptology- ASIACRYPT 2021. Heidelberg: Springer, 2021: 608-639.
[26]	REGEV O. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[C]// ACM. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing. New York: ACM, 2005: 84-93.
[27]	LYUBASHEVSKY V, PEIKERT C, REGEV O. On Ideal Lattices and Learning with Errors over Rings[C]// Springer. Advances in Cryptology- EUROCRYPT 2010. Heidelberg: Springer, 2010: 1-23.
[28]	STEHLÉ D, STEINFELD R, TANAKA K, et al. Efficient Public Key Encryption Based on Ideal Lattices[C]// Springer. Advances in Cryptology- ASIACRYPT 2009. Heidelberg: Springer, 2009: 617-635.
[29]	CHEON J H, KIM D, LEE J, et al. Lizard: Cut off the Tail! A Practical Post-Quantum Public-Key Encryption from LWE and LWR[C]// Springer. Security and Cryptography for Networks. Heidelberg: Springer, 2018: 160-177.
[30]	D’ANVERS J P, KARMAKAR A, SINHA ROY S, et al. Saber: Module-LWR Based Key Exchange, CPA-Secure Encryption and CCA-Secure KEM[C]// Springer. Progress in Cryptology- AFRICACRYPT 2018. Heidelberg: Springer, 2018: 282-305.
[31]	Microsoft. Microsoft SEAL (Release 4.1)[EB/OL]. [2025-08-28]. https://github.com/Microsoft/SEAL.
[32]	COSTACHE A, LAINE K, PLAYER R. Evaluating the Effectiveness of Heuristic Worst-Case Noise Analysis in FHE[C]// Springer. Computer Security - ESORICS 2020. Heidelberg: Springer, 2020: 546-565.

指标	经典方案	BV型方案	GHS型方案	混合型方案
误差大小	$\begin{align} & \frac{t}{q}{{s}_{2}}{{\epsilon }_{2}}-\frac{t}{q}c{{t}_{0}}\cdot \\ & {{\epsilon }_{3}}-\frac{t}{p}{{\epsilon }_{4}} \\ \end{align}$	$\begin{align} & \frac{t}{q}\left( {{s}_{2}}{{\epsilon }_{2}}- \right. \\ & \left\langle BD\left( c{{t}_{0}} \right), \right. \\ & \left. \left. {{m}_{4}} \right\rangle \right)-\frac{t}{p}{{\epsilon }_{3}} \\ \end{align}$	$\begin{align} & \frac{t}{{P}''q}\left( {{s}_{2}}{{\epsilon }_{2}}- \right. \\ & \left. c{{t}_{0}}{{\epsilon }_{4}} \right)-\frac{t}{{P}'p}{{\epsilon }_{3}} \\ \end{align}$	$\begin{align} & \frac{t}{{P}''q}\left( {{s}_{2}}{{\epsilon }_{2}}-\left\langle BD\left( c{{t}_{0}} \right), \right. \right. \\ & \left. \left. {{m}_{4}} \right\rangle \right)-\frac{t}{{P}'p}{{\epsilon }_{3}} \\ \end{align}$
密钥规模	$1\times 2$	$\left( {l}'+1 \right)\times 2$	$1\times 2$	$\left( {l}'+1 \right)\times 2$
模数	$r\times q$	$r\times q$	${P}'r\times {P}''q$	${P}'r\times {P}''q$
乘法次数/次	2	$\left( {l}'+1 \right)\times 2$	2	$\left( {l}'+1 \right)\times 2$

指标	经典方案	BV型方案	GHS型方案	混合型方案
误差大小	$\frac{t}{p}c{{t}_{0}}{{\epsilon }_{2}}$	$\frac{t}{p}\left\langle BD\left( c{{t}_{0}} \right),{{m}_{2}} \right\rangle $	$\frac{t}{p{P}'}\text{c}{{\text{t}}_{0}}{{\epsilon }_{2}}$	$\begin{align} & \frac{t}{{P}''q}\left( {{s}_{2}}{{\epsilon }_{2}}-\left\langle BD\left( c{{t}_{0}} \right), \right. \right. \\ & \left. \left. {{m}_{4}} \right\rangle \right)-\frac{t}{{P}'p}{{\epsilon }_{3}} \\ \end{align}$
密钥规模	$1\times 2$	$\left( {l}'+1 \right)\times 2$	$1\times 2$	$\left( {l}'+1 \right)\times 2$
模数	$q\times p$	$q\times p$	${P}''q\times {P}'p$	${P}''q\times {P}'p$
乘法次数/次	2	$\left( {l}'+1 \right)\times 2$	2	$\left( {l}'+1 \right)\times 2$

基于RLWR的同态加密方案的密钥切换技术

Key Switching for Somewhat Homomorphic Encryption Based on RLWR

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 32

相关文章 15

编辑推荐

Metrics

本文评价

[1]	陈春玲, 路献辉, 王睿达, 白吉康, 解树兵. 全同态加密中的门自举研究[J]. 信息网络安全, 2025, 25(11): 1691-1706.
[2]	温金明, 刘庆, 陈洁, 吴永东. 基于错误学习的全同态加密技术研究现状与挑战[J]. 信息网络安全, 2024, 24(9): 1328-1351.
[3]	王南, 袁也, 杨浩然, 文周之, 苏明, 刘晓光. 环保大数据在区块链中的隐私计算[J]. 信息网络安全, 2024, 24(10): 1515-1527.
[4]	李增鹏, 王梅, 陈梦佳. 新形态伪随机函数研究[J]. 信息网络安全, 2023, 23(5): 11-21.
[5]	李宁波, 周昊楠, 车小亮, 杨晓元. 云环境下基于多密钥全同态加密的定向解密协议设计[J]. 信息网络安全, 2020, 20(6): 10-16.
[6]	周昊楠, 李宁波, 车小亮, 杨晓元. 基于素数幂次阶分圆多项式环的多密钥全同态方案[J]. 信息网络安全, 2020, 20(5): 83-87.
[7]	刘文超, 潘峰, 杨晓元, 周潭平. 基于GPU的全同态加密软件库调试与分析[J]. 信息网络安全, 2019, 19(6): 76-83.
[8]	宋新霞, 马佳敏, 陈智罡, 陈克非. 基于SEAL的虹膜特征密文认证系统[J]. 信息网络安全, 2018, 18(12): 15-22.
[9]	王嵘冰, 李雅囡, 徐红艳, 冯勇. 适合云服务环境的实数全同态加密方案[J]. 信息网络安全, 2018, 18(11): 49-56.
[10]	李增鹏, 马春光, 张磊, 张雯雯. 两类基于容错学习的多比特格公钥加密方案[J]. 信息网络安全, 2017, 17(10): 1-7.
[11]	李增鹏, 邹岩, 张磊, 马春光. 一种基于全同态加密的智能电网数据交换隐私保护方案[J]. 信息网络安全, 2016, 16(3): 1-7.
[12]	王志刚, 马春光, 史晓倩. 基于Binary LWE的全同态加密方案研究[J]. 信息网络安全, 2015, 15(7): 41-50.
[13]	吕海峰, 丁勇, 代洪艳, 李新国. LWE上的全同态加密方案研究[J]. 信息网络安全, 2015, 15(1): 32-38.
[14]	. 可计算密文加密体制研究[J]. , 2014, 14(5): 78-.
[15]	吴旭东. 云计算数据安全研究[J]. , 2011, 11(9): 0-0.