| 1. |
- Lin, Hsuan Yin, et al.
(författare)
-
Multi-Server Weakly-Private Information Retrieval
- 2022
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448 .- 1557-9654. ; 68:2, s. 1197-1219
-
Tidskriftsartikel (refereegranskat)abstract
- Private information retrieval (PIR) protocols ensure that a user can download a file from a database without revealing any information on the identity of the requested file to the servers storing the database. While existing protocols strictly impose that no information is leaked on the file’s identity, this work initiates the study of the tradeoffs that can be achieved by relaxing the perfect privacy requirement. We refer to such protocols as weakly-private information retrieval (WPIR) protocols. In particular, for the case of multiple noncolluding replicated servers, we study how the download rate, the upload cost, and the access complexity can be improved when relaxing the perfect privacy constraint. To quantify the information leakage on the requested file’s identity we consider mutual information (MI), worst-case information leakage, and maximal leakage (MaxL). We present two WPIR schemes, denoted by Scheme A and Scheme B, based on two recent PIR protocols and show that the download rate of the former can be optimized by solving a convex optimization problem. We also show that Scheme A achieves an improved download rate compared to the recently proposed scheme by Samy et al. under the so-called ϵ-privacy metric. Additionally, a family of schemes based on partitioning is presented. Moreover, we provide an information-theoretic converse bound for the maximum possible download rate for the MI and MaxL privacy metrics under a practical restriction on the alphabet size of queries and answers. For two servers and two files, the bound is tight under the MaxL metric, which settles the WPIR capacity in this particular case. Finally, we compare the performance of the proposed schemes and their gap to the converse bound.
|
|
| 2. |
- Lin, Hsuan Yin, et al.
(författare)
-
The Capacity of Single-Server Weakly-Private Information Retrieval
- 2020
-
Ingår i: IEEE International Symposium on Information Theory - Proceedings. - 2157-8095. ; 2020-June, s. 1053-1058
-
Konferensbidrag (refereegranskat)abstract
- Weakly-private information retrieval (WPIR) is a variant of the private information retrieval problem in which a user wants to efficiently retrieve a file stored across a set of servers while tolerating some information leakage on the identity of the requested file to the servers. In this paper, we consider WPIR from a single-server database where the information leakage is measured in terms of the mutual information (MI) or maximal leakage (MaxL) privacy metrics. In particular, we establish a connection between the WPIR problem and rate-distortion theory, and fully characterize the optimal tradeoff between the download cost and the allowed information leakage under the MI and MaxL metrics, settling the single-server WPIR capacity.
|
|
| 3. |
- Lin, Hsuan Yin, et al.
(författare)
-
The Capacity of Single-Server Weakly-Private Information Retrieval
- 2021
-
Ingår i: IEEE Journal on Selected Areas in Information Theory. - 2641-8770. ; 2:1, s. 415-427
-
Tidskriftsartikel (refereegranskat)abstract
- A private information retrieval (PIR) protocol guar- antees 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 proto- cols 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 leak- age (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.
|
|
