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

doi:10.19665/j.issn1001-2400.20230905

Abstract

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

CLC Number:

TN918.4

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

Figures/Tables 10

	层数
输入:密文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//密文加法

References 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

Homomorphic noise evaluation of LowMC in BGV environment

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 30

Related Articles 2

Metrics

Comments

Recommended 0

[1]	YING Zuobin;MA Jianfeng;CUI Jiangtao. Attribute-based encryption with location verification and policy adjusting supporting the cloud mobile office [J]. Journal of Xidian University, 2017, 44(2): 57-62+190.
[2]	LI Zhuo;XING Li-juan;WANG Xin-mei. Encoding and decoding of a family of quantum stabilizer codes [J]. J4, 2008, 35(5): 834-837.