专栏首页包罗万想GCAC32 9.12 A fun application: private information retrieval

GCAC32 9.12 A fun application: private information retrieval

参考资料:

1. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.1099&rep=rep1&type=pdf

2. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=xxwxjsjxt200707007

找不到合适的内容,找了篇综述,大概了解这个概念是在干什么就可以了。

9.12 A fun application: private information retrieval私有信息检索

1. Introduction

私有信息检索(Private Information Retrieval,简称 PIR)是指用户向数据库提交查询时,在用户的私有信息不被泄露的情况下完成查询。该协议被引申为对称性的私有信息检索(sPlR),即要求数据库的私有信息也要得到保护而不被泄露。私有信息检索问题在安全多方计算领域有着广阔的应用前景,例如,多个情报部门的合作查询。假设部门A想要查询部门B所拥有的数据库,但是部门A的查询条件是敏感信息,不能泄漏给部门B;同时,部门B拥有的数据记录涉及隐私,对于部门A不查询的记录,部门B应该尽可能地确保数据记录不被泄漏。以上情景为安全查询问题的典型应用,在商业竞争、军事合作等多个领域(如专利数据库查询、股票数据库查询,数字产品的网上交易等),私有信息检索问题也普 遍存在。

1995年chor等首次提出了PIR的概念,并给了一个有效的解决方案,该方案通过K个互不通信的数据库副本共同协作完成查询,使通信复杂度达到o(n 1/lgk),这种通过多个数据库副本实现的 PIR的研究方法称作是信息论私有信息检索。

私有信息检索问题描述为,假设Alice和Bob分别作为用户方和数据库方参与计算,Bob存储的数据表示为一个n.bits的字符串x=x1,…,xn。Alice用户查询索引为i∈{1,…,n).Alice对Bob提出查询请求,希望从B0b那里检索得到xi,但是不希望Bob知道自己对xi感兴趣;同时Bob也不 愿意Alice知道除xi以外的数据库信息,如何在这种情况下完成查询就是私有信息检索问题。

信息论私有信息检索通过多个互不通信的数据库副本服务器,允许用户向不同的服务器提交不同的查询,然后合并这些服务器的应答消息得到最终的查询结果,整个过程中任何单一的服务器都没有得到关于用户的私有信息。

2.Motivation

在本节中,我们给出了PIR协议的应用示例。我们还解释了为什么某些幼稚的方法不能很好地发挥作用,不能被视为PIR解决方案。

2.1 Application Examples

专利数据库。如果专利服务器知道用户感兴趣的专利,则如果用户是研究人员,发明人或投资人,这可能给用户带来很多问题。想象一下,科学家发现了一个很棒的主意,例如“ 2 + 2 = 4”。自然,他想申请专利。但首先,他在国际专利数据库中检查是否已存在此类或类似专利。该服务器的管理员可以访问科学家的查询“是否有2 + 2 = 4之类的专利”,这会自动为他提供以下信息:

•“ 2 + 2 = 4”可能是一项发明。为什么不尝试首先申请专利呢?

•科学家(或研究实验室)所在的区域也很显眼。

两种观察都非常关键,不应揭露。PIR解决了这个问题:用户可以公开使用信用卡支付下载一项专利的费用;服务器将不知道用户刚刚下载了哪项专利。

药品数据库。通常,制药公司专门从事药物发明或收集有关基本成分及其特性的信息(药品数据库)。合成新药的过程需要有关该数据库中几个基本成分的信息。为了隐藏公司的计划,药物设计师购买了整个药物数据库。如果设计人员使用PIR协议仅购买有关所需的一些基本组件的信息,则可以避免这些巨大的花费。

媒体数据库。这些是电子出版物,音乐(mp3)文件,照片,视频等的商业档案。如上所示,将客户数据置于服务器的信任中太冒险了。在这种情况下,用户可能有兴趣在在线购买数字产品之一时从服务器隐藏其偏好。这意味着,用户可能对PIR协议感兴趣。

学术实例。国防部特种作战部门计划在R区域进行行动。要获得R的高分辨率地图,应向IT部门的地图数据库提出适当的请求。因此,IT部门的员工可以弄清楚,即将在区域R中进行特殊操作。是否可以将秘密保留在特种作战部门内部,并仍然在外部数据库处理查询?如果使用PIR,通常是可能的。

