基于区块链的隐私保护交集算法*

熊 璐，杨 阳，沙金锐，范 磊

（1.中国银联股份有限公司，上海 201201；2.电子商务与电子支付国家工程实验室，上海 201201；3.上海交通大学 网络空间安全学院，上海 200240）

0 引言

近年来，区块链技术作为密码技术和分布式计算的一个重要研究方向得到了广泛研究。由于它可以实现去中心化的数据一致性，可以广泛应用于数据交换与共享领域。但是，区块链本身并不提供隐私保护功能，因此在需要对数据进行隐私保护的领域需要叠加额外的密码协议给予保护。

目前，区块链主要利用零知识证明、同态加密等密码学技术解决数据隐私保护问题。例如，匿名电子货币系统Zcash[1]使用非交互式的零知识证明进行隐私保护。零知识证明允许双方在不泄露任何信息的情况下，证明某个提议的真实性[2]。交易信息在Zcash 中是保密的，无关人员无法获得交易中发送方地址、接收方地址与转账数额，但是他们通过零知识证明可以验证支付是否有效。

零知识证明、全同态加密等密码技术虽然可以实现数据的隐私保护，但是运行效率较低，在需要大量数据共享的领域无法提供有效的性能支持。隐私保护交集计算（Private Set Intersection，PSI）是安全多方计算领域内的一个特殊应用，应用场景是参与者的数据表示成集合的形式，在不泄露各自参与方输入信息的前提下，协同计算输入集合的交集。

PSI 计算是Freedom 等[3]在2004 年提出，借助不经意多项式求值和同态加密得以实现。但是，这种实现由于同态加密的效率问题计算代价较高。因此，传统的应用采用了单向散列函数实现PSI 技术，即对参与双方的集合分别进行单向散列映射，在散列值的基础上进行集合交集计算。这种方法很容易受到敌手的碰撞攻击。

本文设计了一种基于区块链的隐私保护交集算法（Blockchain Private Set Intersection，BPSI），利用区块链的抗合谋性，解决服务端与参与的一方进行合谋的安全隐患，同时分析了该协议在恶意模型下的安全性机制、有效性机制以及仲裁机制。

1 预备知识

1.1 区块链及其安全特性

区块链是一种由区块构成的链式数据结构，通过数字签名等密码算法实现数据的防篡改、防抵赖等安全特性。区块链作为新型的分布式多方记账系统，依托于智能合约技术逐渐由单纯记录数字货币的交易信息发展为一种支持多方参与的分布式计算系统。

Juan[4]等人于2015 年证明了区块链理论的安全性。区块链所能提供的安全性特性包括如下内容。

（1）一致性。在分布式环境中，除了最新的若干区块，所有的参与节点都能够得到一致的数据结果。

（2）存活性。即便有恶意节点存在，区块链仍然能持续不断地记录新的数据，保证系统的活性。

（3）公平性。诚实节点能够为最终的区块链产生区块，所有用户的信息都能得到记录和存储。

但是，区块链协议并不能提供数据的隐私保护，区块链中所承载的数据所有参与节点均能接收与防范，因此在需要隐私保护的场景应叠加其他密码技术。

1.2 隐私保护交集

PSI 计算技术根据是否有第三方参与可以分为两大类。

1.2.1 传统的PSI 计算技术

参与方直接交互执行真实的协议，从而实现对隐私集合的交集计算。这类技术可以根据实现的原理分为基于公钥加密机制的PSI、基于混乱电路的PSI 以及基于不经意多项式的PSI。这里着重关注基于公钥加密体制的PSI 协议。

基于公钥加密体制的PSI 协议主要是对集合进行复杂的公钥加密操作，并通过协议的设计使之能在密文上进行计算。根据协议的设计思想，又可以分为基于不经意多项式的PSI、基于不经意伪随机函数的PSI 以及基于盲签名的PSI。

对于基于不经意多项式的PSI，自从Freedom等[3]在2004 年最先提出后，2016 年Freedom 等[5]又给出了随机Hash、负载均衡Hash、布谷鸟Hash的实验比对，证明了负载均衡Hash 和布谷鸟Hash的实验效果相对更好。同时，2005 年Kissner 等[6]给出了利用基于多项式环的裴蜀定理的协议设计方法；2010 年Hazay[7]、Freedom 等[3]提出同态加密的PSI 协议，给出了恶意模型下利用cut and choose 的解决办法；2017 年陈振华等[8]给出了给予离散对数且不依赖加密算法的PSI 协议。

