publications
2024
- Eureka: A General Framework for Black-box Differential Privacy EstimatorsYun Lu , Malik Magdon-Ismail , Yu Wei, and Vassilis ZikasIn 2024 IEEE Symposium on Security and Privacy (SP) , May 2024
Differential privacy (DP) is a key tool in privacy-preserving data analysis. Yet it remains challenging for non-privacy-experts to prove the DP of their algorithms. We propose a methodology for domain experts with limited data privacy background to empirically estimate the privacy of an arbitrary mechanism. Our Eureka moment is a new link—which we prove—between the problems of DP parameter-estimation and Bayes optimal classifiers in ML, which we believe can be of independent interest. Our estimator uses this link to achieve two desirable properties: (1) black-box, i.e., it does not require knowledge of the underlying mechanism, and (2) it has a theoretically-proven accuracy, depending on the underlying classifier used, allowing plug-and-play use of different classifiers. \{More concretely, motivated by the impossibility of the above task for unrestricted input domains (which we prove), we introduce a natural, application-inspired relaxation of DP which we term relative DP. Intuitively, relative DP defines a mechanism's privacy relative to an input set T, circumventing the above impossibility when T is finite. Importantly, it preserves the key intuitive privacy guarantee of DP while enjoying a number of desirable DP properties—scalability, composition, and robustness to post-processing. We then devise a black-box poly-time (epsilon,delta)-relative DP estimator for any poly-size T—the first privacy estimator to support mechanisms with large output spaces while having tight accuracy bounds. As a result of independent interest, we generalize our theory to develop the first Distributional Differential Privacy (DDP) estimator. We benchmark our estimator in a proof-of-concept implementation. First, using kNN as the classifier we show that our method (1) produces a tight, analytically computed (ε, δ)-DP trade-off of low-dimensional Laplace and Gaussian mechanisms—the first to do so, (2) accurately estimates the privacy spectrum of DDP mechanisms, and (3) can verify a DP mechanism's implementations, e.g., Sparse Vector Technique, Noisy Histogram, and Noisy max. Our implementation and experiments demonstrate the potential of our framework, and highlight its computational bottlenecks in estimating DP, e.g., in terms of the size of δand the data dimensionality. Our second, neural-network-based instantiation makes a first step in showing that our method can be extended to mechanisms with high-dimensional outputs.
@inproceedings{LuMWZ24, author = {Lu, Yun and Magdon-Ismail, Malik and Wei, Yu and Zikas, Vassilis}, booktitle = {2024 IEEE Symposium on Security and Privacy (SP)}, title = {Eureka: A General Framework for Black-box Differential Privacy Estimators}, year = {2024}, volume = {}, issn = {2375-1207}, pages = {165-165}, keywords = {differential privacy; bayes classifier; machine learning; knn}, doi = {10.1109/SP54263.2024.00166}, url = {https://doi.ieeecomputersociety.org/10.1109/SP54263.2024.00166}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, month = may, } - Distributed Differential Privacy via Shuffling Versus Aggregation: A Curious StudyYu Wei, Jingyu Jia , Yuduo Wu , Changhui Hu , Changyu Dong , and 4 more authorsTrans. Info. For. Sec., Jan 2024
How to achieve distributed differential privacy (DP) without a trusted central party is of great interest in both theory and practice. Recently, the shuffle model has attracted much attention. Unlike the local DP model in which the users send randomized data directly to the data collector/analyzer, in the shuffle model an intermediate untrusted shuffler is introduced to randomly permute the data, which have already been randomized by the users, before they reach the analyzer. The most appealing aspect is that while shuffling does not explicitly add more noise to the data, it can make privacy better. The privacy amplification effect in consequence means the users need to add less noise to the data than in the local DP model, but can achieve the same level of differential privacy. Thus, protocols in the shuffle model can provide better accuracy than those in the local DP model. What looks interesting to us is that the architecture of the shuffle model is similar to private aggregation, which has been studied for more than a decade. In private aggregation, locally randomized user data are aggregated by an intermediate untrusted aggregator. Thus, our question is whether aggregation also exhibits some sort of privacy amplification effect? And if so, how good is this “aggregation model” in comparison with the shuffle model. We conducted the first comparative study between the two, covering privacy amplification, functionalities, protocol accuracy, and practicality. The results as yet suggest that the new shuffle model does not have obvious advantages over the old aggregation model. On the contrary, protocols in the aggregation model outperform those in the shuffle model, sometimes significantly, in many aspects.
@article{WeiJWHDLCPW24, author = {Wei, Yu and Jia, Jingyu and Wu, Yuduo and Hu, Changhui and Dong, Changyu and Liu, Zheli and Chen, Xiaofeng and Peng, Yun and Wang, Shaowei}, title = {Distributed Differential Privacy via Shuffling Versus Aggregation: A Curious Study}, year = {2024}, issue_date = {2024}, publisher = {IEEE Press}, volume = {19}, issn = {1556-6013}, url = {https://doi.org/10.1109/TIFS.2024.3351474}, doi = {10.1109/TIFS.2024.3351474}, journal = {Trans. Info. For. Sec.}, month = jan, pages = {2501–2516}, numpages = {16}, } - arXivThe Normal Distributions Indistinguishability Spectrum and its Application to Privacy-Preserving Machine LearningYun Lu , Malik Magdon-Ismail , Yu Wei, and Vassilis ZikasJan 2024
2023
- ePrintFine-Tuning Ideal Worlds for the Xor of Two Permutation OutputsWonseok Choi , Minki Hhan , Yu Wei, and Vassilis ZikasIACR Cryptol. ePrint Arch., Jan 2023
2021
- Searchable Symmetric Encryption with Forward Search PrivacyJin Li , Yanyu Huang , Yu Wei, Siyi Lv , Zheli Liu , and 2 more authorsIEEE Trans. Dependable Secur. Comput., Jan 2021
@article{LiHWLLDL21, author = {Li, Jin and Huang, Yanyu and Wei, Yu and Lv, Siyi and Liu, Zheli and Dong, Changyu and Lou, Wenjing}, title = {Searchable Symmetric Encryption with Forward Search Privacy}, journal = {{IEEE} Trans. Dependable Secur. Comput.}, volume = {18}, number = {1}, pages = {460--474}, year = {2021}, } - How to Make Private Distributed Cardinality Estimation Practical, and Get Differential Privacy for FreeChanghui Hu , Jin Li , Zheli Liu , Xiaojie Guo , Yu Wei, and 3 more authorsIn USENIX Security Symposium , Jan 2021
@inproceedings{DBLP:conf/uss/Hu0LGWGLD21, author = {Hu, Changhui and Li, Jin and Liu, Zheli and Guo, Xiaojie and Wei, Yu and Guang, Xuan and Loukides, Grigorios and Dong, Changyu}, title = {How to Make Private Distributed Cardinality Estimation Practical, and Get Differential Privacy for Free}, booktitle = {{USENIX} Security Symposium}, pages = {965--982}, publisher = {{USENIX} Association}, year = {2021}, }