- Award ID(s):
- 1718658
- NSF-PAR ID:
- 10125443
- Date Published:
- Journal Name:
- 2019 IEEE International Symposium on Information Theory (ISIT)
- Page Range / eLocation ID:
- 1042 to 1046
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Matthieu Bloch (Ed.)Motivated by an open problem and a conjecture, this work studies the problem of single server private information retrieval with private coded side information (PIR-PCSI) that was recently introduced by Heidarzadeh et al. The goal of PIR-PCSI is to allow a user to efficiently retrieve a desired message Wθ, which is one of K independent messages that are stored at a server, while utilizing private side information of a linear combination of a uniformly chosen size-M subset (S ⊂ [K]) of messages. The settings PIR-PCSI-I and PIR-PCSI-II correspond to the constraints that θ is generated uniformly from [K]\S, and S, respectively. In each case, (θ, S) must be kept private from the server. The capacity is defined as the supremum over message and field sizes, of achievable rates (number of bits of desired message retrieved per bit of download) and is characterized by Heidarzadeh et al. for PIR-PCSI-I in general, and for PIR- PCSI-II for M > (K + 1)/2 as (K − M + 1)−1. For 2 ≤ M ≤ (K + 1)/2 the capacity of PIR-PCSI-II remains open, and it is conjectured that even in this case the capacity is (K − M + 1)−1. We show the capacity of PIR-PCSI-II is equal to 2/K for 2 ≤ M ≤ K+1, which is strictly larger 2 than the conjectured value, and does not depend on M within this parameter regime. Remarkably, half the side-information is found to be redundant. We also characterize the infimum capacity (infimum over fields instead of supremum), and the capacity with private coefficients. The results are generalized to PIR-PCSI-I (θ ∈ [K] \ S) and PIR-PCSI (θ ∈ [K]) settings.more » « less
-
more » « less
Information leakage is usually defined as the logarithmic increment in the adversary’s probability of correctly guessing the legitimate user’s private data or some arbitrary function of the private data when presented with the legitimate user’s publicly disclosed information. However, this definition of information leakage implicitly assumes that both the privacy mechanism and the prior probability of the original data are entirely known to the attacker. In reality, the assumption of complete knowledge of the privacy mechanism for an attacker is often impractical. The attacker can usually have access to only an approximate version of the correct privacy mechanism, computed from a limited set of the disclosed data, for which they can access the corresponding un-distorted data. In this scenario, the conventional definition of leakage no longer has an operational meaning. To address this problem, in this article, we propose novel meaningful information-theoretic metrics for information leakage when the attacker hasincomplete information about the privacy mechanism—we call themaverage subjective leakage ,average confidence boost , andaverage objective leakage , respectively. For the simplest, binary scenario, we demonstrate how to find an optimized privacy mechanism that minimizes the worst-case value of either of these leakages.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ISIT.2019.8849283
