深度详谈 | 隐私计算技术如何实现密切接触者追踪系统（Catalic）

本文字数：2765，阅读时长大约6分钟

✪原文作者：Thai Duong，Duong Hieu Phan，Ni Trieu

✪原文标题：Catalic: Delegated PSI Cardinality with Applications to Contact Tracing

✪原文链接：https://eprint.iacr.org/2020/1105.pdf

✪原文来源：Asiacrypt 2020

01引言隐私集合交集基数(Private Set Intersection Cardinality, PSI-CA)允许持有集合元素的两方计算出集合大小而不泄露任何额外信息。该文提出了首个可将接收方的计算委托给不可信云服务器的PSI-CA协议并将其设计的PSI-CA协议作为基础技术构建轻量级的接触者追踪移动端应用程序。

至今，已有相当一部分人使用接触者追踪应用程序提醒COVID-19病毒感染风险，但现有带隐私保护的接触者追踪系统的客户端需要大量的计算和流量，这降低了终端客户的参与意愿。

使用该文设计的接触者追踪系统Catalic将终端计算委托给云服务器能大幅减少客户端设备的带宽和计算负荷，在保护隐私的同时，为每个用户每天节省数百兆的数据流量，并且没有原始Apple&Google的接触者追踪应用所拥有的链接攻击问题。该文主要有以下贡献




提出了一个隐私集合交集基数委托协议(DPSI-CA)，首个提出将PSI-CA的计算委托给云服务器并给出可行方法。该协议计算复杂度和通信复杂的均与小集合元素数量呈线性关系，独立于大集合元素数量。
设计了轻量级接触者追踪系统Catalic，该系统将终端计算委托给云服务器，提供了有效的隐私保护措施，可以防止当前系统所面临的安全隐患，如链接攻击等。

实施DPSI-CA协议并评估其属性，实验显示该文协议客户端计算量和通信量非常少，在服务器5000W数据，客户端4000数据时，忽略等待服务器响应时间，客户端仅需计算2毫秒，发送接收190KB数据。实验显示Catalic系统具有高可用性。

02原理在DPSI-CA协议中，主要参与方由客户端C，后台服务器S和m个云服务器H组成。客户端持有集合X，后台服务器持有集合Y，经委托PSI-CA协议计算后，客户端得到交集基数|X∩Y|对除交集以外的信息一无所知，而云服务器H和后台服务器对计算结果一无所知。
在DPSI-CA引入版本中，后台服务器S通过多项式插值将集合元素Y对应的点集构建成N-1阶多项式P(y)，其中为客户端C与后台服务器S所知的随机数集合。后台服务器S将多项式发送给云服务器H，由云服务器计算。
显而易见，如果,则，且由于云服务器不知道R相关的信息，故无法从计算结果推断其他信息。随后云服务器将R打乱成之后发送给客户端。最终客户端通过检查可以推断集合基数，而又不知道哪些元素是公共的。

注意，上述引入版本中假设云服务器清楚知道集合X，为使得云服务器H能够计算多项式而无需知道集合X，该文设计了基础原语Odk-PRF(Oblivious Distributed Key PRF)，实施时，客户端秘密共享集合元素给m个不合谋的云服务器，每个云服务器收到。

所有云服务器与后端服务器产生n个Odk-PRF协议实例。对于每个Odk-PRF实例，云服务器作为Odk-PRF的client输入得到PRF结果，后端服务器S作为Odk-PRF的server得到主密钥和相关密钥s。作为合并者从收集所有的并重组的PRF结果。Odk-PRF保证了不会泄露,,s给合并者。
假设有n个PRF密钥和N个元素，服务端PRF结果将有nN个，因此多项式的阶数为(nN-1)，高阶多项式的插值和构建非常昂贵，为解决该问题，该文采用与[PSSZ15]类似的思想，使用布谷鸟哈希算法和朴素哈希算法减少不必要的计算，使得多项式的构建与Odk-PRF协议的执行在同一哈希地址的基础上高效进行。03应用该文以DPSI-CA协议为基础，设计了依据用户最近是否接触了疾病感染者来警示用户是否有感染风险的接触者追踪系统Catalic，该系统处理流程如下图所示。以下4个步骤01. 当两个用户靠近时通过蓝牙交换各自生成的唯一令牌。
02. 当用户被权威医疗机构确诊后，用户收到一份签名证书，表明其疾病检测结果为阳性，并可验证证书真伪。
03. 确诊用户通过后台服务器的公钥加密本地PRG种子和确诊证书，并将其密文发送给云服务器，云服务器将收到的多方密文打乱之后发送给后台服务器。后台服务器使用私钥解密收到的密文对，得到某一用户的PRG种子和确诊证书。后台服务器使用医疗机构的公钥验证证书的有效性，如果证书真实，后台服务器将使用对应的PRG种子生成确诊令牌。
04. 每一个用户借助云服务器与后台服务器执行DPSI-CA协议，用户作为接收方输入本地接触的令牌集，后台服务器输入确诊令牌集。用户仅能得知本地令牌集合中有多少是在后台服务器中的确诊令牌库中的，以此可以判断自身是否为高风险感染人群。



在DPSI-CA协议中，用户将计算委托给了多台云服务器，在至少有一台服务器不合谋的前提下能够保证用户数据隐私。在实际实施中，能使用巨大的云服务器集群完成用户的计算委托。
文章简要的描述了分布式服务器部署设计DSUSH(Decentralized System of Untrusted Server-Helpers)，但未对其进行实施，将实施过程留给未来的进一步工作，通过DSUSH网络部署Catalic系统如下图所示。04实验与对比在隐私性、通信轮数、客户端的通信量与计算量方面，Catalic与其他接触者追踪系统在真实数据量情况下对比结果如下表所示。总结

作者首先指出在接触者追踪系统中，降低对终端设备的负载对增加用户使用意愿十分重要，设计了一个轻量级DPSI-CA协议作为核心组件设计接触者追踪系统Catalic，并分析了该系统部署在分布式集群云服务器上的可信性，文章最后与原始Google&Apple等主流方案进行对比，体现出该文方案在安全性和用户友好度上有一定优势。

读者在阅读原文之后存在一些疑问，DPSI-CA算法中，委托服务器数量的增多并不能减少单台服务器的计算量，基于DPSI-CA算法的Catalic系统将客户端的计算委托给多台云服务器同样存在上述问题，未来的工作可以考虑优化为一台服务器或使得服务器的数量与单台服务器的计算量呈负相关。

此外，该方案对后台服务器有较高要求，后台服务器的计算量与终端数量呈正相关，当用户群体较大时，如何降低后台服务器的负载量也是值得思考的问题。

 排版 | 李福玲      图片 | 杨雅清

—END—

点分享

点收藏

点点赞

点在看