基于区块链的隐私集合交集方案研究

陈万东 尹天宇 王璇 吕家兴

摘   要：保护隐私的集合交集运算是当前信息安全领域的研究热点，它使拥有秘密集合的参与者在不泄露各自隐私数据的前提下共同输出秘密集合上的交集结果，但是现阶段的隐私集合交集运算方案允许的参与方少并且效率低下，不能保证参与方之间的公平性。针对这些问题，文章提出了一种基于区块链的隐私集合交集求解方案，要求参与方共同部署并签订智能合约，将运算结果公布至区块链，保证参与者共同获得正确的交集结果。在进行隐私交集运算时，参照YAO氏通用混淆电路估值技术，使用保护隐私的集合交集运算电路和去重电路，设计了一种区块链上保护隐私的集合交集运算方案。

关键词：混淆电路;区块链;隐私集合比较;智能合约

1    隐私集合交集简要介绍

隐私集合交集（Private Set Intersection，PSI）使拥有隐私数据集合的多个参与者能够合作利用他们的私有数据计算交集，同时不泄露各自的私有信息，是安全多方计算研究方向的一个重要分支，在网络信息安全、人类基因研究等领域有广泛的应用。现阶段的隐私集合比较方案存在不能保证参与方的公平性、运算效率低下等问题，本文将介绍一种新的隐私集合交集计算方案，参与方可以在不泄露自己隐私信息的前提下公平、高效地得到交集结果。

2    预备知识

2.1  隐私集合交集

隐私集合交集指的是有N方的参与者Pi（i=1，2，…，N），各个参与者拥有自己的隐私信息Xi={x1，x2，…}（i=1，2，…，N），在不泄露参与者各自隐私信息的情况下计算出共有的集合元素信息X1∩X2∩…∩XN，在经过计算后，参与者最终得到交集结果，且不知道其他参与者的隐私信息。

2.2  区块链及智能合约

区块链（Block chain）是一种新型技术，可以看作是网络上存放所有交易信息的一本公共账簿，账簿的内容是不可修改的。每个节点代表一个用户，每一个节点都可以获取到在这个区块链中的所有交易信息，当部分节点的交易信息被篡改，区块链上的其他节点会在短时间内发现这些未共识的节点并进行维护和更新。区块链内的所有数据以链式存储，通过时间戳技术可以追溯每笔数据的所有信息以及来源。智能合约（Smart contract）是一种可以在区块链上部署的合约，一旦某个事件触发合约中的条款，合约自动执行相应的措施。智能合约有去中心化的特点，合约透明并且一旦签署便无法更改，保证签署方的公平性。

2.3  混淆电路

混淆电路是Andrew Yao在20世纪80年代发明的一种很智能的技术。它可以让两个人针对某个算式来计算答案，而不需要知道他们在计算式所输入的数字。混淆电路是安全多方计算的一种解决方案，可以在参与方不泄露自己隐私信息的情况下进行多种类型的计算。例如Andrew Yao提出的百万富翁问题：两个百万富翁想要知道谁的财产更多一些，但是不想让对方知道自己的财富信息。可以使用混淆电路方案设计相应的电路计算出来结果并且不会泄露参与方的信息。混淆电路方案可以通过电路的设计来解决更为复杂的问题。

3    方案描述

在这个方案中，参与方会在不泄露自己隐私信息的前提下获得所有参与者隐私信息所计算出来的交集结果。首先，各个参与方共同部署智能合約，协商智能合约内容，保证各个参与方能够在不泄露自己隐私的前提下公平地、正确地、及时地获取结果。签署智能合约之后，如果一方违约，将会给其严厉的惩罚。其次，使用设计好的混淆电路（参照下一段）将隐私信息交集结果计算出来。最后，智能合约接收到结果触发条件，将交集结果同时发送给所有参与方。

将介绍混淆电路的设计方案。让C是一个布尔电路接收两个输入x，y∈{0，1}n和输出C{x，y}∈{0，1}n（为简单起见， 假设输入长度、输出长度和安全参数都是相同长度n）。还假设C具有这样的性质：如果电路输出线来自门g，那么门g没有输入到其他门的线。（同样地，如果电路输入线本身也是电路输出，那么它就不是输入到任何栅极中。）

