Key Switching for Somewhat Homomorphic Encryption Based on RLWR

doi:10.3969/j.issn.1671-1122.2025.12.011

Abstract

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

CLC Number:

TP309

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.

Figures/Tables 2

References 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$