The capacity of single-server weakly-private information retrieval

被引：11

作者：

Lin H.-Y. ^{[1
]}

Kumar S. ^{[1
]}

Rosnes E. ^{[1
]}

Graell I Amat A. ^{[1
,2
]}

Yaakobi E. ^{[3
]}

机构：

[1] Simula UiB, Bergen

[2] The Department of Electrical Engineering, Chalmers University of Technology, Gothenburg

[3] The Department of Computer Science, Technion—Israel Institute of Technology, Haifa

来源：

IEEE Journal on Selected Areas in Information Theory | 2021年 / 2卷 / 01期

基金：

以色列科学基金会;

关键词：

Capacity; Information leakage; Information-theoretic privacy; Private information retrieval; Single server;

D O I：

10.1109/JSAIT.2021.3056327

中图分类号：

学科分类号：

摘要：

A private information retrieval (PIR) protocol guarantees that a user can privately retrieve files stored in a database without revealing any information about the identity of the requested file. Existing information-theoretic PIR protocols ensure perfect privacy, i.e., zero information leakage to the servers storing the database, but at the cost of high download. In this work, we present weakly-private information retrieval (WPIR) schemes that trade off perfect privacy to improve the download cost when the database is stored on a single server. We study the tradeoff between the download cost and information leakage in terms of mutual information (MI) and maximal leakage (MaxL) privacy metrics. By relating the WPIR problem to rate-distortion theory, the download-leakage function, which is defined as the minimum required download cost of all single-server WPIR schemes for a given level of information leakage and a fixed file size, is introduced. By characterizing the download-leakage function for the MI and MaxL metrics, the capacity of single-server WPIR is fully described. © 2021 IEEE.

引用

页码：415 / 427

页数：12

共 50 条

[1]

Chor B., Goldreich O., Kushilevitz E., Sudan M., Private information retrieval, Proc. 36th Annu. IEEE Symp. Found. Comput. Sci. (FOCS), pp. 41-50, (1995)

[2]

Shah N.B., Rashmi K.V., Ramchandran K., One extra bit of download ensures perfectly private information retrieval, Proc. IEEE Int. Symp. Inf. Theory (ISIT), pp. 856-860, (2014)

[3]

Chan T.H., Ho S.-W., Yamamoto H., Private information retrieval for coded storage, Proc. IEEE Int. Symp. Inf. Theory (ISIT), pp. 2842-2846, (2015)

[4]

Sun H., Jafar S.A., The capacity of private information retrieval, IEEE Trans. Inf. Theory, 63, 7, pp. 4075-4088, (2017)

[5]

Tajeddine R., Gnilke O.W., El Rouayheb S., Private information retrieval from MDS coded data in distributed storage systems, IEEE Trans. Inf. Theory, 64, 11, pp. 7081-7093, (2018)

[6]

Banawan K., Ulukus S., The capacity of private information retrieval from coded databases, IEEE Trans. Inf. Theory, 64, 3, pp. 1945-1956, (2018)

[7]

Kumar S., Lin H.-Y., Rosnes E., Graell I Amat A., Achieving maximum distance separable private information retrieval capacity with linear codes, IEEE Trans. Inf. Theory, 65, 7, pp. 4243-4273, (2019)

[8]

Lin H.-Y., Kumar S., Rosnes E., Graell I Amat A., Asymmetry helps: Improved private information retrieval protocols for distributed storage, Proc. IEEE Inf. Theory Workshop (ITW), pp. 1-5, (2018)

[9]

Freij-Hollanti R., Gnilke O.W., Hollanti C., Horlemann-Trautmann A.-L., Karpuk D., Kubjas I., T-private information retrieval schemes using transitive codes, IEEE Trans. Inf. Theory, 65, 4, pp. 2107-2118, (2019)

[10]

Sun H., Jafar S.A., The capacity of robust private information retrieval with colluding databases, IEEE Trans. Inf. Theory, 64, 4, pp. 2361-2370, (2018)

← 1 2 3 4 5 →