专栏首页arxiv.org翻译专栏非对称泄露下的私人信息检索(CS IT)
原创

非对称泄露下的私人信息检索(CS IT)

在各种情况下,对私人信息检索 (PIR) 问题的信息理论公式进行了研究。对称私有信息检索 (SPIR) 是一种变体,在这种变体中,用户能够从 N 非共存的复制数据库中私自检索 K 信息中的一个,而不知道其余 K-1 信息的任何信息。然而,对于某些应用来说,完美隐私的目标可能太过繁琐。在本文中,我们研究了是否可以通过放宽用户和数据库的隐私定义来增加 SPIR 的信息理论容量(相当于最小下载成本的倒数)。这种放宽与隐私可以换取通信效率的应用有关。我们引入并研究了在每个方向上具有不同隐私泄漏预算的非对称泄漏PIR(AL-PIR)模型。对于用户隐私泄露,我们通过一个非负常数 ε 的函数来约束所有可能实现的 DB 查询之间的概率比。对于 DB 隐私,我们通过一个非负常数 δ 的函数来约束不希望的消息、查询和答案之间的相互信息。我们提出了一种通用的 AL-PIR 方案,实现了对任意 εδ 的最优下载成本的上界。我们证明,AL-PIR 的最优下载成本的上界为 D^{*}(ε,δ)\leq 1+\frac{1}{N-1}-\frac{δe^ε}{N^{K-1}-1}。其次,我们得到下载成本的信息论下限为 D^{*}(ε,δ)\ge 1+\frac{1}{Ne^ε-1}-\fracδ{(Ne^ε)^{K-1}-1}。两个边界之间的差距分析表明,我们的 AL-PIR 方案在 ε=0 时是最优的,即在完美的用户隐私下,对于任何 (ε,δ),它在 \frac{N-e^{-ε}}{N-1} 的最大乘法差距内是最优的。

原文题目:Asymmetric Leaky Private Information Retrieval

原文:Information-theoretic formulations of the private information retrieval (PIR) problem have been investigated under a variety of scenarios. Symmetric private information retrieval (SPIR) is a variant where a user is able to privately retrieve one out of K messages from N non-colluding replicated databases without learning anything about the remaining K-1 messages. However, the goal of perfect privacy can be too taxing for certain applications. In this paper, we investigate if the information-theoretic capacity of SPIR (equivalently, the inverse of the minimum download cost) can be increased by relaxing both user and DB privacy definitions. Such relaxation is relevant in applications where privacy can be traded for communication efficiency. We introduce and investigate the Asymmetric Leaky PIR (AL-PIR) model with different privacy leakage budgets in each direction. For user privacy leakage, we bound the probability ratios between all possible realizations of DB queries by a function of a non-negative constant ε. For DB privacy, we bound the mutual information between the undesired messages, the queries, and the answers, by a function of a non-negative constant δ. We propose a general AL-PIR scheme that achieves an upper bound on the optimal download cost for arbitrary ε and δ. We show that the optimal download cost of AL-PIR is upper-bounded as D^{*}(ε,δ)\leq 1+\frac{1}{N-1}-\frac{δe^ε}{N^{K-1}-1}. Second, we obtain an information-theoretic lower bound on the download cost as D^{*}(ε,δ)\geq 1+\frac{1}{Ne^ε-1}-\fracδ{(Ne^ε)^{K-1}-1}. The gap analysis between the two bounds shows that our AL-PIR scheme is optimal when ε=0, i.e., under perfect user privacy and it is optimal within a maximum multiplicative gap of \frac{N-e^{-ε}}{N-1} for any (ε,δ).

原文作者:Islam Samy, Mohamed A. Attia, Ravi Tandon, Loukas Lazos

