LowMC在BGV全同态加密环境下的噪声评估

doi:10.19665/j.issn1001-2400.20230905

摘要/Abstract

摘要：

全同态加密技术具备的密文计算特性可以有效保护用户在互联网上的敏感数据,但该技术存在的密文膨胀问题是制约其在云计算、隐私保护等领域进行实际应用的一个难点。针对上述问题,提出了混合全同态加密方案FHE-LowMC,将LowMC对称加密算法与BGV全同态加密算法结合,分析了LowMC在BGV全同态加密环境下的同态噪声。首先给出了将LowMC明文编码成整系数多项式的方法,利用编码和解码完成不同空间明文消息的转换;然后描述了分圆多项式f(X)的选取规则,给出了适合LowMC加密算法的f(X)的条件;接着分析了简化LowMC的同态噪声;最后对一般情况下的LowMC进行同态噪声评估。结果表明,LowMC轮函数所消耗的电路层数大约为两层。相较于目前常用的AES和BGV结合的方案,LowMC与BGV结合的方案噪声更小,即消耗的电路的层数更少,成本更低,更适合构造基于全同态的云服务器;此外用户可以自主选择LowMC的参数集( $n ˜$ ,k,m,d),可以满足用户的不同需求,适用范围更广。

关键词: 同态噪声评估, 敏感数据, LowMC, BGV, 编码和解码

Abstract:

The ciphertext computing characteristics of full homomorphic encryption technology can effectively protect users' sensitive data on the Internet,but the problem of ciphertext inflation in this technology is a difficulty that restricts its practical application in fields such as cloud computing and privacy protection.In response to the above issues,this article proposes a hybrid homomorphic encryption scheme FHE-LowMC,which combines the LowMC symmetric encryption algorithm with the BGV homomorphic encryption algorithm to analyze the homomorphic noise of LowMC in the BGV homomorphic encryption environment.First,a method for encoding the LowMC plaintext into integer coefficient polynomials is proposed,which utilizes encoding and decoding to complete the conversion of plaintext messages in different spaces.Then,the selection rules for the cyclotomic polynomial f(X) is described,with the conditions f(X) suitable for the LowMC encryption algorithm given.Afterwards,the homomorphic noise of the simplified LowMC is analyzed.Finally,homomorphic noise evaluation is performed on LowMC under general conditions.The results show that the number of circuit layers consumed by the LowMC round function is about two.Compared with the currently commonly used AES and BGV combination scheme,the scheme combining LowMC and BGV has a lower noise,which means it consumes fewer layers of circuits and has lower costs,making it more suitable for constructing cloud servers based on homomorphisms.In addition,users can independently select the parameter set( $n ˜$ ,k,m,d)of LowMC,which meets the different needs of users and has a wider scope of application.

Key words: homomorphic noise evaluation, sensitive data, LowMC, BGV, encoding and decoding

中图分类号:

TN918.4

李雪莲, 陈卓皓. LowMC在BGV全同态加密环境下的噪声评估[J]. 西安电子科技大学学报, 2024, 51(3): 182-193.

LI Xuelian, CHEN Zhuohao. Homomorphic noise evaluation of LowMC in BGV environment[J]. Journal of Xidian University, 2024, 51(3): 182-193.

图/表 10

图1

图2

表1

图3

图4

图5

图6

表2

表3

LowMC一轮轮函数噪声分析"

	层数
输入:密文h=( $h a 1$ , $h b 1$ , $h c 1$ , $h a 2$ , $h b 2$ , $h c 2$ ,…, $h a m$ , $h b m$ , $h c m$ ,h³^m⁺¹,h³^m⁺²,…, $h n ˜$ )	t
//S盒变换层
① $s i a$ = $h b i h c i$ (1≤i≤m)	t+1//密文乘法
② $s i b$ = $h a i h c i$ (1≤i≤m)	t+1//密文乘法
③ $s i c$ = $h a i h b i$ (1≤i≤m)	t+1//密文乘法
④ $h * j i$ ← $A ¯$ h^*(1≤i≤m,j=a,b,c)	t+1.5//常量乘法
⑤ $h_{j}^{\prime} \leftarrow h^{*}{ }_{j}^{i} \oplus s_{i}^{j}(1 \leqslant i \leqslant m, j=a, b, c)$	t+1.5//密文加法
⑥ h'=( $h a' 1$ , $h b' 1$ , $h c' 1$ , $h a' 2$ , $h b' 2$ , $h c' 2$ ,…, $h a' m$ , $h b' m$ , $h c' m$ ,h³^m⁺¹,h³^m⁺²,…, $h n ˜$ )	t+1.5//结合
//仿射层
⑦ h^**=L(i)h'	t+2//常量乘法
⑧ \boldsymbol{h}^{\prime \prime}=\boldsymbol{h}^{* *} \oplus \boldsymbol{r}(i)	t+2//密文加法
//轮密钥加层
⑨ $c=\boldsymbol{h}^{\prime \prime} \oplus \boldsymbol{k}[i]$	t+2//密文加法

