安全多方计算(5):隐私集合求交方案汇总分析

一、引言

随着数字经济时代的到来,数据已成为一种基础性资源。然而,数据的泄露、滥用或非法传播均会导致严重的安全问题。因此,对数据进行隐私保护是现实需要,也是法律要求。隐私集合求交(Private Set Intersection, PSI)作为解决数据隐私保护的方案之一,受到广泛关注和研究。

隐私集合求交使得持有数据参与方通过计算得到集合的交集数据,而不泄露任何交集以外的数据信息,其功能如图1所示。作为安全多方计算中的一个重要分支,其不仅具有重要的理论意义,也具有广泛的应用场景。例如:隐私保护位置共享[1]、在线广告的有效转换率衡量以及基于人类基因组序列[2]的亲子鉴定、疾病预测和血统测试等。

图1 隐私集合求交功能示意图

二、PSI分类

隐私集合求交的研究主要聚焦在两个参与方,因此,本文主要针对两方隐私集合求交进行阐述。两方PSI可根据参与方的数据集大小分为三类,如图2所示。根据双方数据集大小差异可将其分为对称数据集和非对称数据集,对于对称数据集,又可分为大数据集和小数据集。本文针对对称数据集及不同场景的需求,介绍与之对应的隐私集合求交方案。

图2 隐私集合求交分类示意图

三、PSI方案介绍

3.1 基于DH的PSI方案

基于DH的PSI方案[3]流程如图3.1所示,该方案基于DH密钥交换的思路,实现两次可以交换加密顺序的加密操作,使得参与双方对于交集数据,得到完全相同的不可逆密文。

图3.1 基于DH的PSI方案流程示意图

基于DH的PSI方案主要分为以下3个步骤:

  1. Alice选择随机数作为私钥。对于每一个数据x,Alice首先对其进行哈希操作,再基于其哈希值使用私钥对其加密,生成密文,并将此密文发送给Bob。
  2. Bob选择随机数作为私钥。对于每一个数据y,Bob首先对其进行哈希操作,再基于其哈希值使用私钥对其加密,并将此密文发送给Alice。对于接收到Alice的密文,Bob使用私钥对其进行二次加密。
  3. Alice对于接收到的密文,基于私钥对其进行二次加密

结论:若Alice和Bob拥有相同的数据,则两次加密得到的密文一致。

基于DH的PSI方案思想简单,易于实现,但也具有一定的局限性,例如:基于公钥加密实现PSI功能会产生较大的计算开销。因此,适用于数据量较小的场景。

3.2 基于OT的PSI方案

  • 预备知识

不经意传输(Oblivious Transfer, OT)[4]是安全多方计算最基础的协议之一,在之前的文章中已做了详细介绍安全多方计算(1):不经意传输协议

本部分我们仅使用了2选1的不经意传输协议,其功能如图3.2所示。Alice有两条消息,Bob可以通过比特b获取消息,而无法获得的任何消息。Alice无法获得关于b的任何信息,即:Alice不知道Bob获取了哪条消息。

图3.2 不经意传输功能示意图

  • 方案详解

在本部分,我们简述经典的基于OT的PSI方案,其流程如图3.3所示。该方案的核心思想为执行多次二选一的不经意传输协议,并结合伪随机函数,使得参与双方对于交集数据得到相同的随机数。

图3.3 基于OT的PSI方案流程示意图

基于OT的PSI方案主要分为以下3个步骤:

  1. Alice生成随机数w;Bob生成随机数,并基于与本方数据的伪随机函数值生成.
  2. Alice与Bob基于w和执行次二选一的不经意传输,其中为的长度。
  3. Alice基于多次不经意传输结果生成q,Bob计算的哈希值。
  4. Alice计算本方数据的随机值

结论:若Alice和Bob拥有相同的数据,则两份数据得到相同的随机值

我们以两种极端情况论述方案的正确性:

图3.4 基于OT的PSI方案正确性验证

基于OT的PSI方案规避了大量的公钥加密,使用效率更高的对称加密完成大部分操作,但通信开销较大,适用于数据量较大的场景。

经典的基于OT的PSI方案仍具有很大的计算开销及通信开销,但是OT的扩展协议为构建高效的PSI方案提供了理论支撑。在3.3中,我们以OPRF为例,介绍基于OT扩展协议的高效PSI方案。

3.3 基于OPRF的PSI方案

  • 预备知识

不经意伪随机函数(Oblivious Pseudorandom Function, OPRF)[5]属于不经意传输的扩展协议,它允许执行少量的基础OT,通过轻量级的对称加密来实现大量的OT实例。OPRF的功能如图3.4所示。

Alice生成伪随机函数的密钥k,可基于k获得本方数据x的伪随机函数值。Bob以本方数据y作为OPRF协议的输入,协议执行完成后,Bob可得到y的伪随机函数值,但无法获得关于k的任何信息。

图3.5 不经意伪随机函数功能示意图

  • 方案详解

