同态加密PIR中查询请求带宽优化的通用构造与实例

doi:10.3969/j.issn.1671-1122.2025.07.008

信息网络安全 ›› 2025, Vol. 25 ›› Issue (7): 1092-1102.doi: 10.3969/j.issn.1671-1122.2025.07.008

同态加密PIR中查询请求带宽优化的通用构造与实例

田海博¹^,², 李奕彤¹, 杜育松¹^,²()

1.中山大学计算机学院，广州 510006
2.广东省信息安全技术重点实验室，广州 510006

收稿日期:2025-04-28 出版日期:2025-07-10 发布日期:2025-08-07
通讯作者: 杜育松 E-mail:duyusong@mail.sysu.edu.cn
作者简介:田海博（1979—），男，河北，副教授，博士，主要研究方向为密码协议设计和分析|李奕彤（2001—），女，山西，硕士研究生，主要研究方向为隐私计算|杜育松（1982—），男，河北，副教授，博士，主要研究方向为密码算法
基金资助:
国家重点研发计划(2022YFB2701500);广东省信息安全技术重点实验室项目(2023B1212060026)

General Construction and Instantiation for Query Request Bandwidth Optimization in Homomorphic Encryption-Based PIR

TIAN Haibo¹^,², LI Yitong¹, DU Yusong¹^,²()

1. School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China
2. Guangdong Provincial Key Laboratory of Information Security Technology, Guangzhou 510006, China

Received:2025-04-28 Online:2025-07-10 Published:2025-08-07
Contact: DU Yusong E-mail:duyusong@mail.sysu.edu.cn

摘要/Abstract

摘要：

同态加密PIR利用同态加密技术使用户能够在不泄露检索内容的前提下从数据库中检索数据，一直备受学术界关注。针对服务器高吞吐量的同态加密PIR中查询请求带宽较大的问题，文章在随机同态流密码的框架下，设计了基于Regev同态加密的随机同态流密码算法，提出了查询请求带宽更优的同态加密PIR通用构造方法，实现了基于SimplePIR协议的PIR实例，分析了该实例的正确性和安全性，测试了该实例在不同数据库大小时的实际查询请求带宽。测试结果表明，查询规模为64 MB的数据库时，该实例的查询请求带宽下降约36.6%。

关键词: 隐私信息检索, 随机同态流密码, Regev同态加密

Abstract:

Homomorphic encryption-based Private Information Retrieval allows users to retrieve data from a database without revealing the query index by leveraging homomorphic encryption technology, and it has always attracted significant attention in the academic community. To address the issue of large query request bandwidth in homomorphic encryption-based PIR schemes for high-throughput on the server side, this paper designed a Regev homomorphic encryption-based randomized homomorphic stream cipher algorithm within the framework of Randomized Homomorphic Stream Cipher. This paper proposed a general construction for optimizing query request bandwidth in homomorphic encryption-based PIR. Furthermore, this paper presented and implemented a concrete instantiation based on the SimplePIR protocol. The correctness and security of this instantiation were thoroughly analyzed. Experimental evaluations were conducted to measure the actual throughput and query request bandwidth under various database sizes. The experimental results demonstrate that for a 64 MB database, the instantiation achieves a 36.6% reduction in query request bandwidth.

Key words: private information retrieval, randomized homomorphic stream cipher, Regev homomorphic encryption

中图分类号:

TP309

田海博, 李奕彤, 杜育松. 同态加密PIR中查询请求带宽优化的通用构造与实例[J]. 信息网络安全, 2025, 25(7): 1092-1102.

TIAN Haibo, LI Yitong, DU Yusong. General Construction and Instantiation for Query Request Bandwidth Optimization in Homomorphic Encryption-Based PIR[J]. Netinfo Security, 2025, 25(7): 1092-1102.

图/表 7

图1

表1

表2

图2

图3

图4

表3

参考文献 20