原文地址:https://arxiv.org/abs/2006.03048

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 12亿网民信息遭黑客攻破!全文检索最大服务商4TB数据,无需密码谷歌云上查看

    人类历史上,可能是第二大个人信息泄露事故发生了!12亿网民的隐私信息,正在毫无遮掩的暴露在互联网上。

    新智元
  • 【火绒安全周报】谷歌将停用Cookies;“军工级”武器库泄露,企业宜早做防范

    近日,谷歌宣布了新的定向广告计划,承诺在Chrome对Cookie(小文本文件)的支持于2022年初结束后,不再使用其他方式跟踪互联网上的个人用户。这并不是要在...

    用户6477171
  • 网络安全自学篇(二十三)| Web安全学习路线及木马、病毒和防御初探

    自幼受贵州大山的熏陶,养成了诚实质朴的性格。经过寒窗苦读,考入BIT,为完成自己的教师梦,放弃IT、航天等工作,成为贵财一名大学教师,并想把自己所学所感真心传授...

    天钧
  • 邮件月刊第一期——数字时代如何管理你的数字隐私

    这是我第一次做邮件月刊,顾名思义,它首先以邮件形式送达到订阅者手中。当然,你仍然在博客和RSS列表能够看到邮件月刊,但是我更希望,读者能以邮件订阅的方式,第一时...

    BessCroft
  • 【火绒安全周报】微软否认其云服务遭入侵 将强制隔离SolarWinds Orion应用

    据报道,黑客滥用微软的 Microsoft 365 平台对美国财政部进行了长达数月的监控。对此,微软表示其云服务未遭到入侵。随后其发布了 IT 管理员指南,帮助...

    用户6477171
  • 数据全裸时代,你的隐私有多容易获取?

    大家好我是痴海,一位转型做增长的爬虫师,由于工作的缘故,对于身边许多信息都非常敏感。上个月朋友圈有很多人都在晒四六级成绩,有人欢喜有人忧愁,而我却感受到深深的恐...

    kbsc13
  • 为什么我3岁的儿子有不良信用记录?儿童数据泄露问题暗潮汹涌

    这一次的泄露的数据不同以往,其信息所属者多是3-20岁的未成年人。具体来说是1998年到2015年出生的儿童的就诊记录。

    华章科技
  • 银行的云计算应用

    1963 年,DARPA(美国国防高级研究计划局)向麻省理工学院提供了约 200 万美元的津贴,启动了著名的 MAC 项目,要求麻省理工开发“多人可同时使用的电...

    用户6900693
  • 领英2/3用户数据泄露,包括中国,邮箱学校工作地点统统流出

    有些甚至含有地理定位信息,从地理位置最新更新时间来看,有可能是2020年之后的最新数据,而非2016年泄露的老数据重新整合。

    量子位
  • 从“万豪泄露事件”看数据安全整个大环境

    11月30日,万豪国际集团发布声明称,公司旗下喜达屋酒店的一个客房预订数据库被黑客入侵,在2018年9月10日或之前曾在该酒店预定的最多约5亿名客人的信息或被泄...

    C4rpeDime
  • 前端该知道些密码学和安全上的事儿

    在密码学的世界里加密之前的消息被称为明文 plaintext,加密之后的消息被称为密文 ciphertext,如果一段密文需要被解密再阅读,这个过程被称之为 d...

    icepy
  • 技术导向的创业公司必须关注IT安全的三大原因

    随着越来越多的企业加入这样一个热潮,即推出下一个旗舰级应用,网络和移动应用现在已经随处可见了。据AppBrain称,迄今为止Android市场上有近280万个应...

    santana2000
  • 是谁泄露了我的信息?

    VRPinea
  • 中国BAT巨头Web浏览器隐私和安全问题

    1. 概述 在奥斯丁举行的互联网自由和开放通信研讨会 FOCI 16会议上,加拿大多伦多大学公民实验室的研究人员总结了中国三大巨头的浏览器——阿里巴巴的 UC ...

    FB客服
  • 火车票中的社会工程学信息

    经常在朋友圈看到好友晒旅行的火车票. 火车票有我们的姓名及经过脱敏处理的身份证信息, 但仅仅屏蔽了出生的月份日期,通过校验位暴力遍历便可筛选可能的30余组号码....

    Spaceack
  • 14个因安全事故引咎辞职的大BOSS

    美国OPM公司主管Katherine Archuleta是最近因数据泄露事件离职的受害人,但她绝不是第一个。如果你从事信息安全保障这份职业,那你的工作就毫无安全...

    FB客服
  • 警告!你的隐私正在被上亿网友围观偷看!

    「Everything」这个软件想必很多同学都有听过,是一款非常好用的文件搜索软件,很多同学把它设置为开机必启动项之一。

    GitHubDaily
  • 警告!你的隐私正在被上亿网友围观偷看!

    「Everything」这个软件想必很多同学都有听过,是一款非常好用的文件搜索软件,很多同学把它设置为开机必启动项之一。

    数据森麟
  • 警告!你的隐私正在被上亿网友围观偷看!

    「Everything」这个软件想必很多同学都有听过,是一款非常好用的文件搜索软件,很多同学把它设置为开机必启动项之一。

    猴哥yuri

扫码关注云+社区

领取腾讯云代金券