More Like this

1. Differential Privacy with Multiple Selections

   Goel, Ashish; Jiang, Zhihao; Korolova, Aleksandra; Munagala, Kamesh; Sarmasarkar, Sahasrajit (July 2024, Foundations of Responsible Computing (FORC 2025))

   We consider the setting where a user with sensitive features wishes to obtain a recommendation from a server in a differentially private fashion. We propose a ``multi-selection'' architecture where the server can send back multiple recommendations and the user chooses one from these that matches best with their private features. When the user feature is one-dimensional -- on an infinite line -- and the accuracy measure is defined w.r.t some increasing function 𝔥(.) of the distance on the line, we precisely characterize the optimal mechanism that satisfies differential privacy. The specification of the optimal mechanism includes both the distribution of the noise that the user adds to its private value, and the algorithm used by the server to determine the set of results to send back as a response and further show that Laplace is an optimal noise distribution. We further show that this optimal mechanism results in an error that is inversely proportional to the number of results returned when the function 𝔥(.) is the identity function. 

   more » « less
2. Weakly Private Information Retrieval from Heterogeneously Trusted Servers

   https://doi.org/10.1109/ISIT57864.2024.10619321  

   Huang, Yu-Shin; Zhao, Wenyuan; Zhou, Ruida; Tian, Chao (July 2024, IEEE)

   We study the problem of weakly private information retrieval (PIR) when there is heterogeneity in servers’ trustfulness under the maximal leakage (Max-L) metric. A user wishes to retrieve a desired message from N non-colluding servers efficiently, such that the identity of the desired message is not leaked in a significant manner; however, some servers can be more trustworthy than others. We propose a code construction for this setting and optimize the probability distribution for this construction. It is shown that the optimal probability allocation for the proposed scheme essentially separates the delivery patterns into two parts: a completely private part that has the same download overhead as the capacity-achieving PIR code, and a non-private part that allows complete privacy leakage but has no download overhead by downloading only from the most trustful server. The optimal solution is established through a sophisticated analysis of the underlying convex optimization problem, and a reduction between the homogeneous setting and the heterogeneous setting. 

   more » « less
3. Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages

   Asi, Hilal; Feldman, Vitaly; Nelson, Jelani; Nguyen, Huy L; Talwar, Kunal; Zhou, Samson (July 2024, Proceedings of Machine Learning Research)

   We study the problem of private vector mean estimation in the shuffle model of privacy where n users each have a unit vector v^{(i)} in R^d. We propose a new multi-message protocol that achieves the optimal error using O~(min(n*epsilon^2, d)) messages per user. Moreover, we show that any (unbiased) protocol that achieves optimal error requires each user to send Omega(min(n*epsilon^2,d)/log(n)) messages, demonstrating the optimality of our message complexity up to logarithmic factors. Additionally, we study the single-message setting and design a protocol that achieves mean squared error O(dn^{d/(d+2)} * epsilon^{-4/(d+2)}). Moreover, we show that any single-message protocol must incur mean squared error Omega(dn^{d/(d+2)}), showing that our protocol is optimal in the standard setting where epsilon = Theta(1). Finally, we study robustness to malicious users and show that malicious users can incur large additive error with a single shuffler. 

   more » « less
4. Efficient Off-Chain Transaction to Avoid Inaccessible Coins in Cryptocurrencies

   https://doi.org/10.1109/TrustCom50675.2020.00260  

   Rezaeighaleh, Hossein; Zou, Cliff C. (December 2020, 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom))

   null (Ed.)

   Bitcoin and other altcoin cryptocurrencies use the Elliptic-Curve cryptography to control the ownership of coins. A user has one or more private keys to sign a transaction and send coins to others. The user locks her private keys with a password and stores them on a piece of software or a hardware wallet to protect them. A challenge in cryptocurrencies is losing access to private keys by its user, resulting in inaccessible coins. These coins are assigned to addresses which access to their private keys is impossible. Today, about 20 percent of all possible bitcoins are inaccessible and lost forever. A promising solution is the off-chain recovery transaction that aggregates all available coins to send them to an address when the private key is not accessible. Unfortunately, this recovery transaction must be regenerated after all sends and receives, and it is time-consuming to generate on hardware wallets. In this paper, we propose a new mechanism called lean recovery transaction to tackle this problem. We make a change in wallet key management to generate the recovery transaction as less frequently as possible. In our design, the wallet generates a lean recovery transaction only when needed and provides better performance, especially for micropayment. We evaluate the regular recovery transaction on two real hardware wallets and implement our proposed mechanism on a hardware wallet. We achieve a %40 percentage of less processing time for generating payment transactions with few numbers of inputs. The performance difference becomes even more significant, with a larger number of inputs. 

   more » « less
5. Revisiting Model-Agnostic Private Learning: Faster Rates and Active Learning

   Liu, Chong; Zhu, Yuqing; Chaudhuri, Kamalika; Wang, Yu-Xiang (November 2021, Journal of machine learning research)

   Krause, Andreas (Ed.)

   The Private Aggregation of Teacher Ensembles (PATE) framework is one of the most promising recent approaches in differentially private learning. Existing theoretical analysis shows that PATE consistently learns any VC-classes in the realizable setting, but falls short in explaining its success in more general cases where the error rate of the optimal classifier is bounded away from zero. We fill in this gap by introducing the Tsybakov Noise Condition (TNC) and establish stronger and more interpretable learning bounds. These bounds provide new insights into when PATE works and improve over existing results even in the narrower realizable setting. We also investigate the compelling idea of using active learning for saving privacy budget, and empirical studies show the effectiveness of this new idea. The novel components in the proofs include a more refined analysis of the majority voting classifier — which could be of independent interest — and an observation that the synthetic “student” learning problem is nearly realizable by construction under the Tsybakov noise condition. 

   more » « less