在本部分,我们简述基于OPRF的PSI方案[6],其总体流程如图3.5所示。为便于阐述,我们将Alice作为数据拥有者,记为DO(Data Owner);Bob作为请求者,记为Re(Requester)。

图3.6 基于OPRF的PSI方案总体流程示意图

我们将基于OPRF的PSI方案分为以下步骤进行阐述:

  1. 请求者将数据映射为,映射过程如图6所示。首先,请求者随机生成m行w列的二进制矩阵A,其中m为数据集大小。对于每个数据,请求者计算其伪随机函数值,并将伪随机函数值与二进制矩阵A相结合,获取二进制比特串。同时,将对应位置标记为数据位(如图3.6中蓝色部分)。然后,基于二进制比特串执行哈希操作,得到数据映射值。

图3.7 请求者数据映射流程图

  1. 请求者生成矩阵B。请求者生成一个m行w列的全1矩阵D,将第1步标记的数据位部分置为0。然后,将矩阵A与矩阵D执行异或操作得到矩阵B。因此,矩阵A、B具有如下特性:矩阵A、B对于数据位的比特值相同;对于非数据位的比特值相反。这一步主要是为了二选一的不经意传输做准备。

图3.8 矩阵B生成示意图

  1. 数据拥有者获得矩阵C,这一步的核心思想是请求者与数据拥有者执行w次不经意传输,其执行过程如图3.8所示。通过1、2步,请求者已获得A、B矩阵;在第3步,数据拥有者生成长度为w的二进制比特串。在每一次OT执行中,请求者以A、B矩阵的第i列作为输入;数据拥有者以比特串s的第i位{s[i]}作为输入。若s[i]=0,则数据拥有者得到列;若s[i]=1,则数据拥有者得到列. 最终,数据拥有者得到矩阵C。矩阵A、B、C具有如下特性:此三个矩阵对于数据为的比特值相同;而通过不经意传输,矩阵C的非数据位已被置乱。

图3.9 不经意传输执行示意图

  1. 数据拥有者将数据映射为,映射过程如图3.9所示。对于每个数据,这一步与第1步的流程类似,其目的是为了对于参与双方的交集数据生成完全相同的随机映射值。首先,数据拥有者计算其本方数据的伪随机函数值,并将伪随机函数值与第3步得到的二进制矩阵C相结合,获取二进制比特串然后,基于二进制比特串执行哈希操作,得到数据映射值。

图3.10 数据拥有者数据映射流程图

  1.  数据拥有者将其本方所有数据映射值发给请求者,请求者对比两方数据映射值确定交集数据,而其不会获得数据拥有者的任何非交集数据信息。至此,协议完成,

四、总结

本文介绍了基于两方对称数据集的三种隐私集合求交方案,其中基于DH的PSI方案适用于小数据的场景;基于OT的PSI方案适用于大数据集的场景,但其依然有较大的通信开销,因此,介绍了基于OPRF的PSI方案,其在计算开销和通信开销方面均具有良好的表现。

随着隐私计算技术的发展,多方及外包隐私集合求交方案也在被逐渐关注与研究,我们在后续文章中进行介绍。

参考文献

[1] NARAYANAN A, THIAGARAJAN N, LAKHANI M, et al. Location Privacy via Private Proximity Testing[C]//Proceedings of the Network and Distributed System Security Symposium, NDSS 2011, San Diego, California, USA, 6th February – 9th February 2011. 2011.

[2] SHAFIN K, PESOUT T, LORIG-ROACH R, et al. Nanopore sequencing and the Shasta toolkit

enable efficient de novo assembly of eleven human genomes[J]. Nature Biotechnology, 2020(Suppl.2).

[3] Meadows C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party[C]//1986 IEEE Symposium on Security and Privacy. IEEE, 1986: 134-134.

[4] RABIN M O. How to Exchange Secrets by Oblivious Transfer[J]. Technical Memo TR-81, 1981.

[5] FREEDMAN M J, ISHAI Y, PINKAS B, et al. Keyword Search and Oblivious Pseudorandom

Functions[C]//KILIAN J. Theory of Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg,2005: 303-324.

[6]CHASE M, MIAO P. Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF[C]//MICCIANCIO D, RISTENPART T. Advances in Cryptology – CRYPTO 2020. Cham: Springer International Publishing, 2020: 34-63.

版权声明
本站“技术博客”所有内容的版权持有者为绿盟科技集团股份有限公司(“绿盟科技”)。作为分享技术资讯的平台,绿盟科技期待与广大用户互动交流,并欢迎在标明出处(绿盟科技-技术博客)及网址的情形下,全文转发。
上述情形之外的任何使用形式,均需提前向绿盟科技(010-68438880-5462)申请版权授权。如擅自使用,绿盟科技保留追责权利。同时,如因擅自使用博客内容引发法律纠纷,由使用者自行承担全部法律责任,与绿盟科技无关。

Spread the word. Share this post!

Meet The Author