0 概述

安全多方计算（Secure Multi-Party Computation，SMC）是指两个及两个以上的参与者在不泄露各自隐私数据的情况下，利用隐私数据进行保密计算并共同完成某项计算任务。SMC可满足人们利用隐私数据进行保密计算的需求，同时兼顾数据的保密性与共享性，因此被广泛应用于机器学习^[1]、数据分析^[2]、社交网络^[3]以及医疗信息等领域。

百万富翁问题（Millionaires’ Problem，MP）是安全多方计算中的基本问题，其在1982年由YAO提出^[4]后引起多方关注。近年来，研究人员相继提出多种解决该问题的方法。文献[5]将安全多方计算规约到智力游戏中，利用混淆电路解决百万富翁问题。文献[6]采用不经意传输工具对两方输入进行双重加密，设计一种解决百万富翁问题的安全双方计算协议。文献[7]使用不经意传输工具并通过简单异或运算解决百万富翁问题。文献[8-9]借助茫然第三方提出一种安全的百万富翁比较协议，解决第三方合谋问题。文献[10]利用零知识证明构造一种百万富翁问题协议。文献[11-13]通过私有置换操作提出基于卡片的密码协议，解决了百万富翁问题。文献[14-15]利用对称密码解决恶意模型下的百万富翁问题。

利用编码是解决百万富翁问题的有效措施之一。文献[16]采用0-1编码将双方待比较的数据转化为0/1集合，结合具有乘法同态性的加密算法解决百万富翁问题，但其计算复杂度较高且无法精确区分两数相等的情况。文献[17]利用基于二次剩余困难问题的GM加密算法，通过构造0-1编码将数据编码转换为向量，提出一种基于几何方法的有理数比较协议，但GM算法在解密过程中的时间开销随二次非剩余集合增大呈线性增长。文献[18]使用文献[16]中编码方式提出一种基于DDH假设的方案，但该方案仅适用于输入较小数据，当两个待比较数据较大时计算开销较高。文献[19]结合1-r编码方式和ELGamal同态加密算法解决数据比较问题，提出一种数据比较协议并将其应用于保密数据排序。文献[20-21]提出0-1-2编码方法，同时利用Paillier同态加密算法将百万富翁问题转化为向量问题求解。虽然文献[19-21]提出的方法能有效解决百万富翁问题中的两数相等问题，但计算效率均较低。

本文提出一种采用0-1编码的百万富翁问题协议。通过改进保密数据编码规则，利用ElGamal同态加密变体算法解决安全两数比较问题，在半诚实模型下证明协议的正确性和安全性，并从理论和实验两个角度对协议的计算复杂度与效率进行分析。

1 基础知识 1.1 安全多方计算的安全模型

在安全多方计算协议的执行过程中，半诚实参与者在忠实履行协议的同时会保留协议执行过程中的有效信息，并尝试推导出其他参与方的隐私信息。若安全多方计算协议中参与者均为半诚实参与者，则称该协议使用的计算模型为半诚实模型。由于本文协议的计算模型均为半诚实模型，因此以下文给出半诚实模型下两方计算模型的安全性定义。

设Alice和Bob分别拥有隐私数据$ x $、$ y $，$ \pi $为计算函数$ f $的协议。Alice和Bob希望通过合作计算函数$ F:\left(x, y\right)\to \left({f}_{1}\left(x, y\right), {f}_{2}\left(x, y\right)\right) $且不泄露各自隐私数据，其中存在概率多项式函数$ f:{\left\{0，1\right\}}^{\mathrm{*}}\times {\left\{0，1\right\}}^{\mathrm{*}}\to {\left\{0，1\right\}}^{\mathrm{*}}\times {\left\{0，1\right\}}^{\mathrm{*}} $，$ {f}_{1}\left(x, y\right) $和$ {f}_{2}\left(x, y\right) $分别为Alice和Bob计算所得函数$ F $的两个分量。将Alice和Bob在执行$ P $协议过程中得到的消息序列分别记为$ \mathrm{v}\mathrm{i}\mathrm{e}{\mathrm{w}}_{1}^{\pi }\left(\mathrm{x}, \mathrm{y}\right)\mathrm{和}\mathrm{v}\mathrm{i}\mathrm{e}{\mathrm{w}}_{2}^{\pi }\left(x, y\right) $，其所得输出结果分别记为$ \mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}{\mathrm{t}}_{1}^{\pi }\left(\mathrm{x}, \mathrm{y}\right)\mathrm{和}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}{\mathrm{t}}_{2}^{\pi }\left(x, y\right) $。

定义1（半诚实参与者的保密性）  对于函数$ f $，如果存在概率多项式算法$ {S}_{1} $和$ {S}_{2} $（也称为模拟器）满足式（1）与式（2），则称其为$ \pi $保密计算函数。

$ \begin{array}{l}{\left\{{S}_{1}\left(x, {f}_{1}\left(x, y\mathrm{ }\right)\right), {f}_{2}\left(x, y\mathrm{ }\right)\right\}}_{x, y}\stackrel{\mathrm{c}}{\equiv }\\ {\left\{\mathrm{v}\mathrm{i}\mathrm{e}{\mathrm{w}}_{1}^{\pi }\left(x, y\mathrm{ }\right), \mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}{\mathrm{t}}_{2}^{\pi }\left(x, y\mathrm{ }\right)\right\}}_{x, y}\end{array} $

(1)

$ \begin{array}{l}{\left\{{f}_{1}\left(x, y\mathrm{ }\right), {S}_{2}\left(x, {f}_{2}\left(x, y\mathrm{ }\right)\right)\right\}}_{x, y}\stackrel{\mathrm{c}}{\equiv }\\ {\left\{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}{\mathrm{t}}_{1}^{\pi }\left(x, y\mathrm{ }\right), \mathrm{v}\mathrm{i}\mathrm{e}{\mathrm{w}}_{2}^{\pi }\left(x, y\mathrm{ }\right)\right\}}_{x, y}\end{array} $

(2)

其中，$ \stackrel{\mathrm{c}}{\equiv } $表示计算上不可区分。若要证明一个安全多方计算协议具备安全性，则需构造模拟器$ {S}_{1}\mathrm{和}\mathrm{模}\mathrm{拟}\mathrm{器}{S}_{2} $使式（1）与式（2）成立。