[1]	CHOR B, KUSHILEVITZ E, GOLDREICH O, et al. Private Information Retrieval[C]// IEEE. IEEE 36th Annual Foundations of Computer Science. New York: IEEE, 1995: 41-50.
[2]	KUSHILEVITZ E, OSTROVSKY R. Replication is Not Needed: Single Database, Computationally-Private Information Retrieval[C]// IEEE. 38th Annual Symposium on Foundations of Computer Science. New York: IEEE, 1997: 364-373.
[3]	MENON S J, WU D J. YPIR: High-Throughput Single-Server PIR with Silent Preprocessing[C]// USENIX. 33rd USENIX Security Symposium(USENIX Security ’24). Berkeley: USENIX, 2024: 5985-6002.
[4]	HENZINGER A, HONG M M, CORRIGAN-GIBBS H, et al. One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval[C]// USENIX. 32nd USENIX Security Symposium (USENIX Security ’23). Berkeley: USENIX, 2023: 3889-3905.
[5]	GE Yifei, ZHENG Yanbin. Private Information Retrieval Schemes with Erasure-Correcting or Error-Correcting Properties[J]. Journal of Guangxi Teachers Education University(Philosophy and Social Sciences Edition), 2020, 38(3): 33-44.
	葛奕飞, 郑彦斌. 带有纠删或纠错性质的隐私保护信息检索方案[J]. 广西师范大学学报(自然科学版), 2020, 38(3):33-44.
[6]	ZHANG Xiaoqing, ZHANG Shuli, LEI Shumei, et al. Analysis and Comparison of Private Information Retrieval Techniques[J]. Communications Technology, 2023, 56(2): 198-206.
	张小青, 张舒黎, 雷术梅, 等. 私有信息检索技术分析对比研究[J]. 通信技术, 2023, 56(2):198-206.
[7]	CHI Jialin, FENG Dengguo, ZHANG Min, et al. Advances in Privacy-Preserving Ciphertext Retrieval[J]. Journal of Electronics & Information Technology, 2024, 46(5): 1546-1569.
	迟佳琳, 冯登国, 张敏, 等. 隐私保护密文检索技术研究进展[J]. 电子与信息学报, 2024, 46(5):1546-1569.
[8]	AGUILAR-MELCHOR C, BARRIER J, FOUSSE L, et al. XPIR: Private Information Retrieval for Everyone[J]. Proceedings on Privacy Enhancing Technologies, 2016(2): 155-174.
[9]	ANGEL S, CHEN Hao, LAINE K, et al. PIR with Compressed Queries and Amortized Query Processing[C]// IEEE. 2018 IEEE Symposium on Security and Privacy (SP). New York: IEEE, 2018: 962-979.
[10]	MUGHEES M H, CHEN Hao, REN Ling. OnionPIR: Response Efficient Single-Server PIR[C]// ACM. Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2021: 2292-2306.
[11]	MENON S J, WU D J. Spiral:Fast, High-Rate Single-Server PIR via FHE Composition[C]// IEEE. 2022 IEEE Symposium on Security and Privacy (SP). New York: IEEE, 2022: 930-947.
[12]	LUO Ming, LIU Fenghao, WANG Han. Faster FHE-Based Single-Server Private Information Retrieval[C]// ACM. Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2024: 1405-1419.
[13]	PARK J, TIBOUCHI M. SHECS-PIR: Somewhat Homomorphic Encryption-Based Compact and Scalable Private Information Retrieval[C]// Springer. Computer Security-ESORICS 2020-25th European Symposium on Research in Computer Security. Heidelberg: Springer, 2020: 86-106.
[14]	TIAN Haibo, LIN Yini. An Efficient Private Information Retrieval Protocol Based on TFHE[C]// Springer. EAI SecureComm 2023-19th EAI International Conference on Security and Privacy in Communication Networks. Heidelberg: Springer, 2023: 476-495.
[15]	HENZINGER A, DAUTERMAN E, CORRIGAN-GIBBS H, et al. Private Web Search with Tiptoe[C]// ACM. Proceedings of the 29th Symposium on Operating Systems Principles. New York: ACM, 2023: 396-416.
[16]	LI Baiyu, MICCIANCIO D, RAYKOVA M, et al. Hintless Single-Server Private Information Retrieval[C]// Springer. Advances in Cryptology-CRYPTO 2024-44th Annual International Cryptology Conference. Heidelberg: Springer, 2024: 183-217.
[17]	BECK M. Randomized Decryption (RD) Mode of Operation for Homomorphic Cryptography-Increasing Encryption, Communication and Storage Efficiency[C]// IEEE. 2015 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). New York: IEEE, 2015: 220-226.
[18]	REGEV O. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[C]// ACM. The Thirty-Seventh Annual ACM Symposium on Theory of Computing. New York: ACM, 2005: 84-93.
[19]	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.
[20]	LINDNER R, PEIKERT C. Better Key Sizes (and Attacks) for LWE-Based Encryption[C]// Springer. Topics in Cryptology-CT-RSA 2011: The Cryptographers’ Track at the RSA Conference 2011. Heidelberg: Springer, 2011: 319-339.

