成本摊销式单服务器私人情报检索方法

doi:10.3976/j.issn.1002-4026.20240092

摘要/Abstract

摘要：

私人情报检索旨在保护用户的查询内容和隐私,是情报检索领域内隐私保护的重要技术扩展。基于成本摊销的思想设计了一种高度可配置、有状态的、单服务器私人情报检索方案。在一个包含100万个1 kB元素的数据库上进行的实验表明,该方法能够在不到1 s的时间内响应客户端的查询请求,同时服务器的响应数据仅放大不到3.6倍。值得注意的是,实验分析基于一个简单的、未经过优化的Rust实现,说明该方法在涉及大量客户端的部署环境中特别适用。综上,结果表明该方法在私人情报检索领域具有显著的潜力,并且可以为处理大规模情报检索任务提供高效、经济实惠的解决方案。

关键词: 情报检索, 单服务器, 在线开销, 摊销成本, 隐私保护

Abstract:

Private information retrieval aims to protect users’ query content and privacy, serving as an important extension of privacy protection in the field of information retrieval. A highly configurable, stateful, single-server private information retrieval scheme was designed based on the concept of cost amortization. Experiments conducted on a database containing 1 million 1 kB elements showed that this method delivered superior performance, being able to respond to client queries in less than 1 s, with the server’s response data being increased by less than 3.6 times. It is noteworthy that the experimental analysis was based on a simple, unoptimized Rust implementation, suggesting that this method is particularly suitable for deployment environments involving a large number of clients. Experimental results indicate that this method holds significant potential in the field of private information retrieval and can provide an efficient and cost-effective solution for handling large-scale retrieval tasks.

Key words: information retrieval, single-server, online overhead, amortized cost, privacy protection

中图分类号:

G354

蔡馨燕, 于晓. 成本摊销式单服务器私人情报检索方法[J]. 山东科学, 2024, 37(5): 122-130.

CAI Xinyan, YU Xiao. Cost amortization-based single-server private information retrieval method[J]. Shandong Science, 2024, 37(5): 122-130.

图/表 6

表1

表2

表3

表4

客户端消耗"

方法	安全假设	客户端消耗
		通信		计算		存储
		离线	在线	离线	在线	存储
Stateless	RLWE	—	m	—	m	—
PSIR	RLWE	—	1	m	$m$	$m$
SOnionPIR	RLWE	$m$	1	k $m$	k	$m$
CHKPIR	RLWE	—	$m$	$m$	$m$	$m$
本文方法	LWE	—	m	m	1	λ

表4

表5

服务器端消耗"

方法	安全假设	服务器端消耗
		通信		计算		花费
		离线	在线	离线	在线	花费
Stateless	RLWE	—	1	—	m	5.2×10^-3
PSIR	RLWE	$D B m$	1	—	m	8.8×10^-5
SOnionPIR	RLWE	$m$	1	$m$	m	6.4×10^-4
CHKPIR	RLWE	$m$	1	$m$	$m$	8.8×10^-5
本文方法	LWE	λm^-1^/²	1	$m$ /C	m	1.9/C×10^-2+1.3×10^-5

表5

表6

参考文献 20