对于基于不经意伪随机函数的PSI 协议，2008年Hazay 等[9]给出了根据OT 协议涉及的不经意伪随机函数的PSI 协议；2009 年Jarecki 等[10]基于复合剩余假设，利用Dodis-Yampolskiy 伪随机函数[11]、Camenisch-Shoup 加法同态[12]以及零知识证明，提出了另一种PSI；2010 年Jarecki 等[13]又利用不可预测函数，提出了速度提升20 倍的PSI 协议。

对于基于盲签名的PSI 协议，2010 年De Cristrofaro等[14]提出了基于RSA 的PSI 协议，但是该协议仅针对半诚实模型是安全的。为了解决恶意模型下的安全性问题，De Cristrofaro 等[15]在2010 年提出了基于零知识证明的PSI 协议，同时给出了传统PSI的效率比对[16]，证明了基于零知识证明的PSI 协议是在几个经典的传统PSI 模型中效率最高的。

1.2.2 云辅助的PSI 计算技术

主要利用云服务器的计算资源进行隐私交集的安全计算，云服务器承担着交集计算的作用，但是不会得到任何的明文信息。云辅助的PSI 技术大大提升了隐私计算的效率，但是在模型中要假设云端是可信的，从而解决云端与某一参与方的合谋性，否则将退化成两个计算能力相差悬殊的安全多方计算协议。

近几年，云辅助的PSI 协议才有了相关细致的研究，由Kerschbaum 等[17]在2012 年提出，分别是基于hash 函数和RSA 公钥加密算法的PSI 协议。但是，两个方案一个是牺牲安全性换来高效性，另一个是牺牲高效性换来安全性。2014 年Liu 等[18]提出了基于对称加密和非对称加密的PSI 协议，实现相对简单，但泄露了交集基数。2014 年Kamara等[19]提出了基于伪随机函数的PSI 协议，解决了恶意模型，且有着较高的计算效率，但存在不抗合谋缺陷。2015 年Abadi[20]提出了基于同态加密和多项式插值的PSI 协议，但是存在效率较低的问题。

2 协议设计

2.1 场景描述

传统的PSI 技术不适用于大规模场景，这是因为基于公钥加密机制协议的开销很大，不适合大规模信息的传输比对；基于混乱电路的协议需要将电路提前构建并全部加载到内存中，当集合很大时会造成内存的限制；基于布隆过滤器的协议需要加载布隆过滤器结构至内存。所以，上述办法都不适合大规模数据的应用。

云辅助的PSI 技术解决了大规模数据的应用问题，但由于现在的云服务器大多都是私有云，所以云服务器存在与参与方进行合谋的隐患。区块链相比云服务端，由于是基于去中心化的共识协议，可以有效避免某一参与者与中心合谋的攻击问题。

相比传统的PSI 协议和云辅助的PSI 协议，区块链因为链上信息公开透明，任何人都可以看到链上的信息，所以对于密钥协商、加密处理等步骤是完全不同的。因此，需要根据区块链的特性设计新的PSI 协议，这里称为基于区块链的隐私保护交集协议——BPSI 协议。

本文尤其关注一类具体的应用场景，如金融机构间信用数据共享、致病基因检测等。在这种场景中，服务的申请者可以预先知道服务提供者数据集合的部分信息，如所有金融机构已知的失信人员、部分已知的致病基因片段等。基于此假设，服务申请者可嵌入随机先验点位，从而检测服务提供者返回结果的有效性。

2.2 符号定义

本文基于Kamara 等[19]提出的云辅助的基于伪随机函数加密的PSI 技术的基础协议，设计了一种适用于区块链系统的BPSI 协议。在给出具体的算法前，本文协议设计中使用的参数定义如表1 所示。

表1 协议符号与参数

2.3 协议流程

协议的执行流程如图1 所示。

协议执行过程如下。

图1 BPSI 协议流程

定义与输出：F:{0,1}k×U→{0,1}≥k

协议流程：

3 协议分析

3.1 安全性分析

协议的两个参与方分别为服务的发起者P1服务提供者P2以及区块链系统S。由于用户P1是协议的发起者，在计算过程中由于需要获取有用信息，故需要提供自己真实信息并按照协议要求执行，为半诚实模型。协议执行过程的安全性依赖于区块链技术保证。在区块链参与节点较多时，它被恶意节点控制的概率较小，即是恶意模型的概率很小。因此，假设S是半诚实模型（由于区块链上信息公开，故存在被第三方利用的可能）。