1.2 ELGamal同态加密变体算法

ELGamal同态加密^[22]变体算法如下：

1）密钥生成（KeyGen）。给定安全参数$ k $，定义$ k $特别大，采用密钥生成算法生成1个大小为$ k $比特的素数$ p $以及有限域$ {\mathbb{Z}}_{p}^{\mathrm{*}} $的1个生成元$ g $，随机选取$ x $作为私钥，其对应公钥$ h={g}^{x}\mathrm{m}\mathrm{o}\mathrm{d}\;p $。

2）加密阶段（Enc）。给定消息$ M\in {\mathbb{Z}}_{P}^{\mathrm{*}} $，选择随机数$ r $，密文$ E\left(M\right)=\left({c}_{1}, {c}_{2}\right)=\left({g}^{r}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{M}{h}^{r}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right) $。

3）解密阶段（Dec）。将密文$ E\left(M\right) $解密为$ {g}^{M}={c}_{2}\cdot {c}_{1}^{-x}\mathrm{m}\mathrm{o}\mathrm{d}\;p $，对明文$ {m}_{1}\mathrm{和}{m}_{2} $加密后得到：

$ E\left({m}_{1}\right)=\left({c}_{1}, {c}_{2}\right)=\left({g}^{r}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{m}_{1}}{h}^{r}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right) $

(3)

$ E\left({m}_{2}\right)=\left({c}_{1}, {c}_{2}\right)=\left({g}^{r}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{m}_{2}}{h}^{r}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right) $

(4)

由于存在以下关系式：

