Asymmetric Leaky Private Information Retrieval
| Autor: | Loukas Lazos, Mohamed Adel Attia, Ravi Tandon, Islam Samy |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
FOS: Computer and information sciences Information privacy Computer Science - Information Theory Information Theory (cs.IT) Multiplicative function Inverse 020206 networking & telecommunications Databases (cs.DB) 02 engineering and technology Function (mathematics) Library and Information Sciences Upper and lower bounds Computer Science - Information Retrieval Computer Science Applications Computer Science - Databases 0202 electrical engineering electronic engineering information engineering Relaxation (approximation) Variety (universal algebra) Constant (mathematics) Information Retrieval (cs.IR) Computer Science::Cryptography and Security Information Systems Mathematics |
| DOI: | 10.48550/arxiv.2006.03048 |
| Popis: | Information-theoretic formulations of the private information retrieval (PIR) problem have been investigated under a variety of scenarios. Symmetric private information retrieval (SPIR) is a variant where a user is able to privately retrieve one out of $K$ messages from $N$ non-colluding replicated databases without learning anything about the remaining $K-1$ messages. However, the goal of perfect privacy can be too taxing for certain applications. In this paper, we investigate if the information-theoretic capacity of SPIR (equivalently, the inverse of the minimum download cost) can be increased by relaxing both user and DB privacy definitions. Such relaxation is relevant in applications where privacy can be traded for communication efficiency. We introduce and investigate the Asymmetric Leaky PIR (AL-PIR) model with different privacy leakage budgets in each direction. For user privacy leakage, we bound the probability ratios between all possible realizations of DB queries by a function of a non-negative constant $\epsilon $ . For DB privacy, we bound the mutual information between the undesired messages, the queries, and the answers, by a function of a non-negative constant $\delta $ . We propose a general AL-PIR scheme that achieves an upper bound on the optimal download cost for arbitrary $\epsilon $ and $\delta $ . We show that the optimal download cost of AL-PIR is upper-bounded as $D^{*}(\epsilon,\delta)\leq 1+\frac {1}{N-1}-\frac {\delta e^{\epsilon }}{N^{K-1}-1}$ . Second, we obtain an information-theoretic lower bound on the download cost as $D^{*}(\epsilon,\delta)\geq 1+\frac {1}{Ne^{\epsilon }-1}-\frac {\delta }{(Ne^{\epsilon })^{K-1}-1}$ . The gap analysis between the two bounds shows that our AL-PIR scheme is optimal when $\epsilon =0$ , i.e., under perfect user privacy and it is optimal within a maximum multiplicative gap of $\frac {N-e^{-\epsilon }}{N-1}$ for any $\epsilon >0$ and $\delta >0$ . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|