数据库大小N	2²⁶	2²⁸	2³⁰	2³⁴	2³⁸	2⁴²
缩放因子${{\Delta }_{1}}$	2⁷	2⁷	2⁷	2⁷	2⁶	2⁵
缩放因子${{\Delta }_{2}}$	2²²	2²³	2²³	2²⁴	2²⁴	2²⁴
中间模量$\tilde{p}$	2²³	2²⁴	2²⁴	2²⁵	2²⁶	2²⁷

数据库规模	指标	RHSC-SimplePIR	SimplePIR	DoublePIR	Spiral	KsPIR	YPIR
4 MB (2²⁵×1)	离线提示通信量/MB	22.6	22.6	16	0	0	0
	在线上传通信量/KB	16	22	256	14	140	486
	在线下载通信量/KB	22	22	32	14	26	12
	吞吐量 (MB/s)	4455	4749	3467	13	30	74
16 MB (2²⁷×1)	离线提示通信量/MB	45.2	45.2	16	0	0	0
	在线上传通信量/KB	33	45	264	14	140	510
	在线下载通信量/KB	45	45	32	20	26	12
	吞吐量 (MB/s)	4976	5107	4144	35	49	281
64 MB (2²⁹×1)	离线提示通信量/MB	90.5	90.5	16	0	0	0
	在线上传通信量/KB	57	90	288	14	140	558
	在线下载通信量/KB	90	90	32	20	26	12
	吞吐量 (MB/s)	7762	7810	5125	76	97	969

同态加密PIR中查询请求带宽优化的通用构造与实例

General Construction and Instantiation for Query Request Bandwidth Optimization in Homomorphic Encryption-Based PIR

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 20

相关文章 15

编辑推荐

Metrics

本文评价

[1]	陈平, 骆明宇. 云边端内核竞态漏洞大模型分析方法研究[J]. 信息网络安全, 2025, 25(7): 1007-1020.
[2]	张全新, 李可, 邵雨洁, 谭毓安. 基于FPGA的SM4异构加速系统[J]. 信息网络安全, 2025, 25(7): 1021-1031.
[3]	王梅, 杨潇然, 李增鹏. 简洁低交互的物联网设备认证协议研究[J]. 信息网络安全, 2025, 25(7): 1032-1043.
[4]	刘宇靖, 王致林, 李鹏飞, 王成孝. 基于路由时间介数的域间路由传播特征分析方法[J]. 信息网络安全, 2025, 25(7): 1044-1052.
[5]	张光华, 常继友, 陈放, 毛伯敏, 王鹤, 张建燕. 基于库函数动态替换的物联网设备固件仿真方案[J]. 信息网络安全, 2025, 25(7): 1053-1062.
[6]	杨望, 马鸣宇, 卞郡菁. 基于ATT&CK的多维网络靶场属性刻画模型及其相似性算法[J]. 信息网络安全, 2025, 25(7): 1063-1073.
[7]	闫宇坤, 唐朋, 陈睿, 都若尘, 韩启龙. 面向数据投毒后门攻击的随机性增强双层优化防御方法[J]. 信息网络安全, 2025, 25(7): 1074-1091.
[8]	冷永清, 敖天勇, 邱昕, 崔兴利, 李邵石. S盒密码学指标自动评估系统设计与实现[J]. 信息网络安全, 2025, 25(7): 1103-1110.
[9]	高扬, 张琪, 王琛, 徐剑. 新型可组合的认证分布式数据结构模型研究[J]. 信息网络安全, 2025, 25(7): 1111-1125.
[10]	赵海霞, 刘德雄. 基于Walsh谱与真值表关联矩阵${}_{n}\text{A}$和${}_{n}B$的RSBF的多指标搜索方法[J]. 信息网络安全, 2025, 25(7): 1126-1137.
[11]	汪正阳, 刘晓露, 沈卓炜, 韦梦立. 多智能体系统安全防护技术研究综述[J]. 信息网络安全, 2025, 25(7): 1138-1152.
[12]	张雪锋, 苗锴. 一种基于渐进聚焦的低质量指纹姿态估计方案[J]. 信息网络安全, 2025, 25(7): 1153-1162.
[13]	酆薇, 肖文名, 田征, 梁中军, 姜滨. 基于大语言模型的气象数据语义智能识别算法研究[J]. 信息网络安全, 2025, 25(7): 1163-1171.
[14]	赵波, 彭君茹, 王一琁. 基于威胁传播的网络安全态势评估方法[J]. 信息网络安全, 2025, 25(6): 843-858.
[15]	孙剑文, 张斌, 司念文, 樊莹. 基于知识蒸馏的轻量化恶意流量检测方法[J]. 信息网络安全, 2025, 25(6): 859-871.