[1]	ANGEL S, SETTY S. Unobservable communication over fully untrusted infrastructure[C]// Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2016: 551-569.
[2]	ZHOU M X, PARK A, SHI E, et al. Piano: extremely simple, single-server PIR with sublinear server computation[J]. IACRCryptol EPrint Arch, 2023, 2023: 452.
[3]	MENON S J, WU D J. YPIR: high-throughput single-server PIR with silent preprocessing[EB/OL]. [2024-06-20]. https://www.cs.utexas.edu/-dwu4/papers/YPIR.pdf.
[4]	ULUKUS S, AVESTIMEHR S, GASTPAR M, et al. Private retrieval, computing, and learning: Recent progress and future challenges[J]. IEEE Journal on Selected Areas in Communications, 2022, 40(3): 729-748. DOI: 10.1109/JSAC.2022.3142358.
[5]	CORRIGAN-GIBBS H, HENZINGER A, KOGAN D. Single-server private information retrieval with Sublinear amortized time[M]// DUNKELMANO, DZIEMBOWSKIS. Lecture Notes in Computer Science. Cham: Springer International Publishing, 2022: 3-33. DOI: 10.1007/978-3-031-07085-3_1.
[6]	MUGHEES M H, CHEN H, REN L. OnionPIR: response efficient single-server PIR[C]// CCS '21: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. New York, USA: Association for Computing Machinery, 2021: 2292-2306. DOI: 10.1145/3460120.3485381.
[7]	PATEL S, PERSIANO G, YEO K. Private stateful information retrieval[C]// PROCEEDINGS OF THE 2018 ACM Sigsac Conference On Computer and Communications Security (CCS'18). Toronto, CANADA: ACM, 2018.1002-1019. DOI: 10.1145/3243734.3243821.
[8]	SION R, CARBUNAR B. On the practicality of private information retrieval[EB/OL].[2024-06-20]. https://users.cs.fiu.edu/-carbunar/pir.pdf.
[9]	KUSHILEVITZ E, OSTROVSKY R. Replication is not needed: Single database, computationally-private information retrieval[C]// Proceedings 38th Annual Symposium on Foundations of Computer Science. Miami Beach, FL, USA. IEEE, 1997: 364-373. DOI: 10.1109/SFCS.1997.646125.
[10]	CACHIN C, MICALI S, STADLER M. Computationally private information retrieval with polylogarithmic communication[M]// Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999: 402-414. DOI: 10.1007/3-540-48910-x_28.
[11]	GENTRY C, RAMZAN Z. Single-database private information retrieval with constant communication rate[M]// Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005: 803-815. DOI: 10.1007/11523468_65.
[12]	AGUILAR-MELCHOR C, BARRIER J, FOUSSE L, et al. XPIR: Private information retrieval for everyone[J]. Proceedings on Privacy Enhancing Technologies, 2016, 2016(2): 155-174. DOI: 10.1515/popets-2016-0010.
[13]	MENON S J, WU D J. SPIRAL: Fast, high-rate single-server PIR via FHE composition[C]// 2022 IEEE Symposium on Security and Privacy (SP). San Francisco, CA, USA. IEEE, 2022: 930-947. DOI: 10.1109/SP46214.2022.9833700.
[14]	ANGEL S, CHEN H, LAINE K, et al. PIR with compressed queries and amortized query processing[C]// 2018 IEEE Symposium on Security and Privacy (SP). San Francisco, CA, USA. IEEE, 2018: 962-979. DOI: 10.1109/SP.2018.00062.
[15]	CORRIGAN-GIBBS H, KOGAN D. Private information retrieval with sublinear online time[C]// CANTEAUT A, ISHAI Y. 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Zagreb, Croatia: Int Assoc Cryptol Res, 2020: 44-75.
[16]	REGEV O. On lattices, learning with errors, random linear codes, and cryptography[J]. JOURNAL OF THE ACM, 2009, 56(6):34. DOI: 10.1145/1568318.1568324.
[17]	BRAKERSKI Z, LANGLOIS A, PEIKERT C, et al. Classical hardness of learning with errors[C]// STEHLé D. 45th Annual ACM Symposium on the Theory of Computing (STOC). Palo Alto, CA: Assoc Comp Machinery Special Interest Grp Algorithms & Computat Theory, 2013: 575-584.
[18]	MICCIANCIO D, PEIKERT C. Trapdoors for lattices: Simpler, tighter, faster, smaller[J]. IACRCryptol EPrint Arch, 2012, 2011: 501. DOI: 10.1007/978-3-642-29011-4_41.
[19]	PATEL S, PERSIANO G, YEO K. Private stateful information retrieval[C]// Proceedings of the 2018 Acm Sigsac Conference on Computer and Communications Security (CCS'18). New York, USA: Assoc Comp Machinery, 2018:1002-1019. DOI:10.1145/3243734.3243821.
[20]	ALBRECHT M R, PLAYER R, SCOTT S. On the concrete hardness of learningwitherrors[J]. Mathematical Cryptology, 2015, 9(3):169-203.

客户端状态	离线	在线
客户端上传	—	mlog(q)
客户端下载	λ+nωlog(q)	ωlog(q)

存储位置	进行预处理	不进行预处理
服务器端存储	λ+mωlog(ρ)	λ+mωlog(ρ)
客户端存储	λ+c(m+ω)log(q)	λ+nωlog(q)

q	维数n	元素数m	ρ	改进因子κ	安全参数λ
2³²	1 774	2¹⁶	2¹⁰	13.028	128
2³²	1 774	2¹⁷	2¹⁰	26.056	128
2³²	1 774	2¹⁸	2¹⁰	52.112	128
2³²	1 774	2¹⁹	2⁹	93.802	128
2³²	1 774	2²⁰	2⁹	187.603	128

DB项数 log(m)	离线				在线
DB项数 log(m)	客户端下载/kB	数据库预处理/s	客户端推导矩阵/s	客户端查询预处理/s	客户端查询/kB	服务器端回复/kB	客户端查询/ms	服务器端回复/ms	客户端输出/ms
16	5 682.47	104.57	0.582 6	0.146 8	256	3.203	0.021 3	45.013	0.359
17	5 682.47	206.26	1.169 8	0.289 8	512	3.203	0.042 2	94.505	0.398
18	5 682.47	429.07	2.211 8	0.579 5	1 024	3.203	0.081 1	188.360	0.363
19	6 313.07	936.36	4.728 4	1.182 0	2 048	3.556	0.164 8	417.920	0.420
20	6 313.07	1 895.20	9.250 0	2.343 0	4 096	3.556	0.342 9	825.370	0.434