安全多方计算(2):隐私信息检索方案汇总分析

安全,多方,计算,隐私,信息检索,方案,汇总,分析 · 浏览次数 : 731

小编点评

**安全多方计算中隐私信息检索方案** **1. 介绍** 隐私信息检索方案是安全多方计算中一个实用的一类方案,可实现多方数据安全查询。该方案可在保护用户隐私的前提下,实现多方数据安全查询。 **2. 3类方案特点** **3. 1. 基于OT的PIR** *依赖技术:RSA公钥密码 *通信开销:RSA公钥传输消耗约0.68MB *计算开销:OT代码基于RSA的基于DH的PIR基于OT的基于Paillier的带关键词的PIR **3. 2. 基于paillier同态加密的PIR** *依赖技术:Paillier同态加密 *通信开销:密文查询向量消耗约1.3MB *计算开销:PA代码基于Paillier同态加密的带关键词的PIR **3. 3. 基于OT的PIR** *依赖技术:RSA公钥密码 *通信开销:RSA公钥传输消耗约0.68MB *计算开销:OT代码基于RSA的基于DH的PIR基于OT的基于Paillier的带关键词的PIR **4. 代码实现** **4. 1. 基于OT的PIR** ```python import rsa import crypt ``` **4. 2. 基于paillier同态加密的PIR** ```python import paillier ``` **5. 总结** 隐私信息检索方案是安全多方计算中一个实用的一类方案,可实现多方数据安全查询。该方案可在保护用户隐私的前提下,实现多方数据安全查询。

正文

学习&转载文章:安全多方计算(2):隐私信息检索方案汇总分析

前言

多头贷问题是网络小额贷款平台放款时所要考虑的一个重要问题。假设银行A有一潜在贷款客户小张,银行A为了足够多的了解小张的信用情况,希望向其他多家银行查询小张贷款情况或信用记录。但因为害怕其他银行抢走该客户,所以银行A不希望泄露自己在查询小张这一事实。是否可以通过技术手段解决银行A的诉求?答案是肯定的,即图1漫画中的“隐私信息检索技术”——一种不泄露查询条件和查询结果的加密技术

图片

图1 隐私信息检索技术应用示例漫画

隐私信息检索(Private InformationRetrieval – PIR,也叫匿踪查询)是安全多方计算中很实用的一项技术,用来保护用户的查询隐私。其目的是保证用户向服务器(数据源方)提交查询请求时,在用户查询信息不被泄漏的条件下完成查询[1]。即整个查询过程中服务器不知道用户具体查询信息及查询出的数据项

一句话总结就是:不泄漏查询条件和查询结果

为什么可搜索加密技术无法替代隐私信息检索技术

通过前面对PIR技术的描述,可知PIR的目的是保护用户查询隐私。提到“保护用户查询隐私”,会有人想到可搜索加密技术,但可搜索加密技术并不能替代PIR技术。

先来简单了解可搜索加密技术。