Isabelle Duchesnay提出了另一种假设的应用。间谍处理各种国家机密的资料集。在他的目录中,每个秘密都带有诱人的标题,例如“ Abu Nidal在哪里”。他不会接受以一个价格为代价,甚至不只透露一个以上秘密的部分信息而泄露两个秘密。您(潜在的买家)不愿让他知道您想获取哪个秘密,因为他对自己特定利益的了解可能是他出售给他人的宝贵秘密(标题为“谁正在寻找恐怖分子”) )。您可以使用PIR私下检索您选择的秘密。双方都很高兴。

2.2 Naive Approaches And Why They Do Not Work

至少有两种直接解决PIR问题的方法。两者都无法解决现实世界中的问题,但它们为我们指出了实际PIR解决方案必须具备的特性。

整个数据库下载。从理论上讲,整个数据库传输(从服务器到客户端)解决了PIR问题:客户端可以处理数据库本地副本上的查询。因此,服务器不了解用户查询的内容,因此,服务器不了解用户首选项。由于用户必须为数据库的所有记录付费,因此这种方法无法真正应用。通讯的额外成本等于数据库的大小。但是,与整个数据库内容的成本相比,此成本通常可以忽略不计。

匿名化技术。使用流量匿名化技术,用户可以匿名向服务器发送查询并匿名接收答案。另外,使用匿名支付系统,用户可以匿名执行查询。有人可能认为这是一种PIR解决方案。并非如此,因为服务器仍可以收集有关用户首选项的一些常规统计信息。例如,服务器可以跟踪访问的记录比其他记录更多。或者,服务器可以计算在给定的时间间隔内已访问了多少条特定记录。基于此类统计信息的数据挖掘和其他一些工作可能会破坏用户的隐私。这种方法的另一个缺点是,大多数网络匿名化技术以及支付匿名化技术都是:

1.依赖于第三方的信任方(我们又回到了开始:客户端现在必须信任第三方而不是信任服务器。)

2.当所有参与者与一个用户合作时,就会在“全反一”攻击下变得不安全。

3 PIR Approaches

自从PIR问题在[19]中首次提出以来,就PIR主题发表了20多篇科学论文。我们根据作者在这些论文中依赖的假设对结果进行分类。由于空间限制,甚至没有解释一种算法。相反,给出了一些算法的基本思想。

3.1 Theoretical Private Information Retrieva

“理论上”代表以下事实:独立于作弊者的计算能力,假定用户的隐私是坚不可摧的。乔等证明,任何理论上的PIR解决方案都具有一个下限等于数据库大小的通信。因此,就通信量而言,下载整个数据库是最佳解决方案。这样的解决方案称为琐碎的。因此,非平凡的PIR解决方案是一种通信量小于数据库大小的解决方案。

考虑到获得非平凡的理论PIR解决方案的想法,Chor等人放松问题设置。他们假设有几个(而不是一个)彼此不通信且具有相同数据的数据库服务器。该假设使非平凡的理论PIR可行。([19]中最基本的想法是将几个查询发送到多个数据库。查询是以这种方式构造的,即它们不向服务器提供有关用户感兴趣的记录的信息但是,使用查询的答案,用户可以构建所需的记录。)还有一种情况是,最多允许t台服务器与用户合作。

3.2 Computational Private Information Retrieval

为了获得更好的通信复杂性,Chor和Gilboa削弱了另一个假设。“计算性”是指假定数据库服务器受到计算限制。即,在适当的难处理性假设下,数据库无法获取有关i的信息。对于每个ε> 0,提出了两个具有通信复杂度O(Nε)的数据库计算PIR方案。

在[47]中,Ostrovsky和Shoup构建了PIR协议,可以选择以某种方式在数据库中写入第i条记录,即数据库服务器不知道i。对于具有两个或更多服务器的理论PIR和计算PIR,都有协议。例如,对于具有三台服务器的理论PIR,它们提供了通信复杂度为O(N1 / 3 log3 N)的协议。具有多对数通信复杂性的计算PIR协议需要O(logN)轮次,而本次审查中大多数PIR方案只需要一轮。

