隐私求交的技术衍化

什么是隐私求交

  • 隐私求交（Private Set Intersection，PSI），顾名思义，是求解双方(或多方)集合的交集数据，而不透漏交集以外的任何数据信息。
  • 一般情况下，都是研究基于两方的隐私求交，可基于数据集的大小，区分大数据集和小数据集，或是非对称数据集。

隐私求交的几种典型方法

  • 从衍化路径上来看，目前有以下几种PSI的方案。

基于 hash 的纯粹PSI

  • 思路：即对双方的数据元素分别进行哈希运算，将数据集的交集转换成哈希值的交集。

  • 优点：思路简单，速度快；
  • 缺点：如果𝑥𝑖,𝑦𝑖是随机string，这个方案是可行的； 但如果𝑥𝑖,𝑦𝑖是类似ID之类的信息，就很容易猜出来；

基于 DH密钥交换（Diffie-Hellman key exchange ）的PSI

  • 思路：采用密钥交换的思想，对双方的数据元素进行加密处理，之后求交集；

  • 优点：数据的安全性得到了保障；
  • 缺点：
    • 涉及大量的指数运算，计算成本比较高；
    • 需要额外的密钥管理，当多个参与方加入时，密钥管理是一个挑战；
    • 无法处理动态变化的数据集，当集合发生变化时，需要重新计算；

基于不经意伪随机函数（Oblivious Pseudo Random Function, OPRF）的PSI

  • 缺点：正如图中所示，运算复杂度为O(N^2).

基于布谷鸟哈希（Cuckoo hash）改进的OPRF 的PSI

  • 布谷鸟哈希的思想：借用了“鸠占鹊巢”的思想，如果某个数据hash之后发现位置被别人占据了，就把对方踢出去；而提出去的那一方，再用一个新的hash方式重新寻找落脚点。
  • 布谷鸟哈希的demo

  • 核心思想：(Mike Rosulek 教授给出了形象的表示，如下图)
    • 发送方Alice：采用Cuckoo hash，将数据归属到某一个bin桶中；
    • 接收方Bob：采用Cuckoohash 中用到的多个simple hash，以此对数据进行哈希，同一数据可归属到多个bin中；
    • 对于Alice中的每个bin桶，Bob都返回分组好的bin，由Alice进行比对求交；

隐私求交的应用

  • PSI是安全多方计算中的一个重要分支，具有广泛的应用前景，如隐私保护的位置信息共享，在线广告的有效转换率衡量，以及基因序列的比对等。
  • 但针对不同的场景，需要采用不同的隐私求交技术，以达到最大的效果。

小数据集的双方

  • 这种场景下采取 DH 密钥交换的技术，效率较高；

大数据集的双方

  • 这种场景下采用基于OPRF的方式比较好。

不对称的双方

  • 可以采用DH密钥交换的技术，但结合线上和线下，在数据量大的一方提前计算一批，缓存发到数据量小的那方；（但缺点是不适合数据更新）
  • 采用分桶的方式，将双方的数据源分桶后再求交；（缺点是隐私会有泄露）

References:

  1. 安全多方计算5-隐私集合求交方案汇总分析
  2. 隐私计算基础理论-安全求交集和匿踪查询 段普老师很靠谱:)
  3. 隐私计算关键技术：隐私集合求交PSI原理介绍
  4. Mike Rosulek教授开讲PSI协议 Mike老师很给力

results matching ""

    No results matching ""