服务提供者P2可能不遵守服务过程与协议，因此被视为恶意模型。容易得到，当P2发生不遵守协议的行为时，用户P1可以在本地进行安全性核查。这是由于在伪随机置换协议中引入了信息复制操作Sλ、补充参量操作τi=D0∪D1和随机扰动操作∏，从而客户端不履行协议（如：不参与协议、修改隐私的输入集合信息、提前终止协议的执行）时，会导致最后上传集合的不完整或错误，从而在进行安全性校验时发现该错误。此外，由于引入冗余保护机制，P2的破解空间明显增大（λ倍以上），使得暴力破解方式（如彩虹表攻击等）难度更大，破解成功概率更低。

另外，考虑到由于P2可能提供错误的信息来达到获取他人信息的恶意目的，在算法外引入有效性机制检验。在区块链可信任的前提下，用户端通过引入先验性知识对服务商数据进行概率性校验，避免服务商恶意更改输出的情况。在区块链可信任的前提下，本系统的安全级别超过了多种传统云隐私保护交集技术的安全性能[17-20]，并从根本上解决了多方合谋的安全隐患。

3.2 协议有效性

有效性机制是考虑如果P2并没有真正利用有限数据做交集计算，在这种情况下P1应能验证结果的有效性。

对于用户P1，其上传自己数据前应该先进行监测点嵌入。

（1）用户P1在需要检测的数据结合中，随机嵌入a个P2数据集合中明确包含的数据点，上传到区块并请求计算服务；

（2）服务方P2访问区块链，得到P1上传的待计算集合；

（3）服务提供者P2将进行交集计算，并将结果上传到区块；

（4）用户P1访问区块链，比对服务提供者P2是否检测出a个随机嵌入的数据点；

（5）如果a个数据点全部检测出来，认为服务提供者P2是诚实的；否则，服务提供者P2是恶意的。

下面对有效性机制进行证明。

不妨设双方数据集合公有n+a个元素。如果服务提供者P2是恶意的，第一种可能是P2故意上传了错误的交集元素，由有效性机制可直接判定；第二种可能是交集元素是服务提供者P2随机生成的，所以服务提供者P2为恶意的敌手，且无法检测出来的概率为。例如，恶意服务提供者随机返回交集，安全参数α≥10 时，计算得到无法检测出敌手的概率，是一个较小的数值。因此，当安全参数a足够大时，服务提供者P2成功欺骗用户的概率可以忽略不计。

3.3 协议仲裁机制

本节给出该系统的仲裁机制算法设计和说明。值得注意的是，仲裁机制依赖于安全性与有效性的分析。仲裁节点由可信第三方负责，若用户P1与服务提供者P2双方在整个过程中完全遵守协议运行，则无需仲裁节点参与。但是，在数据传输和结果返回过程中，若有任何一方提出异议，则需要将此次共享过程提交给仲裁方进行判定。仲裁法进行审判后，失败方将受到惩罚，具体惩罚机制可由联盟自行约定，不在本系统中做具体规定。本系统设计的仲裁机制需要在联盟中的各个节点配合的情况下才能成功解决争议。该仲裁机制与CCP 机制中的中央对手方作用类似，增加了系统的中心化色彩，区别在于CCP 需要对每一笔交易进行校验，但本系统的仲裁只在参与双方提出异议时工作。

对于本系统，因为用户P1与服务提供者P2双方资源差距过大，所以只考虑用户P1申请仲裁带来的影响。

用户P1控诉服务提供者P2，当用户P1对交集部分的数据解密后，安全校验出现错误，即出现且时，说明安全校验出现问题，此时仲裁介入。由于区块链的不可篡改性，D0、D1、D2均有记录。用户P1将安全校验的错误通过智能合约发布在链上，仲裁通过判定安全校验的错误性，判定用户P1与服务提供者P2谁将胜诉。

用户P1控诉服务提供者P2上传的数据不正确，当进行有效性检测时，用户P1上传的集合中k个数据点存在未检测出的，此时仲裁介入。用户P1将进行有效性检测的加密密钥和上传的带有的k个数据点通过智能合约发布在链上。仲裁通过将这k个数据点利用密钥加密，与之前得到的交集进行比较。仲裁通过是否存在某加密后的序列段不在之前的交集内，判定用户P1与服务提供者P2谁将胜诉。

4 结语

本项目研究了隐私保护交集（PSI）协议的设计方法，分析了现有方案中传统PSI 技术和云辅助PSI 技术的不足，提出了基于区块链的隐私保护交集协议BPSI，并给出了针对恶意模型下的安全性和有效性的算法改进。该方案在特定的数据共享场景下，解决了现有模型不抗合谋、效率较低、可追踪等缺陷，具有广阔的应用前景。