顾名思义,可搜索加密就是在加密的情况下实现搜索功能,常用于云计算当中。可搜索加密应用示例如图2所示,能够实现将用户的数据进行特殊的加密后上传到云服务器上, 并且可以实现根据关键字进行检索的功能。(更详细内容可阅读本公众号文章:防止云端数据与查询行为泄露—可搜索加密

图片

图2 可搜索加密应用示例

可搜索加密实现密文检索时,过程示例如图3所示。可简单描述为:检索用户提交密文关键字(keyword3),云服务器将密文关键字与密文数据库比对,比对成功后则将对应的密文数据(数据3)返回给检索用户,最终检索用户对拿到的密文数据进行解密。

图片

图3 可搜索加密密文检索示例

整个过程中云服务器不知道检索关键字(keyword3)和检索结果(数据3)对应的原始明文是什么。但是,数据拥有者(不一定是云服务器)监听到检索结果的话,可以直接解密并得到对应的明文。即可搜索加密技术仅能阻止云服务器获得用户查询隐私,不能阻止数据拥有者获得用户查询隐私(这很正常,云计算环境下,云服务器中一段密文数据的拥有者和检索者,可能是同一用户)。

  • 总结一下:可搜索加密仅能保护查询条件,不能保护查询结果

3类场景隐私信息检索方案

为了加强保护用户查询隐私,使得查询条件和查询结果仅查询用户可知,安全多方计算中的PIR技术应运而生。目前常见的PIR方案实现有3类,分别是基于不经意传输(Oblivious Transfer,OT)的PIR实现基于同态加密的PIR实现和keyword PIR实现。

其中基于不经意传输的PIR和基于同态加密的PIR需要检索用户提前知道被检索数据在服务端数据库中索引号。

3类方案的实现过程介绍如下。

基于不经意传输的PIR实现

基于不经意传输的PIR实现过程如图4所示(不经意传输协议此处不在赘述,更多内容可阅读本公众号文章:安全多方计算(1):不经意传输协议),主要利用的是n选1的OT协议。

图片

图4 基于不经意传输的PIR实现过程

基于OT的PIR实现过程有5个重要步骤:

  1. 服务端有\(n\)条数据,则产生\(n\)个RSA公私钥对,并将\(n\)个私钥保留,\(n\)个公钥发送给用户端。
  2. 用户随机产生一个大整数key(key为第5步中的解密密钥),已知用户要检索第\(t\)条数据,则用户用收到的第\(t\)个RSA公钥加密大整数key,将加密结果\(s\)发送给服务端。
  3. 服务端用保留的\(n\)个RSA私钥,依次尝试解密\(s\),获得\(n\)个解密结果,依次为\((key1,key2,…,keyt,…,keyn)\)
  4. 服务端利用对称加密算法(此处为AES算法),利用\((key1,...,keyn)\),加密对应的消息\((m1,...,mn)\),将产生的密文消息\((M1,...,Mn)\)发送给用户。
  5. 用户利用第2步中的key,对第\(t\)条密文\(M_t\)进行对称解密「即检索用户需要提前知道检索索引」,则得到想要检索的第\(t\)条原始明文消息\(m_t\)

代码实现

基于同态加密的PIR实现

基于同态加密的PIR实现过程如图5所示,此处采用paillier加法半同态加密算法[2],paillier同态加密算法计算过程参见文献2,此处不赘述,但强调3个paillier算法特点:

paillier具有加法同态性和标量乘法同态性,即
image
在该方案中,同态计算体现在:\(\sum_{i=1}^nm_i*\nu_i\),是【m*c】和【c+c】,所以预测这里不是paillier,感谢园友的提醒。

(1)可以实现两个密文加法计算【c+c】;

(2)可以实现一个密文与一个明文相乘【c*m】;

(3)由于加密时用到随机数,所以相同的明文、相同的密钥,可以产生很多个不同的密文,这些不同的密文解密后都能得到相同的原始明文。

图片

图5 基于同态加密的PIR实现过程

基于paillier同态加密的PIR实现过程有4个重要步骤:

  1. 用户端产生同态加密公钥\(pk\)和私钥\(sk\)
  2. 已知服务端有\(n\)条数据,用户要检索第\(t\)条数据,则产生一个\(n\)维密文向量\(vector=(v1,…,vn)\),其中第\(t\)项是公钥\(pk\)加密数字1后的密文「即检索用户需要提前知道检索索引」,其他项是公钥\(pk\)加密数字0后的密文。将\(vector\)和公钥\(pk\)发送给服务端,paillier算法第3个特点保证了\(vector\)中的\(n\)条密文都不重复,保证服务端无法猜出哪一条是数字1的密文。
  3. 服务端\(vector\)\(n\)条明文数据集做向量内积运算,得到密文结果\(en\_result\),将\(en\_result\)发送给用户端。同态加密的密文计算结果解密后与明文计算结果相等,相当于\(en\_result=E(m1*0 + … + mt-1*0 + mt*1 + mt+1*0+ … + mn*0, pk) = E(mt, pk)\)
  4. 用户端利用私钥\(sk\)\(en\_result\)进行解密,得到想要检索的第\(t\)条原始明文消息\(mt\)

代码实现

keyword PIR实现

实际上,在大多数的查询场景中,查询方往往不知道自己要查询的数据的索引号【即要检索的是第几个(索引)】,而大多根据关键词进行查询,此类方案又称keyword PIR,可以利用paillier同态加密拉格朗日插值多项式实现(拉格朗日插值多项式细节可阅读本公众号文章:秘密共享—隐私计算和区块链共识中的榫卯),具体实现过程如图6所示。

图片

图6 keyword PIR实现过程

keyword PIR实现过程有5个重要步骤:

  1. 服务端有明文数据集【关键词,数据】\(((x1,m1),…,(xn,mn))\),对此明文数据集进行拉格朗日多项式插值,插值结果即为最高次幂为\(n-1\)的多项式\(g(x)\);对于图6中的多项式\(f(x)\)\(f(x) = (x-x1)*(x-x2)*…*(x-xn)\),展开后即为图6中的\(f(x)\)。数据集中任意一个点(\(xi,mi)\),满足\(f(xi)=0,g(xi)=mi\)
  2. 用户生成paillier同态加密公钥\(pk\)和私钥\(sk\)
  3. 对于待查关键字\(xt\),用户利用\(pk\)分别加密\(xt\)的1次方到\(xt\)\(n\)次方,组成密文向量\(vector\),发送给服务端。
  4. 服务端利用密文向量\(vector\),和\(f(x)、g(x)\)的系数,分别计算同态密文\(E(f(xt))、E(g(xt))\),将计算结果发送给用户。
  5. 用户利用私钥\(sk\)对两条密文进行解密,如果\(f(xt)=0\),则\(g(xt)\)即为检索结果;否则检索结果为空。

代码实现

方案验证及总结分析

前文对3类PIR方案实现方法做了描述,此处对3类方法做一个全面的比对分析,方便读者对3类方案有一个更直观的理解。

本文所提PIR方案理论分析

表1所示的表格,分别从依赖技术、通信开销、计算开销等方面对3类PIR方案特点做了总结。

表1 3类PIR方案特点总结

依赖技术 通信量与数据集(n条)关系 需要提前知道被检索数据索引号 计算开销与数据集(n条)关系
基于OT的PIR 公钥密码,对称密码 n个RSA公钥n条AES密文 n次公钥解密n次对称加密
基于同态加密PIR 同态加密 n+1条同态密文 3n次同态加密
Keyword-PIR 多项式插值;同态加密 n+2条同态密文 5n次同态加密2次多项式构造
  • 在计算开销上,由于同态加密计算开销大于RSA计算开销,所以基于OT的PIR方案计算开销有优势;
  • 通信开销上,如果服务端每条明文数据都较长,如数千字节,则基于同态加密PIR通信开销较小。

代码实例验证

本环节,我们用python代码分别实现了基于OT的PIR和基于同态加密的PIR,让读者对PIR性能有更清晰的了解。我们模拟服务端有一个漏洞库,共有2245条数据(数据为绿盟真实漏洞库数据,原始数据数十万条,此处仅选取一部分用于实验),用户输入“软件名称+具体版本号”可查询对应的漏洞信息,查询过程中不会泄漏检索条件和检索结果。此部分仅展示用户获知检索项在服务端中的索引号后(索引号如何获取非本文重点,此处略过),分别模拟利用基于OT的PIR和基于同态加密的PIR实现漏洞信息检索。

图片

图7 基于OT的PIR代码实验结果

图7为基于OT的PIR代码实现,网络为内部局域网,服务端为低配Ubuntu虚拟机,模拟结果总耗时3.3秒通信开销RSA公钥传输消耗约0.68MB,全量AES密文传输消耗约5.6MB

图片

图8 基于paillier同态加密的代码实验结果

图8为基于paillier同态加密的PIR代码实现,相同配置下,计算开销耗时117秒通信开销密文查询向量消耗约1.3MB网络开销,检索结果传输消耗约0.14MB。可以明显比对出前两类PIR方案在计算开销和网络开销上的差异。

总结

本文介绍了安全多方计算中很实用的一类方案——隐私信息检索方案,此类方案可在保护用户隐私的前提下,实现多方数据安全查询。另外,分别介绍了3种不同的实现方法原理,并对其进行理论对比分析,且对其中的两类方法做了代码实现。通过理论分析和实验对比,能够让读者对隐私信息检索有一个更直观的认识。

参考文献

[1]https://blog.csdn.net/hellompc/article/details/103784360

[2]Paillier P . Public-key cryptosystemsbased on composite degree residuosity classes[J]. Advances in CryptologyLeurocrypt, 2004.

  • 程序实现:
    • 拉格朗日插值法
    • OT代码
      • 基于RSA的
      • 基于DH的
    • PIR
      • 基于OT的
      • 基于Paillier的
      • 带关键词的PIR

与安全多方计算(2):隐私信息检索方案汇总分析相似的内容:

安全多方计算(2):隐私信息检索方案汇总分析

> 学习&转载文章:[安全多方计算(2):隐私信息检索方案汇总分析](https://mp.weixin.qq.com/s/7JF-g6m8RLPWf0QgbYE-7g) ## 前言 **多头贷问题**是网络小额贷款平台放款时所要考虑的一个重要问题。假设银行A有一潜在贷款客户小张,银行A为了足够多的

安全多方计算(1):不经意传输协议

学习&转载文章:安全多方计算(1):不经意传输协议 前言 在安全多方计算系列的首篇文章(安全多方计算之前世今生)中,我们提到了百万富翁问题,并提供了百万富翁问题的通俗解法,该通俗解法可按图1简单回顾。 图1 百万富翁问题通俗解法 百万富翁问题通俗解法场景中,我们可以将Alice和Bob的诉求总结如下

安全多方计算(5):隐私集合求交方案汇总分析

学习&转载文章:安全多方计算(5):隐私集合求交方案汇总分析 前言 随着数字经济时代的到来,数据已成为一种基础性资源。然而,数据的泄漏、滥用或非法传播均会导致严重的安全问题。因此,对数据进行隐私保护是现实需要,也是法律要求。隐私集合求交(Private Set Intersection, PSI)作

多方安全计算(3):MPC万能钥匙-混淆电路

学习&转载文章:多方安全计算(3):MPC万能钥匙-混淆电路 前言 我们在讲解不经意传输(Oblivious Transfer,OT)的文章(安全多方计算(1):不经意传输协议)中提到,利用n选1的不经意传输可以解决百万富翁问题(两位富翁Alice和Bob在不泄露自己真实财富的情况下比对出谁更有钱)

【隐私计算笔谈】MPC系列专题(十):安全多方计算下的集合运算

学习&转载文章:【隐私计算笔谈】MPC系列专题(十):安全多方计算下的集合运算 集合运算 集合可以通俗地描述为确定的一堆东西。如有一个集合$𝐴$,一个元素$𝑐$要么属于集合$𝐴$,记做$𝑐\in 𝐴$;要么不属于集合$𝐴$,记做$𝑐∉𝐴$,元素$𝑐$不能既属于集合$𝐴$又不属于$

隐私集合求交(PSI)协议研究综述

摘要 隐私集合求交(PSI)是安全多方计算(MPC)中的一种密码学技术,它允许参与计算的双方,在不获取对方额外信息(除交集外的其它信息)的基础上,计算出双方数据的交集。隐私集合求交在数据共享,广告转化率,联系人发现等领域有着广泛的应用空间。本文对隐私集合求交的各项实现技术做了介绍和对比,对隐私集合求

MPC:百万富翁问题

学习文章:“一起学MPC:(一)百万富翁问题”和“【隐私计算笔谈】MPC系列专题(一):安全多方计算应用场景一览” 百万富翁问题 将问题具体化: Alice有$i$亿元,Bob有$j$亿元,为方便描述,我们限定$0

多方安全计算(4):MPC万能积木-秘密共享

学习&转载文章:多方安全计算(4):MPC万能积木-秘密共享 前言 在之前的文章(多方安全计算(3)MPC万能钥匙:混淆电路中,我们对MPC中一类通用方案混淆电路(GC)与密文比较策略做了介绍。混淆电路通过将任务抽象为电路以及对基础电路提供加密方案达到了万能钥匙的效果。在姚期智先生提出GC方案不久后

多方安全计算(6):MPC中场梳理

学习&转载文章:多方安全计算(6):MPC中场梳理 前言 诚为读者所知,数据出域的限制约束与数据流通的普遍需求共同催生了数据安全计算的需求,近一两年业界又统将能够做到多方数据可用不可见的技术归入隐私计算范畴。粗略来说,隐私计算可分为以联邦学习为代表的机器学习类升级方案、以可信硬件为基础的可信执行环境

对于多方安全计算,你是否也有这样的疑惑?

学习&转载文章:对于多方安全计算,你是否也有这样的疑惑? 问题 假设多方安全计算中有两个参与方$P_0$和$P_1$,其中$P_0$拥有$x$,$P_1$拥有$y$,双方想要在不暴露自己拥有的数据的同时计算一个结果$z$,且$z=x+y$。那么不管用哪种协议进行计算得到最终结果$z$,并且公布给双方