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

doi:10.3976/j.issn.1002-4026.20240092

Abstract

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

CLC Number:

G354

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

Figures/Tables 6

Table 1

Table 2

Table 3

Table 4

Client consumption"

方法	安全假设	客户端消耗
		通信		计算		存储
		离线	在线	离线	在线	存储
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	λ

Table 4

Table 5

Server consumption"

方法	安全假设	服务器端消耗
		通信		计算		花费
		离线	在线	离线	在线	花费
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

Table 5

Table 6

References 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.

Metrics

Comments

Recommended 0

Open Access This article is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0), which permits third parties to freely share (i.e., copy and redistribute the material in any medium or format) and adapt (i.e., remix, transform, or build upon the material) the articles published in this journal, provided that appropriate credit is given, a link to the license is provided, and any changes made are indicated. The material may not be used for commercial purposes. For details of the CC BY-NC 4.0 license, please visit: https://creativecommons.org/licenses/by-nc/4.0

客户端状态	离线	在线
客户端上传	—	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

Cost amortization-based single-server private information retrieval method

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 20

Related Articles 1

Metrics

Comments

Recommended 0