More Like this

1. Auditing Differentially Private Machine Learning: How Private is Private SGD?

   Jagielski, Matthew ; Ullman, Jonathan ; Oprea, Alina ( January 2020 , Advances in Neural and Information Processing Systems)

   null (Ed.)
2. On Single Server Private Information Retrieval With Private Coded Side Information

   https://doi.org/10.1109/TIT.2023.3253078  

   Lu, Yuxiang ; Jafar, Syed A. ( May 2023 , IEEE Transactions on Information Theory)

   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
3. Contract design for purchasing private data using a biased differentially private algorithm

   https://doi.org/10.1145/3338506.3340273  

   Khalili, Mohammad Mahdi ; Zhang, Xueru ; Liu, Mingyan ( June 2019 , 14th Workshop on the Economics of Networks, Systems and Computation)

   Personal information and other types of private data are valuable for both data owners and institutions interested in providing targeted and customized services that require analyzing such data. In this context, privacy is sometimes seen as a commodity: institutions (data buyers) pay individuals (or data sellers) in exchange for private data. In this study, we examine the problem of designing such data contracts, through which a buyer aims to minimize his payment to the sellers for a desired level of data quality, while the latter aim to obtain adequate compensation for giving up a certain amount of privacy. Specifically, we use the concept of differential privacy and examine a model of linear and nonlinear queries on private data. We show that conventional algorithms that introduce differential privacy via zero-mean noise fall short for the purpose of such transactions as they do not provide sufficient degree of freedom for the contract designer to negotiate between the competing interests of the buyer and the sellers. Instead, we propose a biased differentially private algorithm which allows us to customize the privacy-accuracy tradeoff for each individual. We use a contract design approach to find the optimal contracts when using this biased algorithm to provide privacy, and show that under this combination the buyer can achieve the same level of accuracy with a lower payment as compared to using the unbiased algorithms, while incurring lower privacy loss for the sellers. 

   more » « less
4. Private selection from private candidates

   https://doi.org/10.1145/3313276.3316377  

   Liu, Jingcheng ; Talwar, Kunal ( June 2019 , Proceedings of the ACM Symposium on Theory of Computing (STOC))
5. Private Information Retrieval When Private Noisy Side Information is Available

   https://doi.org/10.1109/ISIT54713.2023.10206733  

   ZivariFard, Hassan ; Chou, Rémi A. ( June 2023 , IEEE)