$ \begin{array}{l}E\left({M}_{1}\right)\times E\left({M}_{2}\right)=\left({g}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{M}_{1}}{h}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)\times \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({g}^{{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{M}_{2}}{h}^{{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({g}^{{r}_{1}+{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{M}_{1}+{M}_{2}}{h}^{{r}_{1}+{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;E\left({M}_{1}+{M}_{2}\right)\end{array} $

(5)

$ \begin{array}{l}E{\left({M}_{1}\right)}^{b}=\left({\left({g}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)}^{b}, {\left({g}^{{M}_{1}}{h}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)}^{b}\right)=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({g}^{{r}_{1}b}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{M}_{1}b}{h}^{{r}_{1}b}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)=E\left(b{M}_{1}\right)\end{array} $

(6)

因此，ELGamal同态加密变体算法满足如下性质：

$ E\left({m}_{1}\right)E\left({m}_{2}\right)=E\left({m}_{1}+{m}_{2}\right) $

(7)

$ E{\left({m}_{1}\right)}^{b}=E\left(b{m}_{1}\right) $

(8)

2 MP解决方案 2.1 改进的0~1编码规则

百万富翁问题的实质是在保密情况下比较两数大小，即Alice有1个隐私数据$ x $，Bob有1个隐私数据$ y $，两人在不泄露$ x $和$ y $大小的前提下合作计算并比较两数大小。为解决该问题，本文将文献[20]中保密数据编码规则改进为0-1编码规则，并利用该规则构造基于0-1编码的百万富翁问题协议。

0-1编码规则如下：

设$ x, y\in \left\{{v}_{1}, {v}_{2}, \cdots , {v}_{n}\right\}=U $，其中$ {v}_{1}<{v}_{2}<\cdot \cdot \cdot <{v}_{n} $。令$ x={v}_{k}\mathrm{且}\mathrm{y}={v}_{l}\left(1\le k, l\le n\right) $，根据$ x $与$ U $构建只含0和1的向量$ \boldsymbol{\alpha }=\left({\alpha }_{1}, {\alpha }_{2}, \cdots , {\alpha }_{n}\right) $，具体规则如下：

$ {\alpha }_{i}=\left\{\begin{array}{c}0, {v}_{i}\le {v}_{k}，i=\mathrm{1, 2}, \cdots , n\\ 1, {v}_{i}>{v}_{k}，i=\mathrm{1, 2}, \cdots , n\end{array}\right. $

(9)

根据$ y={v}_{l} $在$ U $中的位置计算$ M={\alpha }_{l}+{\alpha }_{l+1} $。若$ M=0 $，则$ k>l $，即$ x>y $；若$ M=1 $，则$ k=l $，即$ x=y $；若$ M=2 $，则$ k<l $，即$ x<y $。

2.2 基于0-1编码的MP协议

本文利用0-1编码规则提出一种解决百万富翁问题的协议，以下介绍MP协议的具体设计方案，并对其正确性与安全性进行分析。

2.2.1 设计方案

MP协议利用0-1编码规则将判断隐私数据$ x $与$ y $大小的问题归约到求解$ {\alpha }_{l}+{\alpha }_{l+1} $值的问题，主要通过两元素之和来判断两数大小，该协议框架如图 1所示。

基于0-1编码规则的MP协议实现流程如下：

协议1  基于0-1编码的MP协议

输入  $ \mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e} $：$ x $，$ \mathrm{B}\mathrm{o}\mathrm{b} $：$ y $.$ x, y\in \left\{{v}_{1}, {v}_{2}, \cdots , {v}_{n}\right\}=U $

输出  $ M $

1.Alice：$ \mathrm{x}, \mathrm{U}\to \mathrm{A}=\left({\mathrm{\alpha }}_{1}, {\mathrm{\alpha }}_{2}, \cdots , {\mathrm{\alpha }}_{\mathrm{n}}\right) $ // α _i ∈ $ \left\{\mathrm{0, 1}\right\} $（i=1，2，…，n）

2.$ \mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}\to \mathrm{B}\mathrm{o}\mathrm{b} $：$ \mathrm{E}\left(\mathrm{A}\right)=\left(\mathrm{E}\left({\mathrm{\alpha }}_{1}\right), \mathrm{E}\left({\mathrm{\alpha }}_{2}\right), \cdots , \mathrm{E}\left({\mathrm{\alpha }}_{\mathrm{n}}\right)\right) $

3.$ \mathrm{B}\mathrm{o}\mathrm{b} $：$ \forall {\mathrm{r}}_{\mathrm{z}}\in {\mathrm{Z}}_{\mathrm{N}}^{\mathrm{*}} $，$ \mathrm{E}\left({\mathrm{\alpha }}_{\mathrm{l}}\right)=\left({\mathrm{g}}^{{\mathrm{r}}_{\mathrm{z}}}{\mathrm{g}}^{{\mathrm{r}}_{\mathrm{i}}}\mathrm{m}\mathrm{o}{\mathrm{d}}\;\mathrm{p}, {\mathrm{h}}^{{\mathrm{r}}_{\mathrm{z}}}{\mathrm{g}}^{{\mathrm{\alpha }}_{\mathrm{i}}}{\mathrm{h}}^{{\mathrm{r}}_{\mathrm{i}}}\mathrm{m}\mathrm{o}{\mathrm{d}}\;\mathrm{p}\right) $

//$ {\mathrm{a}}_{\mathrm{l}} $为Bob在$ \mathrm{U} $中位置所对应$ \mathrm{A} $的值；$ \mathrm{E}\left(\mathrm{M}\right)=\mathrm{E}\left({\mathrm{\alpha }}_{\mathrm{l}}\right)\times \mathrm{E}\left({\mathrm{\alpha }}_{\mathrm{l}+1}\right) $

//$ \mathrm{E}\left({\mathrm{\alpha }}_{\mathrm{l}+1}\right)=\left({\mathrm{g}}^{{\mathrm{r}}_{\mathrm{l}+1}}\mathrm{m}\mathrm{o}{\mathrm{d}}\;\mathrm{p}, {\mathrm{g}}^{{\mathrm{\alpha }}_{\mathrm{l}+1}}{\mathrm{h}}^{{\mathrm{r}}_{\mathrm{l}+1}}\mathrm{m}\mathrm{o}{\mathrm{d}}\;\mathrm{p}\right) $

4.$ \mathrm{B}\mathrm{o}\mathrm{b}\to \mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e} $：$ \mathrm{E}\left(\mathrm{M}\right) $

5.$ \mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e} $：$ \mathrm{D}\left(\mathrm{E}\left(\mathrm{M}\right)\right)=\mathrm{M} $

该协议具体内容如下：

1）Alice按照式（9）中的规则利用自身隐私数据$ x $和隐私数据集合$ U=\left\{{v}_{1}, {v}_{2}, \cdots , {v}_{n}\right\} $构造1个只含0和1的向量$ \boldsymbol{A}=\left({\alpha }_{1}, {\alpha }_{2}, \cdots , {\alpha }_{n}\right) $。

2）Alice根据ELGamal同态加密算法生成公私钥对$ \left(\mathrm{p}\mathrm{k}, \mathrm{s}\mathrm{k}\right) $，选取不同的随机数$ {r}_{i} $，利用公钥$ \mathrm{p}\mathrm{k} $将向量A中各个元素分别加密得到$ E\left(\boldsymbol{A}\right)=\left(E\left({\alpha }_{1}\right), E\left({\alpha }_{2}\right), \cdots \mathrm{ }, E\left({\alpha }_{n}\right)\right) $，$ E\left({\alpha }_{i}\right)=\left({c}_{{i}_{1}}, {c}_{{i}_{2}}\right)=\left({g}^{{r}_{i}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{\alpha }_{i}}{h}^{{r}_{i}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)，$其中，$ {\alpha }_{i}\in \boldsymbol{A} $，$ i=\mathrm{1, 2}, \cdots , n $，并将$ E\left(\boldsymbol{A}\right) $发送给Bob。

3）Bob根据$ y $在隐私数据集合$ U $中的排列位置（即$ {a}_{l} $所在位置）进行以下操作：

（1）选取随机数$ {r}_{z}\in {\mathbb{Z}}_{N}^{\mathrm{*}} $，计算$ E\left({\alpha }_{l}\right)=\left({c}_{{l}_{1}}, {c}_{{l}_{2}}\right)=\left({g}^{{r}_{z}}{g}^{{r}_{i}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {h}^{{r}_{z}}{g}^{{\alpha }_{i}}{h}^{{r}_{i}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right) $。

（2）计算$ E\left(M\right)=E\left({\alpha }_{l}\right)E\left({\alpha }_{l+1}\right) $。

4）Bob将$ E\left(M\right) $发送给Alice。

5）Alice利用私钥$ \mathrm{s}\mathrm{k} $对$ E\left(M\right) $进行解密操作$ D\left(E\left(M\right)\right) $得到$ M $。若$ M=1 $，则$ x>y $；若$ M=g $，则$ x=y $；若$ M={g}^{2} $，则$ x<y $。

2.2.2 协议的正确性与安全性分析

本文对基于0-1编码规则的MP协议正确性与安全性进行分析。

定理1   在半诚实模型下，协议1是正确的，同时也是安全的。

正确性证明：

1）Alice拥有密文信息$ E\left({\alpha }_{i}\right)=\left({c}_{{i}_{1}}, {c}_{{i}_{2}}\right)=\left({g}^{{r}_{i}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, \right. $$ \left.{g}^{{\alpha }_{i}}{h}^{{r}_{i}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)，{\alpha }_{i}\in A, i=\mathrm{1, 2}, \cdots , n\text{。}$

2）基于ELGamal的同态加密变体算法具有加法同态性，计算公式如下：

$ \begin{array}{l}E\left({M}_{1}\right)\times E\left({M}_{2}\right)=\left({g}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{M}_{1}}{h}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)\times \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left({g}^{{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{M}_{2}}{h}^{{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)=\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left({g}^{{r}_{1}+{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{M}_{1}+{M}_{2}}{h}^{{r}_{1}+{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;E\left({M}_{1}+{M}_{2}\right)\end{array} $

(10)

3）Bob利用公钥对$ M={\alpha }_{l}+{\alpha }_{l+1} $计算过程进行加密：

$ \begin{array}{l}   E\left({\alpha }_{l}\right)E\left({\alpha }_{l+1}\right)=\left({g}^{{r}_{z}}{g}^{{r}_{l}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {h}^{{r}_{z}}{g}^{{\alpha }_{l}}{h}^{{r}_{l}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)\times \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left({g}^{{r}_{l+1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{\alpha }_{l+1}}{h}^{{r}_{l+1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)=\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left({g}^{{r}_{z}+{r}_{l}+{r}_{l+1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, \right.\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left.{g}^{{\alpha }_{l}+{\alpha }_{l+1}}{h}^{{r}_{z}+{r}_{l}+{r}_{l+1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;E\left({\alpha }_{l}+{\alpha }_{l+1}\right)=E\left(M\right)\end{array} $

(11)

4）Bob对$ E\left(M\right) $进行解密：

$ \begin{array}{l}D\left(E\left(M\mathrm{ }\right)\right)=\frac{{g}^{{\alpha }_{l}+{\alpha }_{l+1}}{h}^{{r}_{z}+{r}_{l}+{r}_{l+1}}}{{\left({g}^{{r}_{z}+{r}_{l}+{r}_{l+1}}\right)}^{x}}\mathrm{m}\mathrm{o}\mathrm{d}\;p=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{{g}^{{\alpha }_{l}+{\alpha }_{l+1}}{\left({g}^{x}\right)}^{{r}_{z}+{r}_{l}+{r}_{l+1}}}{{\left({g}^{{r}_{z}+{r}_{l}+{r}_{l+1}}\right)}^{x}}\mathrm{m}\mathrm{o}\mathrm{d}\;p=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{g}^{{\alpha }_{l}+{\alpha }_{l+1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\end{array} $

(12)

5）由于选取的安全参数$ k $很大，因此生成大小为$ k $ bit的$ p $很大，生成元$ g $非常小且满足$ {g}^{M}\mathrm{m}\mathrm{o}\mathrm{d}\;p={g}^{M} $。针对计算得到的$ {g}^{M} $：当$ {g}^{M}=1 $时，$ M=0 $，$ y $位置在$ x $左侧，$ x>y $；当$ {\mathrm{g}}^{M}=g $时，$ M=1 $，$ y $位置与$ x $位置相同，$ x=y $；当$ {g}^{M}={g}^{2} $，$ M=2 $，$ y $位置在$ x $右侧，$ x<y $。

安全性证明：

Alice根据自身隐私数据$ x $和双方的共有集合$ U=\left\{{v}_{1}, {v}_{2}, \cdots , {v}_{n}\right\} $构建向量$ \boldsymbol{A}=\left({\alpha }_{1}, {\alpha }_{2}, \cdots , {\alpha }_{n}\right) $，其中$ {\alpha }_{i}\in \left\{\mathrm{0, 1}\right\} $，$ i=\mathrm{1, 2}, \cdots , n $。Alice拥有公钥$ \mathrm{p}{\mathrm{k}}_{A} $与私钥$ \mathrm{s}{\mathrm{k}}_{A} $，在计算每个$ E\left({\alpha }_{i}\right)\left(i=\mathrm{1, 2}, \cdots , n\right) $时，其对利用ELGamal同态加密算法选取的不同$ r $进行加密操作，即$ E\left({\alpha }_{i}\right)=\left({c}_{{i}_{1}}, {c}_{{i}_{2}}\right)=\left({g}^{{r}_{i}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{\alpha }_{i}}{h}^{{r}_{i}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)，$其中，$ {\alpha }_{i}\in \boldsymbol{A}, $ $ i=\mathrm{1, 2}, \cdots , n $，由于选取的$ r $不同造成密文不同，因此对于加密后的向量$ \boldsymbol{E}\left(\boldsymbol{A}\right)=\left(E\left({\alpha }_{1}\right), E\left({\alpha }_{2}\right), \cdots , E\left({\alpha }_{n}\right)\right) $，Bob无法通过解密从中获取有用信息；Bob自身隐私数据$ y $在集合$ U $中位置为已知，其在向量$ \boldsymbol{A} $中对应的位置$ {a}_{l} $不变，Bob为混淆密文选取随机$ {r}_{z}\in {\mathbb{Z}}_{N}^{\mathrm{*}} $，若其利用$ {a}_{l} $直接计算$ E\left(M\right)=E\left({\alpha }_{l}\right)E\left({\alpha }_{l+1}\right) $，则Alice可通过列举方式计算每两个元素相乘的密文值$ E\left(M'\right)=E\left({\alpha }_{l}^{'}\right) $ $ E\left({\alpha }_{l+1}^{'}\right) $，当$ E\left(M'\right)=E\left(M\right) $时，可确定Bob的隐私数据$ y $在集合$ U $中的位置，从而造成其隐私数据泄露。因此，双方在整个过程中均无法获得对方的隐私信息。以下通过构造模拟器$ {S}_{1} $和模拟器$ {S}_{2} $进一步证明协议的安全性。

1）构造模拟器$ {S}_{1} $。

具体步骤如下：

（1）模拟器$ {S}_{1} $接受输入$ \left(x, p\left(x, y\mathrm{ }\right)\right) $，由$ p\left(x, y\right) $的值构造$ y' $且满足$ p\left(x, y'\right)=p\left(x, y\right) $，并用$ x' $和$ y $进行模拟。根据$ x $与$ U $构建只含0和1的向量$ \boldsymbol{A}=\left({\alpha }_{1}, {\alpha }_{2}, \cdots , {\alpha }_{n}\right) $。

（2）利用ELGamal同态加密算法选取不同$ r $对向量$ \boldsymbol{A}=\left({\alpha }_{1}, {\alpha }_{2}, \cdots , {\alpha }_{n}\right) $进行加密，得到：

$ \begin{array}{l}\boldsymbol{E}\left(\boldsymbol{A}\mathrm{ }\right)=\left(E\left({\alpha }_{1}\right), E\left({\alpha }_{2}\right), \cdots , E\left({\alpha }_{n}\right)\right)=\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left(\left({g}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{\alpha }_{1}}{h}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right), \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({g}^{{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{\alpha }_{2}}{h}^{{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right), \cdots ,\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left({g}^{{r}_{n}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{\alpha }_{n}}{h}^{{r}_{n}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)\right)\end{array} $

(13)

（3）根据$ \alpha {\mathrm{'}}_{l} $计算$ E\left(M'\right)=E\left({\alpha '}_{l}\right)E\left({\alpha '}_{l+1}\right) $。

（4）对数据$ E\left(M'\right) $进行解密得到$ M\mathrm{'} $。

在协议1中，$ \mathrm{v}\mathrm{i}\mathrm{e}{{\mathrm{w}}_{1}}^{\pi }\left(x, y\right)=\{\boldsymbol{A}, E\left(\boldsymbol{A}\right) $，令$ {S}_{1}\left(x, P(\right.x, $ $ \left.\left.y\right)\right)=\{\boldsymbol{A}, \boldsymbol{E}\left(\boldsymbol{A}\right), E\left(M'\right), P\left(x, y'\right)\} $，由于$ P\left(x, y\right)=P\left(x, y'\right) $，且协议计算所得值与模拟器计算所得值在计算上不可区分，即$ E{\left(M\right)}_{x, y}\stackrel{\mathrm{c}}{\equiv }E{\left(M'\right)}_{x, y} $，同时ELGamal同态加密算法是语义安全的，因此$ \left\{{S}_{1}\left(x, P\left(x, y\right)\right), \right.{\left.P\left(x, y\right)\right\}}_{x, y}\stackrel{\mathrm{c}}{\equiv } $ $ {\left\{\mathrm{v}\mathrm{i}\mathrm{e}{\mathrm{w}}_{1}^{\pi }\left(x, y\mathrm{ }\right), \mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}{\mathrm{t}}_{2}^{\pi }\left(x, y\mathrm{ }\right)\right\}}_{x, y} $成立。

2）构造模拟器$ {S}_{2} $。

具体步骤如下：

（1）模拟器$ {S}_{2} $接受输入$ \left(p\left(x, y\right), y\right) $，根据$ p\left(x, y\right) $的值构造$ x' $且满足$ p\left(x', y\right)=p\left(x, y\right) $，并用$ x' $和$ y $进行模拟。根据$ x' $与$ U' $构建只含0和1的向量$ \boldsymbol{A}'=\left({\alpha '}_{1}, {\alpha '}_{2}, \cdots , {\alpha '}_{n}\right) $。

（2）利用ELGamal同态加密算法选取不同$ {r}^{'} $对向量$ {\boldsymbol{A}}'=\left({{\alpha }^{'}}_{1}, {{\alpha }^{'}}_{2}, \cdots , {{\alpha }^{'}}_{n}\right) $进行加密，得到：

$ \begin{array}{l}E\left({\boldsymbol{A}}^{'}\mathrm{ }\right)=\left(E\left({\alpha }_{1}^{'}\mathrm{ }\right), E\left({\alpha }_{2}^{'}\mathrm{ }\right), \cdots , E\left({\alpha }_{n}^{'}\mathrm{ }\right)\right)=\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left(\left({g}^{{r}_{1}^{'}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{\alpha }_{1}^{'}}{h}^{{r}_{1}^{'}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right), \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left({g}^{{r}_{2}^{'}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{\alpha }_{2}^{'}}{h}^{{r}_{2}^{'}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right), \cdots , \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left({g}^{{r}_{n}^{'}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{\alpha }_{n}^{'}}{h}^{{r}_{n}^{'}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)\right)\end{array} $

(14)

（3）根据$ {{\alpha }^{'}}_{l} $计算$ E\left(M\mathrm{'}\right)=E\left({{\alpha }^{'}}_{l}\right)E\left({\alpha '}_{l+1}\right) $。

（4）对数据$ E\left({M}^{'}\right) $进行解密操作，得到$ {M}^{'} $。

在协议1中，$ \mathrm{v}\mathrm{i}\mathrm{e}{{\mathrm{w}}_{2}}^{\pi }\left(x, y\right)=\{E\left(\boldsymbol{A}\right), E\left(M\right), P\left(x, y\right)\} $，令$ {S}_{2}\left(P\left(x, y\right), y\right)=\{E\left(\boldsymbol{A}'\right), E\left({M}^{'}\right), P\left({x}^{'}, y\right)\} $，由于$ P(x, $ $ y)=P\left(x', y\right) $，且协议计算所得值与模拟器计算所得值在计算上不可区分，即$ E{\left(M\right)}_{x, y}\stackrel{\mathrm{c}}{\equiv }E{\left(M'\right)}_{x, y} $，同时ELGamal同态加密算法是语义安全的，因此$ \left\{{S}_{1}\left(x, P\left(x, y\right)\right), \right. $ $ \left.P\left(x, y\right)\right\}{}_{x, y}\stackrel{\mathrm{c}}{\equiv }{\left\{\mathrm{v}\mathrm{i}\mathrm{e}{\mathrm{w}}_{1}^{\pi }\left(x, y\right), \mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}{\mathrm{t}}_{2}^{\pi }\left(x, y\right)\right\}}_{x, y} $。

3 协议性能分析 3.1 计算效率分析

对协议1和文献[16, 19, 21]协议的计算复杂度、通信轮数以及适用范围进行对比。由于文献[16, 19]协议基于ElGamal同态加密算法，文献[21]协议基于Paillier同态加密算法，本文协议基于ELGamal同态加密变体算法，因此为便于对比分析，令Paillier同态加密算法模为N，数据长度为n，ElGamal同态算法及其变体算法的模为P，比较结果如表 1所示。

从上述3种协议的计算复杂性来看，协议1、文献[16, 19]协议都是基于ElGamal同态加密，而采用ElGamal同态加密算法进行1次加密需$ 2\mathrm{l}{\mathrm{b}}_{}\;P $次模乘计算，进行1次解密需$ \mathrm{l}{\mathrm{b}}_{}\;P $次模乘计算。协议1中Alice进行n次加密和1次解密，Bob进行3次模乘计算，总计算开销为$ \left(2n+3\right)\mathrm{l}{\mathrm{b}}_{}\;P+2 $次模乘计算；文献[16]协议需n次加密、n次解密和$ 2n\mathrm{l}{\mathrm{b}}_{}\;P+4n-6 $次模乘计算，总计算开销为$ 5n\mathrm{l}{\mathrm{b}}_{}\;N+4n-6 $次模乘计算。文献[19]协议中Alice需n次加密和1次解密，Bob需1次加密和2次模乘计算，总计算开销为$ \left(2n+3\right)\mathrm{l}{\mathrm{b}}_{}\;P+2 $次模乘计算。文献[21]协议需n次加密、1次解密与$ l $次模乘计算，由于该协议是基于Paillier同态加密，因此由Paillier同态加密算法中每次加密和解密需$ 2\mathrm{l}{\mathrm{b}}_{}\;N $次模乘计算可知，文献[21]协议的总计算开销为$ 2\left(n+1\right)\mathrm{l}\mathrm{b}\;N+l $次模乘计算。

从通信轮数来看，协议1中Alice将密文$ E\left(A\right) $发送给Bob，Bob将处理后的密文$ E\left(M\right) $反馈给Alice，Alice对其解密后得到结果$ M $并告知Bob，在整个协议执行过程中双方共通信3次，因此，协议1通信轮数为3，其他3种协议的通信轮数与协议1相同。

由上述分析可知，虽然协议1的通信轮数与其他协议相同，但是其计算复杂度较其他协议更低。此外，与文献[16]协议相比，协议1可更好地比较两数据相等的问题。因此，协议1整体计算效率优于其他协议。

3.2 计算耗时分析

将协议1和文献[16, 19, 21]协议加密和解密的计算耗时进行对比。实验采用Windows10 64位操作系统，Inter^® Core^TM i7-4720HQ 2.60 GHz CPU，8 GB内存以及MyEclipse 2017CI编译环境。假设上述协议中双方商定向量元素个数n=100，令Paillier同态加密算法与ELGamal同态加密算法中模数相同，则在模数为128 bit、256 bit、512 bit和1 024 bit时分别计算这2种同态加密算法加密和解密的耗时，结果如表 2所示。

由表 2可计算得到这2种算法加密和解密的平均耗时，结合3.1节中对4种协议的效率分析可得到各协议在不同模数下的时间开销，结果如图 2所示（文献[21]协议中$ l $值取决于Bob的隐私数据在商定向量中的位置，$ l $取值范围为[1, 100]，由于实验假定所商定向量的长度n=100，为便于对比，设定$ l=50 $）。由图 2可以看出：文献[16]协议的时间开销最高，协议1与文献[19]协议的时间开销最低且两者很接近。对协议1与文献[19]协议在不同模数下的时间开销进行对比，结果如表 3所示。可以看出，协议1在不同模数下的耗时均低于文献[19]协议。由上述分析可知，协议1时间开销低于其他协议，此结果与协议计算效率分析结果一致。

4 集合交集的势 4.1 问题描述

当前社交网络已深入人们的日常生活，为扩大用户交友范围，云服务器会向每个用户推荐可能认识的好友，其推荐时判断依据为用户之间相同好友数量。然而在服务器与用户交互过程中，服务器在精准计算不同用户之间相同好友数量的同时，还要保证用户隐私不被泄露。如果将计算相同好友数量的过程视为安全两方的计算问题，则该问题可转化为求解安全两方集合交集个数的问题，即：Alice拥有隐私数据集合$ {W}_{1}=\left\{{x}_{1}, {x}_{2}, \cdots , {x}_{n}\right\} $，Bob拥有隐私数据集合$ {W}_{2}=\left\{{y}_{1}, {y}_{2}, \cdots , {y}_{m}\right\} $，Alice与Bob在不泄露自身隐私数据集合情况下求解两集合交集的势。

4.2 协议设计

本文结合协议1，设计出求解保密集合交集势的协议，其具体内容如下：

1）Alice和Bob利用自身隐私数据集合与共有隐私数据集合$ U=\left\{{v}_{1}, {v}_{2}, \cdots , {v}_{z}\right\}\left(z\ge m+n\right) $构造0-1编码向量$ \boldsymbol{A}=\left({a}_{1}, {a}_{2}, \cdots , {a}_{z}\right) $和$ \boldsymbol{B}=\left({b}_{1}, {b}_{2}, \cdots , {b}_{z}\right) $，编码规则如下：

$ {a}_{i}=\left\{\begin{array}{c}1, {v}_{i}\in U\\ 0, {v}_{i}\notin U\end{array}\right., i=\mathrm{1, 2}, \cdots , z $

(15)

$ {b}_{i}=\left\{\begin{array}{c}1, {v}_{i}\in U\\ 0, {v}_{i}\notin U\end{array}\right., i=\mathrm{1, 2}, \cdots , z $

(16)

2）$ \left(G, D, E\mathrm{ }\right) $为ElGamal同态加密算法，$ k $为设定的安全参数，Alice运行G（$ k $）生成算法的公私钥对$ \left(\mathrm{p}\mathrm{k}, \mathrm{s}\mathrm{k}\right) $。Alice用公钥$ \mathrm{p}\mathrm{k} $加密向量$ \boldsymbol{A} $得到$ E\left(\boldsymbol{A}\right)=\left(E\left({a}_{1}\right), E\left({a}_{2}\right), \cdots , E\left({a}_{z}\right)\right) $，并将$ E\left(\boldsymbol{A}\right) $发送给Bob。

3）Bob计算$ E\left(M\right)=\left(E{\left({a}_{1}\right)}^{{b}_{1}}E{\left({a}_{2}\right)}^{{b}_{2}}\cdots E{\left({a}_{z}\right)}^{{b}_{z}}\right) $，并将其发送给Alice。

4）Alice通过私钥$ \mathrm{s}\mathrm{k} $对$ E\left(M\right) $进行解密得到数据$ \omega ={g}^{M} $，两集合交集的势$ M=\mathrm{l}\mathrm{o}{\mathrm{g}}_{g}\;\omega $。

求解保密隐私数据集合交集势的协议实现流程如下：

协议2  求解保密隐私数据集合交集势的协议

输入  Alice：$ {W}_{1}=\left\{{x}_{1}, {x}_{2}, \cdots , {x}_{n}\right\} $；Bob：$ {W}_{2}=\left\{{y}_{1}, {y}_{2}, \cdots , \right. $ $ \left.{y}_{m}\right\} $

输出  $ M $

1.$ \mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}, \mathrm{B}\mathrm{o}\mathrm{b} $：$ \mathrm{A}, \mathrm{U}\to \mathrm{A}=\left({\mathrm{a}}_{1}, {\mathrm{a}}_{2}, \cdots , {\mathrm{a}}_{\mathrm{z}}\right) $；$ \mathrm{B}, \mathrm{U}\to \mathrm{B}=\left({\mathrm{b}}_{1}, {\mathrm{b}}_{2}, \cdots , {\mathrm{b}}_{\mathrm{z}}\right) $

2.$ \mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e}\to \mathrm{B}\mathrm{o}\mathrm{b} $：$ \mathrm{E}\left(\mathrm{A}\right)=\left(\mathrm{E}\left({\mathrm{a}}_{1}\right), \mathrm{E}\left({\mathrm{a}}_{2}\right), \cdots , \mathrm{E}\left({\mathrm{a}}_{\mathrm{z}}\right)\right) $

3.$ \mathrm{B}\mathrm{o}\mathrm{b}\to \mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e} $：$ \mathrm{E}\left(\mathrm{M}\right)=\left(\mathrm{E}{\left({\mathrm{a}}_{1}\right)}^{{\mathrm{b}}_{1}}\mathrm{E}{\left({\mathrm{a}}_{2}\right)}^{{\mathrm{b}}_{2}}\cdots \mathrm{E}{\left({\mathrm{a}}_{\mathrm{z}}\right)}^{{\mathrm{b}}_{\mathrm{z}}}\right) $

4.$ \mathrm{A}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{e} $：$ \mathrm{D}\left(\mathrm{E}\left(\mathrm{M}\right)\right)={\rm{ \mathsf{ ω} }}$//$ {\rm{ \mathsf{ ω} }}={\mathrm{g}}^{\mathrm{M}}\mathrm{M}=\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{g}}\;{\rm{ \mathsf{ ω} }} $

定理2   在半诚实模型下，协议2是正确的，同时也是安全的。

正确性证明：

1）Alice拥有密文信息：$ E\left({a}_{i}\right)=\left({c}_{{i}_{1}}, {c}_{{i}_{2}}\right)=\left({g}^{{r}_{i}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{a}_{i}}{h}^{{r}_{i}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right), i=\mathrm{1, 2}, \cdots , z $。

2）基于ELGamal加密变体算法具有加法同态性，计算公式如下：

$ \begin{array}{l}E{\left({M}_{1}\right)}^{b}=\left({\left({g}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)}^{b}, {\left({g}^{{M}_{1}}{h}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)}^{b}\right)=\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left({g}^{{r}_{1}b}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{M}_{1}b}{h}^{{r}_{1}b}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;E\left(b{M}_{1}\right)\end{array} $

(17)

$ \begin{array}{l}E\left({M}_{1}\right)\times E\left({M}_{2}\right)=\left({g}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{M}_{1}}{h}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)\times \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left({g}^{{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{M}_{2}}{h}^{{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)=\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left({g}^{{r}_{1}+{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{M}_{1}+{M}_{2}}{h}^{{r}_{1}+{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;E\left({M}_{1}+{M}_{2}\right)\end{array} $

(18)

3）Bob利用编码后的隐私数据集合$ \boldsymbol{B}=\left({b}_{1}, {b}_{2}, \cdots , {b}_{z}\right) $对$ E\left({a}_{i}\right) $进行加密：

$ \begin{array}{l}\prod\limits_{i = 1}^z E{\left({a}_{i}\right)}^{{b}_{i}}=\prod\limits_{i = 1}^z \left({\left({g}^{{r}_{i}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)}^{{b}_{i}}, {\left({g}^{{a}_{i}}{h}^{{r}_{i}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)}^{{b}_{i}}\right)=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\prod\limits_{i = 1}^z \left({g}^{{r}_{i}{b}_{i}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{a}_{i}{b}_{i}}{h}^{{r}_{i}{b}_{i}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)=\\\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \prod\limits_{i = 1}^z E\left({a}_{i}{b}_{i}\right)=E\left(\sum _{i=1}^{z}{a}_{i}{b}_{i}\right)=E\left(M\mathrm{ }\right)\end{array} $

(19)

4）Bob对$ E\left(M\right) $进行解密：

$ D\left(E\left(M\right)\right)=\frac{{g}^{M}{h}^{r}}{{\left({g}^{r}\right)}^{x}}\mathrm{m}\mathrm{o}\mathrm{d}\;p=\frac{{g}^{M}{\left({g}^{x}\right)}^{r}}{{\left({g}^{r}\right)}^{x}}\mathrm{m}\mathrm{o}\mathrm{d}\;p=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{g}^{M}\mathrm{m}\mathrm{o}\mathrm{d}\;p=\omega $

(20)

5）由于选取的安全参数$ k $很大，因此生成大小为$ k $比特的$ p $很大，生成元$ g $非常小且满足$ {g}^{M}\mathrm{m}\mathrm{o}\mathrm{d}\;p={g}^{M} $。对解密后$ D\left(E\left(M\right)\right) $的数据$ \omega $进行计算得到$ M=\mathrm{l}\mathrm{o}{\mathrm{g}}_{g}\;\omega $，$ M $即集合的势。

安全性证明：

采用模拟器$ {S}_{1} $和模拟器$ {S}_{2} $证明定理2，首先构造模拟器$ {S}_{1} $。

1）模拟器$ {S}_{1} $接受输入$ \left(x, p\left(x, y\right)\right) $，由$ p\left(x, y\right) $的值构造$ y' $且满足$ p\left(x, y'\right)=p\left(x, y\right) $，并用$ x' $和$ y $进行模拟。根据$ x $与$ U $构建只含0和1的向量$ \boldsymbol{A}=\left({a}_{1}, {a}_{2}, \cdots , {a}_{z}\right) $。通过模拟器$ {S}_{1} $构造向量$ {\boldsymbol{B}}^{'}=\left({b}_{1}^{'}, {b}_{2}^{'}, \cdots , {b}_{z}^{'}\right) $。

2）利用ELGamal同态加密算法选取不同的$ r $对向量$ \boldsymbol{A}=\left({a}_{1}, {a}_{2}, \cdots , {a}_{z}\right) $进行加密，得到：

$ \begin{array}{l}E\left(\boldsymbol{A}\right)=\left(E\left({a}_{1}\right), E\left({a}_{2}\right), \cdots , E\left({a}_{z}\right)\right)=\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left(\left({g}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{a}_{1}}{h}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right), \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({g}^{{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{a}_{2}}{h}^{{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right), \cdots , \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({g}^{{r}_{z}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{a}_{z}}{h}^{{r}_{z}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)\right)\end{array} $

(21)

3）根据$ {\boldsymbol{B}}^{'}=\left({b}_{1}^{'}, {b}_{2}^{'}, \cdots , {b}_{z}^{'}\right) $计算$ E\left(M\mathrm{'}\right) $，计算公式如下：

$ \begin{array}{l}E\left(M'\right)=\left(E{\left({a}_{1}\right)}^{{b}_{1}^{'}}, E{\left({a}_{2}\right)}^{{b}_{2}^{'}}, \cdots , E{\left({a}_{z}\right)}^{{b}_{z}^{'}}\right)=\\\;\;\;\;\;\;\;\;\;\left({\left({g}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{a}_{1}}{h}^{{r}_{1}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)}^{{b}_{1}^{'}}, \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\left({g}^{{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{a}_{2}}{h}^{{r}_{2}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)}^{{b}_{2}^{'}}, \cdots , \\\;\;\;\;\;\;\; {\left({g}^{{r}_{z}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{a}_{z}}{h}^{{r}_{z}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)}^{{b}_{z}^{'}}\right)=\\\;\;\;\;\;\;\; \left(\left({g}^{{r}_{1}{b}_{1}^{'}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{a}_{1}{b}_{1}^{'}}{h}^{{r}_{1}{b}_{1}^{'}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right), \\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({g}^{{r}_{2}{b}_{2}^{'}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{a}_{2}{b}_{2}^{'}}{h}^{{r}_{2}{b}_{2}^{'}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right), \cdots ,\\\;\;\;\;\;\;\; \left({g}^{{r}_{z}{b}_{z}^{'}}\mathrm{m}\mathrm{o}\mathrm{d}\;p, {g}^{{a}_{z}{b}_{z}^{'}}{h}^{{r}_{z}{b}_{z}^{'}}\mathrm{m}\mathrm{o}\mathrm{d}\;p\right)\right)=\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \left(E\left({a}_{1}{b}_{1}^{'}\right), E\left({a}_{2}{b}_{2}^{'}\right), \cdots , E\left({a}_{z}{b}_{z}^{'}\right)\right)\end{array} $

(22)

4）对数据$ E\left(M\mathrm{'}\right) $进行解密得到$ M' $。

在协议2中，$ \mathrm{v}\mathrm{i}\mathrm{e}{{\mathrm{w}}_{1}}^{\pi }\left(x, y\right)=\{\boldsymbol{A}, E\left(\boldsymbol{A}\right), E\left(M\right), $ $ P(x, y)\}, $令$ {S}_{1}\left(x, P(x, y)\right)=\{\boldsymbol{A}, E\left(\boldsymbol{A}\right), E\left(M'\right), $ $ P(x, y')\} $，由于$ P\left(x, y\right)=P\left(x, y\mathrm{'}\right) $，且协议计算所得值与模拟器计算所得值在计算上不可区分，即$ E{\left(M\right)}_{x, y}\stackrel{\mathrm{c}}{\equiv }E{\left(M'\right)}_{x, y} $，同时ELGamal同态加密算法是语义安全的，因此$ {\left\{{S}_{1}\left(x, P\left(x, y\right)\right), P\left(x, y\right)\right\}}_{x, y}\stackrel{\mathrm{c}}{\equiv }{\left\{\mathrm{v}\mathrm{i}\mathrm{e}{\mathrm{w}}_{1}^{\pi }\left(x, y\right), \mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}{\mathrm{t}}_{2}^{\pi }\left(x, y\right)\right\}}_{x, y} $成立。

采用与上述类似的方法构造模拟器$ {S}_{2} $得到$ \left\{{S}_{1}\left(x, \right.\right. $ $ {\left.\left.P\left(x, y\right)\right)P\left(x, y\right)\right\}}_{x, y}\stackrel{\mathrm{c}}{\equiv }{\left\{\mathrm{v}\mathrm{i}\mathrm{e}{\mathrm{w}}_{1}^{\pi }\left(x, y\right), \mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}{\mathrm{t}}_{2}^{\pi }\left(x, y\right)\right\}}_{x, y} $。

在协议2中，Alice需执行$ n $次加密、1次解密和1次对数计算。Bob需要执行$ z $次模幂计算和$ z $次模乘运算，定义Mul、Exp、lb分别代表 1次模乘计算、1次模幂计算和1次对数计算。因此，协议2的计算复杂度为$ \left(\left(2n+1\right)\mathrm{l}{\mathrm{b}}_{}\;N+z\right)\mathrm{M}\mathrm{u}\mathrm{l}+{z}\;\mathrm{E}\mathrm{x}\mathrm{p}+1\times \mathrm{l}\mathrm{b} $。

在协议2中，Alice将编码后的隐私数据集合元素$ \boldsymbol{A} $进行加密，将加密结果$ E\left(\boldsymbol{A}\right) $发送给Bob，Bob对$ E\left(\boldsymbol{A}\right) $进行处理得到$ E\left(M\right) $并将其反馈给Alice，Alice对$ E\left(M\right) $解密并向Bob公布结果。在整个协议执行过程中双方共通信3次，因此通信轮数为3。

5 结束语

百万富翁问题作为安全多方计算的基本模块，常见于数据挖掘、数据查询和计算几何等方面，而现有解决方案计算效率与安全性较低。本文提出一种基于0-1编码的百万富翁问题协议，利用ELGamal同态加密的性质解决百万富翁问题，在半诚实模型下证明其安全性，并用协议求解安全两方集合交集个数。实验结果表明，与采用ElGamal和Paillier同态加密算法的协议相比，该协议计算效率更高。后续将在两数比较的基础上进行多数比较，以解决带隐私保护的多集合交集问题。