此次分享的是发表在AsiaCrypt’21 的题为 “Private Join and Compute from PIR with Default” 的文章。文章第一作者现在就职于 AWS 安全团队。

Introduction

这篇文章考虑在隐私集合求交集 (PSI) 下的一个特殊分类： private join and compute （PJC）。这个功能不仅要求最终的计算结果只能揭示两个集合的交集，同时还要对交集中的数字进行运算。

具体来说，接收方有两个集合（X,W）={(x1,w1),…,(xt,wt)},发送方也有两个集合，(Y,V)={(y1,v1),…,(yn,vn)}。其中集合X和Y代表id集合，W,V代表与id对应的权重。PJC的目的是在保证双方隐私的情况下，计算出X,Y交集对应的权重的乘积总和：

上面的公式可以用于在隐私保护下计算广告的有效性，以及进行 covid19 进行感染者追踪等。

Overview of Their Approach

Private Information Retrival (PIR)

这篇文章的开始点起于 PIR. 因为考虑用户和服务器模型下，服务器所拥有的数据量远大于客户的数据量，因此在他们双方进行 PSI 以及相应运算时，为了减少用户的计算量，自然会想到通过使用 PIR 去构造协议。

如下图所示，PIR 协议中，服务器端（右边）有一个数据库 Y = (y1, y2,…, yn)，客户（左边）通过发送一个索引请求 i，在协议结束后，客户只可以得到该位置的数据 yi, 而服务器不知道客户具体的请求位置 i。

Keyword PIR

在 keyword PIR 协议中 （PIR 协议的一个变种），服务器拥有的是一组键盘-值对，Y = (y1, …, yn) 和 W = (w1, …, wn)，而客户的请求为一个关键词 (keyword)。 在协议结束后，客户可以得到 W[x] （如果 x 在集合 Y 中），否则客户将会得到一个随意的值。

PIR with Default + value + mask (Extended PIR-with-Default)

default: 服务器还有一个默认值 t。 如果客户请求的关键词不在 Y 中，那么协议的最后客户将会得到这个默认值 t。

value: 同时，客户也额外拥有一个值 v, 如果 x 在集合 Y 中，那么协议结束后，客户将会得到 v * W[x]。

mask: 为了防止信息泄漏，服务器还会有一个随机的值 r 用来隐藏其他值。因此，客户在协议结束后得到的最终值为 t + r 或者 v * W[x] + r。协议完成后，客户不知道自己收到的是哪一个。

PJC from PIR

通过 extended PIR-with-Default 可以比较容易地构造一个 PJC 协议，其构造如下图，这里不再描述其具体细节。

下面，我们介绍下如何构造最终协议所需的 extended PIR-with-Default 协议 以及所需要的 building blocks。

Construction

对于最终协议的构造，分成两个部分。第一个部分关于如何回应客户对于索引的请求，第二部分关于如何回应对应索引对应值的请求。

PIR with BF

Bloom Filter (BF) 布隆过滤器 (BF)，是一个数据结构，假设一共有 n 个位置。 它一共定义了 k 个哈希函数 h1, h2, …, hk（下图 k = 4)， 插入 x 的时候，将 x 使用每一个哈希函数映射得到一个位置，一共会得到 k 个位置，将 BF 中这 k 个位置对应的数变为 1。当询问 y 是否在 BF 中时，将这 k 个哈希函数对 y 做映射，检查是否每个映射的位置都为1。如果是，则证明 y 在此 BF 中；否则不在。

Construction 回到最初的问题，客户拥有（X, W），服务器拥有(Y, V)。服务器首先将集合 Y 中的元素插入到一个 BF 中。 对于客户的每一个请求 x, 其首先用 k 个哈希函数做映射，并将映射的位置同态加密后发送给服务器。服务器处理来自客户的 PIR 请求：在用户选定位置上同态提取出 BF 中所存的数字，并把他们的和与一个随机数 r2 同态加起来发送给客户。客户收到结果后解密并减去 k 记为 r1。 那么如果 x 在集合 Y 中，则有 r1 = r2。

PIR with GBF

Garbled Bloom Filter (GBF) 相比较于上面的 BF, GBF 存储的是对于一个键所对应的值。具体来说， 假设有 （Y, W） = ({y1 ,…, yn}, {w1 ,…,wn})，以及有 k 个哈希函数。 如果要存储 w1, 那么需要满足，对 y1 进行 k 个哈希函数的映射后的位置内所存储的值加起来等于 w1。

Construction 在协议中，服务器将 (Y, V) 使用 k 个哈希函数插入到 GBF 中。对于客户的一个请求 （x, v），首先对 x 使用 k 个哈希函数映射得到 k 个位置，将这些位置同态加密后发送给服务器，同时也要讲 v 同态加密后发送过去。服务器将在 GBF 这些位置上存储的值相加并乘以 v 减去一个随机值 s2（同态，并将结果发送给客户。客户解密后得到 s1. 如果 x 在集合 Y 中，那么 s1 + s2 等于 V[x]* W[x], 即想要的值；否则会得到随机值。

最终的协议其实是上面两部分协议相加，这里不再描述。

Efficiency

下图中红色线表示该协议。当客户端的询问次数不变时，无论服务器端数据量有多大，他们之间的通信量都几乎不变。

• • 本推送部分图片来自该文章的 presentation slides 以及网络。

原文始发于微信公众号（COMPASS Lab）：论文分享|Private Join and Compute from PIR with Default