iNews新知科技 关注科技，自有新知
谷歌是如何从学术界摘果子来解决工业界实际问题的呢？
谷歌这个开源库的主要工作就是设计一个切实可行的密码学安全计算协议，其目的是为了工业界的使用。
01问题模型
有两方各自拥有包含用户身份的数据集，其中一方还拥有与用户身份相关的一个整数，例如该整数可以是该用户的交易金额。双方想知道如下内容：
(1) 双方拥有的共同用户数量；
(2) 在不泄露用户输入的任何隐私信息下，这些共同用户所对应的整数之和。
这就是一个隐私交集和（PIS）问题。
该问题不是一个空想出来的问题，而是来自于企业的具体需求。
例如在广告战中，计算具体广告转化率，也就是打广告的效果。有多少人因为广告而购买了商品。在该需求中，可能涉及到多个企业。这是在企业合作中经常会出现的情况。
这个问题具有重要的实际价值，而且在很多场景下都需要，具有共性。
02技术框架
而谷歌这里定义的PIS是除了PIS所完成的功能外，还能够对交集做聚合计算。显然这会带来额外的计算开销。
注意，聚合就是对同一属性的元素求和。
谷歌开源库做的事就是以PSI方案为基石，对其进行扩展。将其扩展为在不泄露交集的情况下，能够在相应的属性上做聚合计算。
所以该开源库的架构是：
PSI + 对交集元素求和（在不泄露交集元素的前提下）
03技术路线
一种方法是基于随机不经意传输（Random Oblivious Transfer），该方法利用了不经意PRF（OPRF）技巧，获得了隐藏交集元素身份的功能。然后利用加法同态加密，实现了在不泄露交集元素的情况下提供聚合功能。
第二种方法是在加法同态加密下，利用加密的Bloom过滤器构造了一个oblivious协议。聚合功能依然通过加法同态加密实现。
除了以上两个协议外，还构造了第三个协议，称为DDH类型协议。该协议基于传统的集合交集协议，使用Pohlig Hellman 密文（基于判断类DDH问题的困难性）。这种类型协议可以看做是使用共享密钥的不经意PRF。同样，聚合功能也是通过加法同态加密实现。
04性能
2. 指数型ElGamal加密方案
3. 环LWE加密方案
从通信效率和计算效率两个角度，谷歌对基于这三个加法同态加密的三个协议进行了详细分析。
数据显示，第三个协议–DDH类型协议获得了最好的通信效率。在输入集合元素是10万个元素情况下，只需要9.28M的通信量。
此外，在计算效率方面，基于环LWE加密方案的DDH类型协议也依然获得了最佳性能。在输入集合含有10万个元素，以及相关整数是32位的情况下，计算PIS问题仅需395.78秒。
对于其它两个协议，尽管做了计算上的优化，但是其计算瓶颈主要花在了同态操作上。