具有单个数据库的计算PIR。回想一下,在有关PIR的第一篇论文中,已经证明,对于单个数据库,理论上的PIR问题没有非平凡的解决方案。出人意料的是,用难处理性假设代替信息理论安全性可以为单个数据库模式实现非平凡的PIR协议[38]。对于任何ε> 0,其通信复杂度均为O(Nε)。它们使用难解性假设,如[30]中所述。(基本方法是对查询进行加密,服务器仍然可以使用特殊算法对其进行处理。但是,服务器既不能识别明文查询也不能识别结果。结果只能由客户端解密。)

这也是第一个单一数据库协议,设计人员在其中考虑并提供数据库隐私(请参见第3.3节)。使用另一个难处理的假设[15],Cachin等。演示了具有多对数通信的单个数据库计算PIR协议。与[38]中的多项式通信复杂度相比,这是一个改进。该结果看起来特别有效,因为用户必须发送最少的logN位以仅寻址数据库中的第i位(他想要接收的位),而与协议是否保留隐私无关。效果更好的方案出现在[37]中。

3.3 Symmetrical Private Information Retrieval

对称PIR是一个PIR问题,其中考虑了数据库的隐私。即,对称PIR协议必须防止用户在会话期间学习多个数据库记录。显然,对称的保密性(数据库保密性)对于实际应用是非常重要的属性,因为只有这样才能进行有效的计费。[38]中首先考虑了针对单个服务器的对称PIR协议。对于[28]中考虑的几个服务器。

3.4 Hardware-based Private Information Retrieval

Smith和Safford [60,61]在假设使用特殊防篡改设备的假设下考虑了单个数据库的PIR问题。要理解基本思想,请设想在服务器端安装了安全协处理器(SC)[64、59、31]。用户加密查询“给我第i条记录”,并将其发送给SC进行处理。SC解密查询,进行处理,然后加密答案并将其发送给用户。服务器没有任何查询证据,因为

1. SC的主要属性是安装SC的服务器无法访问SC的内置RAM。因此,服务器无法看到(已解密的)用户查询的外观。

2.为了处理查询,SC从数据库中读取所有记录,而不显示用户感兴趣的记录。

本文分享自微信公众号 - 包罗万想(An-mind),作者:安包

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Dan Boneh密码学笔记12

    12.Public key encryption from Diffie-Hellman

    安包
  • Security and Privacy on Blockchain

    Snow White是第一个被证明是安全的,稳定可重构的PoS协议,其涉众分布不断增加。该协议提出了一种保证安全的腐败延迟机制,即、在零星参与下的稳健性,以及在...

    安包
  • 论文扫读-隐私保护+机器学习系列05

    https://baijiahao.baidu.com/s?id=1632887716655389243&wfr=spider&for=pc

    安包
  • Linux文件访问控制列表、su命令与sudo服务

    基于普通文件或目录设置ACL其实就是针对指定的用户或用户组设置文件或目录的操作权限。另外,针对某个目录设置了ACL。则目录中的文件会继承其ACL;针对文件设置了...

    心跳包
  • Linux——用户管理

    /etc/passwd 从文件名称看是存储密码相关的,但是这个已经是历史,心在主要存储的使用户名称

    羊羽shine
  • Linux笔记6.权限及用户

    章鱼喵
  • [源码] Titan留言板 - Titan的第一个开源项目

    1. 单页面的简单实现留言板功能 2. 做了安全过滤,有效防止SQL注入与XSS等安全问题。 3. AJAX异步提交查询留言、提交留言功能。 4. 校验用户输入...

    泰坦HW
  • python图形用户界面(四):教你实现一个简单实用的计时器

    本系列课程是针对无基础的,争取用简单明了的语言来讲解,学习前需要具备基本的电脑操作能力,准备一个已安装python环境的电脑。如果觉得好可以分享转发,有问题的地...

    用户7054460
  • Entity Framework DBFirst尝试

    “Database First”模式我们称之为“数据库优先”,前提是你的应用已经有相应的数据库,你可以使用EF设计工具根据数据库生成数据数据类,你可以使用Vis...

    aehyok
  • 磊哥测评之数据库saas篇:腾讯云控制台、DMC和小程序

    随着云计算和数据库技术的发展,数据库正在变得越来越强大。数据库的性能如处理速度、对高并发的支持在节节攀升,同时分布式、实时的数据分析、兼容主流数据库等强大的性能...

    磊哥测评

扫码关注云+社区

领取腾讯云代金券