首先描述了C中单个杂乱门g的构造。电路C是布尔型的，因此，任何门都由函数g表示：{0，1}X{0，1}→{0，1}。现在，将g的两条输入线标记为w1和w2，并将g的输出线标记为w3。此外，让k10，k11，k20，k21，k30，k31为独立调用密钥生成算法G（1n）获得的6个键;为了简单起见，假设这些键的长度也为n。直观地说，希望能够从k1α和k2β计算k3g（α，β），而不揭示其他3个值中的任何一个：k3g（1-α，β）、k3g（α，1-β）、k3g（1-α，1-β）。门g由以下4个值定义c（0，0），c（0，1），c（1，0），c（1，1）：

其中，E来自一个私钥加密方案（例如G，E，D），该方案对多条消息进行了不可区分的加密，并且具有难以捉摸的有效验证范围。实际的门是由上述值的随机排列来定义的，表示为c0，c1，c2，c3;从这里称它们为门g的杂乱表。注意，给定k1α和k2β，以及c0，c1，c2，c3的值，可以如下计算门k3g（α，β）的输出。对于每个i，计算。如果多个解密返回一个非值，则输出中止。否则，将k3λ定义为获得的唯一非值。（请注意，如果只获得一个非值，那么这将是k3g（α，β），因为它是在给定的密钥k1α和k2β下加密的。）

现在，我们准备展示如何构造整个混淆电路。设m为电路C中的导线数，设w1，…wj是这些电线的标签。除以下情况外，这些标签都是只选择wi和wj为同一栅极g的两根输出线，则wi=wj。如果g>1，就会发生这种情况。同样地，如果一个输入位进入一个以上的栅极，那么与这个位相关联的所有电路输入线将具有相同的标签。接下来，对于每个标签wi，选择两个独立的ki0，ki1←G（1n）;强调所有这些键都是独立于其他键选择的。现在，给定这些键，按上面描述的方式计算每个门的4个混淆值，并随机排列结果。最后，计算了混淆电路的输出或解密表。这些表只是由（0，ki0）和（1，ki1）的值组成，其中，wi是一种电路输出线。或者，输出门可以直接计算0或1。也就是说，在输出门中，可以为每一个α，β∈{0，1}定义。C的整个乱码电路，即G（C），由每个门的乱码表和输出表组成。由此注意到，给出了C的结构，通过指定每个门的输出表和混乱表，可以简单地定义C的混乱版本。这就完成了对混淆电路的描述。

最后，智能合約会将混淆电路的运算结果，同时返回给参与方。利用伪随机函数生成公开参数，这些参数会影响到计算的结果。所以，根据密文计算的方法以及参数需要部署到智能合约，并由其执行验证。智能合约计算出来的密文结果会由智能合约同时公开给每个参与方，避免参与方提前获取结果并欺骗其他参与方。

[参考文献]

[1]HUANG Y，EVANS D，KATZ J，et al.Faster secure two-party computation using garbled circuits[C].San Diego：20th USENIX Conference on Security，2011.

[2]MOHASSEL P，RIVA B.Garbled circuits checking garbled circuits：more efficient and secure two-party computation[M].Newyork：Advances in Cryptology—CRYPTO，2013.

[3]WATANABE H，FUJIMURA S，NAKADAIRA A，et al.An efficient energy monitoring method based on bluetooth low energy[C].Las Vegas：IEEE International Conference on Consumer Electronics，2016.

[4]WATANABE H，FUJIMURA S，NAKADAIRA A，et al.Blockchain contract：Securing a blockchain applied to smart contracts[C].Las Vegas：IEEE International Conference on Consumer Electronics，2016.

[5]FREDERIKSEN T K，NIELSEN J B，ORLANDI C.Privacy-free garbled circuits with applications to efficient zero-knowledge[C].Springer：Annual International Conference on the Theory and Applications of Cryptographic Techniques，2015.

[6]BELLARE M，HOANG V T，ROGAWAY P.12-foundations of garbled circuits[C].North Carolina：ACM Conference on Computer and Communications Security，2012.