表3

表4

参考文献 30

[1]	RIVEST R L, SHAMIR A, ADLEMAN L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems[J]. Communications of the ACM, 1978, 21(2):120-126.
[2]	GENTRY C. Fully Homomorphic Encryption Using Ideal Lattice[C]//Proceedings of the 41st 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[C]//2011 IEEE 52nd Annual Symposium on Foundations of Computer Science.Piscataway:IEEE, 2013:97-106.
[4]	BRAKERSKI Z, VAIKUNTANATHAN V. Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages[C]//Advances in Cryptology—CRYPTO 2011. Berlin:Springer, 2011:505-524.
[5]	BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V. (Leveled) Fully Homomorphic Encryption without Bootstrapping[J]. ACM Transactions on Computation Theory, 2014, 6(3):1-36.
[6]	GENTRY C, SAHAI A, WATERS B. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster,Attribute-Based[C]//Advances in Cryptology—CRYPTO 2013. Berlin:Springer, 2013:75-92.
[7]	杨雄, 张晓惠, 刘畅. 供应链产品信息搜索系统中基于同态加密的隐私保护研究[J]. 网络安全技术与应用, 2022,(3):32-33.
	YANG Xiong, ZHANG Xiaohui, LIU Chang. Research on Privacy Protection Based on Homomorphic Encryption in Supply Chain Product Information Search System[J]. Network Security Technology & Application, 2022,(3):32-33.
[8]	李阳. 基于共轭搜索问题的全同态机器学习隐私保护方法[D]. 重庆: 重庆交通大学, 2023.
[9]	SPERLING L, RATHA N, ROSS A, et al. HEFT:Homomorphically Encrypted Fusion of Biometric Templates[C]//2022 IEEE International Joint Conference on Biometrics(IJCB).Piscataway:IEEE, 2022:1-10.
[10]	GU Y, SHEN L, ZHANG F, et al. Provably Secure Linearly Homomorphic Aggregate Signature Scheme for Electronic Healthcare System[J]. Mathematics, 2022, 10(15), 2588:1-14.
[11]	杨亚涛, 刘德莉, 刘培鹤, 等. BFV-Blockchainvoting:支持BFV全同态加密的区块链电子投票系统[J]. 通信学报, 2022, 43(9):100-111. doi: 10.11959/j.issn.1000-436x.2022172
	YANG Yatao, LIU Deli, LIU Peihe, et al. BFV-Blockchainvoting:Blockchain-Based Electronic Voting Systems with BFV Full Homomorphic Encryption[J]. Journal on Communications, 2022, 43(9):100-111. doi: 10.11959/j.issn.1000-436x.2022172
[12]	李文华, 董丽华, 曾勇. key-nets同态加密方案的安全性分析及改进[J]. 西安电子科技大学学报, 2023, 50(1):192-202.
	LI Wenhua, DONG Lihua, ZENG Yong. Security Analysis and Improvement of the Key-Nets Homomorphic Encryption Scheme[J]. Journal of Xidian University, 2023, 50(1):192-202.
[13]	王凯文, 王树兰, 王海燕, 等. 一种支持属性撤销的top-k多关键词密文检索方案[J]. 西安电子科技大学学报, 2022, 49(1):26-34.
	WANG Kaiwen, WANG Shulan, WANG Haiyan, et al. Top-K Multi-Keyword Ciphertext Retrieval Scheme Supporting Attribute Revocation[J]. Journal of Xidian University, 2022, 49(1):26-34.
