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

doi:10.3969/j.issn.1671-1122.2025.07.008

Abstract

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

CLC Number:

TP309

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.

Figures/Tables 7

References 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