查看原文
其他

隐私信息检索拓展应用 | Private Join and Compute from PIR with Default


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

1

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 进行感染者追踪等。

2

Overview


2.1 Private Information Retrival(PIR)

这篇文章的开始点起于 PIR. 因为考虑用户和服务器模型下,服务器所拥有的数据量远大于客户的数据量,因此在他们双方进行 PSI 以及相应运算时,为了减少用户的计算量,自然会想到通过使用 PIR 去构造协议。如下图所示,PIR 协议中,服务器端(右边)有一个数据库 Y = (y1, y2,..., yn),客户(左边)通过发送一个索引请求 i,在协议结束后,客户只可以得到该位置的数据 yi, 而服务器不知道客户具体的请求位置 i。

2.2 Keyword PIR

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

2.3 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。协议完成后,客户不知道自己收到的是哪一个。


2.4 PJC from PIR


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

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

3

Construction

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

3.1 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。


3.2 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], 即想要的值;否则会得到随机值。


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


4

Efficiency

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

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


本文来源:COMPASS Lab

END

往期推荐


TDSC 2022 | 为安全联邦学习建立互信的多混洗框架
FedALA | 用于个性化联邦学习的自适应本地聚合方法
多方计算实验中不同网络环境的模拟方法
VFL:针对纵向联邦学习的全面综述性文章
欢迎投稿邮箱:pet@openmpc.com参与更多讨论,请添加小编微信加入交流群

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存