[14]	MUNJAL K, BHATIA R. A Systematic Review of Homomorphic Encryption and Its Contributions in Healthcare Industry[J]. Complex & Intelligent Systems, 2023, 9:3759-3786.
[15]	CHEN J, LI K, YU P S. Privacy-Preserving Deep Learning Model for Decentralized VANETs Using Fully Homomorphic Encryption and Blockchain[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(8):11633-11642.
[16]	VANIN F N D S, POLICARPO L M, RIGHI R D R, et al. A Blockchain-Based End-to-End Data Protection Model for Personal Health Records Sharing:A Fully Homomorphic Encryption Approach[J]. Sensors, 2023, 23(1)14:1-23.
[17]	NAEHRING M, LAUTER K, VAIKUNTANATHAN V. Can Homomorphic Encryption Be Practical?[C]//Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop. New York: ACM, 2011:113-124.
[18]	GENTRY C, HALEVI S, SMART N P. Homomorphic Evaluation of the AES Circuit[C]//Advances in Cryptology—CRYPTO 2012. Berlin:Springer, 2012:850-867.
[19]	DORÖZ Y, HU Y, SUNAR B. Homomorphic AES Evaluation Using the Modified LTV Scheme[J]. Designs,Codes and Cryptography, 2016, 80:333-358.
[20]	MÉAUX P, JOURNAULT A, STANDAERT F X, et al. Towards Stream Ciphers for Efficient FHE with Low-Noise Ciphertexts[C]//Advances in Cryptology—EUROCRYPT 2016. Berlin:Springer, 2016:311-343.
[21]	KAMATCHI T P, KUMARI K A. A Hybrid Homomorphic Model with RSA Algorithm and Modified Enhanced Homomorphic Encryption Technique[C]//2023 International Conference on Intelligent Systems for Communication,IoT and Security(ICISCoIS).Piscataway:IEEE, 2023:371-375.
[22]	陶梦龙, 胡斌. 基于全同态加密与对称加密融合的批处理研究[J]. 四川大学学报(自然科学版), 2019, 56(5):857-866.
	TAO Menglong, HU Bin. Research Based on Batch Fully Homomorphic Encryption-Symmetric Encryption[J]. Journal of Sichuan University(Natural Science Edition), 2019, 56(5):857-866.
[23]	MÉAUX P, CARLET C, JOURNAULT A, et al. Improved FilterPermutators for Efficient FHE:Better Instances and Implementations[C]//Progress in Cryptology—INDOCRYPT 2019. Berlin:Springer, 2019:68-91.
[24]	ALBRECHT M R, RECHBERGER C, SCHNEIDER T, et al. Ciphers for MPC and FHE[C]//Advances in Cryptology—EUROCRYPT 2015. Berlin:Springer, 2015:430-454.
[25]	SMART N P, VERCAUTEREN F. Fully Homomorphic SIMD Operations[J]. Designs,Codes and Cryptography, 2014, 71:57-81.
[26]	陈智罡. 全同态加密——从理论到实践[M]. 北京: 清华大学出出版社, 2022,1-189.
[27]	CHEON J H, KIM A, KIM M, et al. Homomorphic Encryption for Arithmetic of Approximate Numbers[C]//Advances in Cryptology—ASIACRYPT 2017. Berlin:Springer, 2017:409-437.
[28]	SMART N P, VERCAUTEREN F. Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes[C]//Public Key Cryptography—PKC 2010. Berlin:Springer, 2010:420-443.
[29]	宋新霞, 陈智罡, 李焱华. HEBenchmark:全同态加密测试系统设计与实现[J]. 密码学报, 2020, 7(6):853-863. doi: 10.13868/j.cnki.jcr.000411
	SONG Xinxia, CHEN Zhigang, LI Yanhua. HEBenchmark:Design and Implementation of Fully Homomorphic Encryption Test System[J]. Journal of Cryptologic Research, 2020, 7(6):853-863.
[30]	葛欣欣. LowMC实例的差分枚举攻击分析[D]. 山东: 山东大学, 2021.

	1	2	3	4	5	6	7	8	9	10	平均值
密文加法	1.7	2.0	1.9	2.6	1.6	2.5	2.9	2.3	3.1	2.4	2.30
密文乘法	7.5	8.1	8.0	8.9	7.1	8.6	9.5	8.4	10.2	8.5	8.48

	LowMC	AES^[18]
S盒变换	√(1.5)	√(3.5)
轮密钥加	√(0)	√(0)
线性变换	√(0.5)
轮常量加	√(0)
行变换		√(0.5)
列混淆		√(0.5)
噪声总增长	2	4.5