The de-anonymization of users from anonymized microdata through matching or aligning with publicly-available correlated databases has been of scientific interest recently. While most of the rigorous analyses of database matching have focused on random-distortion models, the adversarial-distortion models have been wanting in the relevant literature. In this work, motivated by synchronization errors in the sampling of time-indexed microdata, matching (alignment) of random databases under adversarial column deletions is investigated. It is assumed that a constrained adversary, which observes the anonymized database, can delete up to a $\delta$ fraction of the columns (attributes) to hinder matching and preserve privacy. Column histograms of the two databases are utilized as permutation-invariant features to detect the column deletion pattern chosen by the adversary. The detection of the column deletion pattern is then followed by an exact row (user) matching scheme. The worst-case analysis of this two-phase scheme yields a sufficient condition for the successful matching of the two databases, under the near-perfect recovery condition. A more detailed investigation of the error probability leads to a tight necessary condition on the database growth rate, and in turn, to a single-letter characterization of the adversarial matching capacity. This adversarial matching capacity is shown to be significantly lower than the random matching capacity, where the column deletions occur randomly. Overall, our results analytically demonstrate the privacy-wise advantages of adversarial mechanisms over random ones during the publication of anonymized time-indexed data.


翻译:最近,通过将匿名化的微观数据与公开可用的相关数据库进行匹配或对齐来去匿名化用户已成为科学研究的焦点。尽管数据库匹配的大部分严格分析都集中在随机扭曲模型上,但对于对抗性扭曲模型,相关文献一直比较缺乏。本文通过同步误差来自于时序数据采样,研究了在对抗性列删除下随机数据库的匹配(对齐)。假设一个受限制的攻击者可以删除最多 $\delta$ 小数列(属性),以阻碍匹配并保护隐私。两个数据库的列直方图被用作不变置换特征,以检测攻击者选择的列删除模式。然后,对列删除模式的检测进行了实际行(用户)匹配方案。该二阶段方案的最坏情况分析得出了满足近乎完美恢复条件下成功匹配两个数据库的充分条件。更详细地研究误差概率导致了对数据库增长速率的严格必要条件,并进而得到对抗性匹配容量的单字母特征化。该对抗性匹配容量显示出显著低于随机匹配容量的情况,其中列删除是随机的。总的来说,我们的结果在分析上证明了在发布匿名化的时序数据时,对抗性机制在隐私方面优于随机机制。

0
下载
关闭预览

相关内容

【2023新书】分布测试的主题和技术,163页pdf
专知会员服务
15+阅读 · 2023年1月19日
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
72+阅读 · 2022年6月28日
【干货书】真实机器学习,264页pdf,Real-World Machine Learning
代码推荐 | 轻松实现各种图匹配 Graph matching.
图与推荐
2+阅读 · 2022年10月22日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
德先生
53+阅读 · 2019年4月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
国家自然科学基金
3+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
2+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年5月12日
Arxiv
12+阅读 · 2021年6月29日
Arxiv
12+阅读 · 2020年12月10日
Arxiv
38+阅读 · 2020年3月10日
Generative Adversarial Networks: A Survey and Taxonomy
Adversarial Transfer Learning
Arxiv
12+阅读 · 2018年12月6日
VIP会员
相关基金
国家自然科学基金
3+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
2+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员