有理数域上集合成员关系的保密判定协议

Privacy Preserving Protocol of Rational Set Membership’s Judge

摘要: 本文通过将有理数按位编码为矩阵，并结合ElGamal同态加密算法，设计了有理数域上集合成员关系的保密判定协议，其中点集成员关系的保密判定协议可适用于 维有理点。其次，应用模拟范例的方法严格证明了协议的安全性，同时协议能够保护集合的势。最后，比较分析表明当参与者的有理数满足一定条件时，本文设计的协议是高效的。

Abstract: By encoding the rational numbers into a matrix, combined with the ElGamal homomorphic encryption algorithm, this paper designs secure protocol for the rational set membership’s judge, in which the protocol for the point set membership can be applied to n(n≥2) dimensional rational points. Secondly, using the well accepted simulation paradigm proves that the proposed protocols are secure, and at the same time, the protocol can protect the number of elements in the partici2243pant set. Finally, the comparison and analysis show that the efficiency of the proposed protocol when the rational numbers meet certain conditions.

1. 引言

隐私集合计算是安全多方计算 [1] [2] 领域中的一类重要问题，集合成员关系的保密判定问题是其中的一个基本问题，要求判定一个元素是否属于一个集合，而不泄露该元素和集合的具体信息。集合成员关系的保密判定问题在可搜索加密 [3]、访问控制 [4]、可撤销访问结构 [5] 等问题中有重要的应用。

集合成员关系保密判定可通过数据相等比较 [1] [6] [7]、两方集合交集或交集的势 [8] [9] [10] [11] [12]、集合包含关系 [13] [14] [15] [16] 的保密计算协议间接地来实现。上述方法或者需要将元素与集合中元素进行一一比较、或者不需要协议的全部计算功能，会使协议的效率欠佳或导致参与方拥有的信息泄露。文献 [17] 利用可交换加密方案提出了数集成员关系保密判定协议。文献 [18] 利用全同态加密，结合范德蒙行列式的性质，设计了集合成员判定关系的相关协议。上述协议均仅适用于整数集上的集合成员关系判定。文献 [19] 首次设计了有理数域上集合成员关系保密判定协议，并在数集成员关系保密判定协议的基础上，利用哥德尔编码将有理点编码为有理数，设计了点集成员关系的保密判定协议，但该协议只适用于2维有理点。

由于信息技术的快速发展，与坐标定位相关的应用软件得到了广泛应用，使用户的位置信息的私密性成为需要关注的问题。因此，设计有理点的相关保密计算协议有重要的实用价值。本文借助文献 [20] 中提出的按位编码思想，结合ElGamal同态加密算法，针对有理数集合成员关系和有理点集成员关系的判定问题设计了保密计算协议。

2. 预备知识

2.1. 安全多方计算模型

安全多方计算中通常使用半诚实模型和恶意模型。半诚实模型下的参与者会忠实地执行协议，但同时他们会保留执行协议中收到的中间信息，并试图推断其它参与者的输入。恶意模型下的参与者不按要求执行协议，可能有拒绝参加协议、提供错误的输入或者中间计算结果以及随时终止协议等行为。本文考虑半诚实模型下协议的安全性。

2.2. 半诚实模型下的安全性定义

设 $P_i\left(i=1,2\right)$ 拥有私密信息 $X_i$，利用协议 $\pi$ 合作计算函数 $f\left(X_1,X_2\right)=\left(f_1\left(X_1,X_2\right),f_2\left(X_1,X_2\right)\right)$，其中 $f_i\left(X_1,X_2\right)\left(i=1,2\right)$ 是 $P_i$ 收到的输出。将参与者 $P_i\left(i=1,2\right)$ 收到的信息序列记为 $VIE{W}_i^{\pi }\left(X_1,X_2\right)=\left(X_i,r_i,m_1^i,m_2^i,\cdots ,m_l^i,f_i\left(X\right)\right)$，其中 $X_i$ 是 $P_i$ 的输入， $r_i$ 是 $P_i$ 产生的随机数， $m_t^i\left(t=1,2,\cdots ,l\right)$ 表示 $P_i$ 收到的第t个消息。

定义1 [21] (半诚实模型下协议的安全性)对于 $f\left(X_1,X_2\right)=\left(f_1\left(X_1,X_2\right),f_2\left(X_1,X_2\right)\right)$，若存在概率多项式时间模拟器 $S_i\left(i=1,2\right)$ 满足下式：

${\left\{S_i\left(X_i,f\left(X_1,X_2\right)\right)\right\}}_{X_1,X_2}\stackrel{c}{\equiv }{\left\{VIE{W}_i^{\pi }\left(X_1,X_2\right)\right\}}_{X_1,X_2}$ (1)

则称 $\pi$ 保密地计算了 $f\left(X_1,X_2\right)$，其中符号 $\stackrel{c}{\equiv }$ 表示计算上不可区分。

可通过构造满足式 的概率多项式时间模拟器 $S_i\left(i=1,2\right)$ 来证明协议的安全性，此方法称为模拟范例 [21]。本文将用此方法证明协议的安全性。

2.3. ElGamal同态加密算法

同态加密的概念最早由RIVEST [22] 提出，可以通过对密文的操作实现对相应明文的计算。ElGamal加密算法 [23] 是基于有限域上计算离散对数问题的困难性和Diffie-Hellman假设设计的，算法描述如下：

1) 密钥生成算法

对给定安全参数k，系统生成一个k比特的大素数p和循环群 $Z_p^{*}$ 的一个生成元g。若选取随机数x作为私钥，对应公钥为 $h=g^x\mathrm{mod}p$。

2) 加密算法E

对明文 $M\left(M\in Z_p^{*}\right)$，选取的随机数r，加密得密文： $E\left(M\right)=\left(c_1,c_2\right)=\left(g^r\mathrm{mod}p,M{h}^r\mathrm{mod}p\right)$。

3) 解密算法D

对于密文 $E\left(M\right)$，其明文为： $M=c_2\cdot c_1^{-x}\mathrm{mod}p$。

ElGamal同态加密算法具有乘法同态性。对于明文消息 $M_1,M_2\left(M_1+M_2<p\right)$，其密文 $E\left(M_1\right),E\left(M_2\right)$ 满足 $E\left(M_1\right)\times E\left(M_2\right)=E\left(M_1\times M_2\right)$。

3. 有理数域上集合成员关系保密判定

3.1. 编码方法

李顺东 [20] 等人为了解决多个有理数相等保密判定问题，提出了按位编码的方法，将一个有理数编码为一个矩阵，具体过程如下：

首先，对于参与者 $P_i$ 持有的有理数 $x_i=a_i/b_i=a_i^1{a}_i^2\cdots a_i^{s_i}/b_i^1{b}_i^2\cdots b_i^{s_i}$，其中 $\gcd \left(a_i,b_i\right)=1$， $a_i^k,b_i^l\in \left\{0,1,\cdots ,9\right\},1\le k\le s_i,1\le l\le q_i$，统一其分子和分母位数分别为 $s,q$，位数不够的情况按下式转换数据，

$x_i\to \frac{0\cdots 0a_i^1{a}_i^2\cdots a_i^{s_i}}{0\cdots 0b_i^1{b}_i^2\cdots b_i^{q_i}}\to e_i^1\cdots e_i^j\cdots e_i^{s+q}$ (2)

即通过在分子分母之前补0将其拥有的有理数的分子分母位数统一，并将其分子分母连接起来，其中 $1\le j\le s+q$。其次，根据式(2)将有理数 $x_i$ 按位编码为矩阵：

$U_{\left(s+q\right)\times 10}=\left[\begin{array}{cccc}{u}_1^1& u_2^1& \cdots & u_{10}^1\\ u_1^2& u_2^2& \cdots & u_{10}^2\\ ⋮& ⋮& & ⋮\\ u_1^{s+q}& u_2^{s+q}& \cdots & u_{10}^{s+q}\end{array}\right]$ (3)

对于每一行 $u^j=\left[\begin{array}{cc}\begin{array}{cc}{u}_1^j& u_2^j\end{array}& \begin{array}{cc}\cdots & u_{10}^j\end{array}\end{array}\right]\left(1\le j\le s+q\right)$，有：

$u_k^j=\{\begin{array}{l}0,e_i^j=k-1\\ r_k^j,e_i^j\ne k-1\end{array}$ (4)

其中 $r_k^j\in Z_p^{*}$ 且是非零的随机数。现将上述编码方法中的式(4)改为：

$u_k^j=\{\begin{array}{l}1,e_i^j=k-1\\ r_k^j,e_i^j\ne k-1\end{array}$ (5)

其中 $r_k^j\in Z_p^{*}$ 且是大于1的随机数。下文将利用改动后的方法设计有理数域上集合成员关系的保密判定协议。

3.2. 有理数域上数集成员关系的保密判定

问题描述 Alice拥有有理数 $v_0$，Bob拥有有理数集合 $V=\left\{v_1,v_2,\cdots ,v_m\right\}$。双方希望在不泄露 $v_o$，V中元素及V的势的前提下合作计算函数 $P\left(v_0,V\right)$ ：若 $v_0\in V$， $P\left(v_0,V\right)=1$ ；否则， $P\left(v_0,V\right)=0$。

计算原理 Alice和Bob依据式(2)将有理数 $v_i\left(i=0,1,\cdots ,m\right)$ 作如下转换：

$v_i\to e_i^1\cdots e_i^j\cdots e_i^{s+q}$ (6)

其中 $1\le j\le s+q$。Alice依据式(5)将有理数 $v_0$ 编码为矩阵U，并将U发送给Bob。Bob对于其拥有的有理数 $v_i$，依据式(6)中的 $e_i^j\left(1\le j\le s+q\right)$ 从 $u^1$ 至 $u^{s\text{+}q}$ 中依次取出对应位置编码 $u_{e_i^1+1}^1,u_{e_i^2+1}^2,\cdots ,u_{e_i^{s+q}+1}^{s+q}$，计算 $U_i=u_{e_i^1+1}^1{u}_{e_i^2+1}^2\cdots u_{e_i^{s+q}+1}^{s+q}$，容易得到以下命题是正确的。

命题1 $P\left(v_0,V\right)=1$ 当且仅当对于每一个 $i=1,2,\cdots ,m$ 存在 $U_i=1$。

协议1有理数域上数集成员关系的保密判定协议

输入：Alice输入 $v_0$，Bob输入 $V=\left\{v_1,v_2,\cdots ,v_m\right\}$。

输出： $P\left(v_0,V\right)$

准备：Alice和Bob依据式(2)对有理数 $v_0,v_i\left(i=1,2,\cdots ,m\right)$ 进行转换得到式(6)。

1. Alice执行以下操作：

1) 产生ElGamal同态算法的密钥对 $\left(sk,pk\right)$ ；

2) 根据(5)式将 $v_0$ 按位编码为矩阵U；

3) 利用公钥 $pk$ 加密矩阵U中 $u_k^j=1$ 的分量，得加密矩阵：

$E\left(U\right)=\left[\begin{array}{cccc}{u}_1^1& u_2^1& \cdots & u_{10}^1\\ u_1^2& u_2^2& \cdots & u_{10}^2\\ ⋮& ⋮& & ⋮\\ u_1^{s+q}& u_2^{s+q}& \cdots & u_{10}^{s+q}\end{array}\right]=\left[\begin{array}{cccc}\left(c_{11}^1,c_{12}^1\right)& \left(c_{21}^1,c_{22}^1\right)& \cdots & \left(c_{\left(10\right)1}^1,c_{\left(10\right)2}^1\right)\\ \left(c_{11}^2,c_{12}^2\right)& \left(c_{21}^2,c_{22}^2\right)& \cdots & \left(c_{\left(10\right)1}^2,c_{\left(10\right)2}^2\right)\\ ⋮& ⋮& & ⋮\\ \left(c_{11}^{s+q},c_{12}^{s+q}\right)& \left(c_{21}^{s+q},c_{22}^{s+q}\right)& \cdots & \left(c_{\left(10\right)1}^{s+q},c_{\left(10\right)2}^{s+q}\right)\end{array}\right]$ (7)

其中 $\left(c_{\left(e_0^j+1\right)1}^j,c_{\left(e_0^j+1\right)2}^j\right)=E\left(1\right)$， $\left(c_{\left(\ne e_0^j+1\right)1}^j,c_{\left(\ne e_0^j+1\right)2}^j\right)\in Z_p^{*}\times Z_p^{*}$ 为随机数对。Alice将矩阵 $E\left(U\right)$ 及公钥 $pk$ 发送

给Bob。

2. 对于每个 $i=1,2,\cdots ,m$，Bob执行以下操作：

1) 根据式 中的 $e_i^j\left(1\le j\le s+q\right)$ 从 $E\left(U\right)$ 中按位取出密文 $E\left(u_{e_i^1+1}^1\right),E\left(u_{e_i^2+1}^2\right),\cdots ,E\left(u_{e_i^{s+q}+1}^{s+q}\right)$，并计算：

$E\left(U_i\right)=E\left(u_{e_i^1+1}^1\right)E\left(u_{e_i^2+1}^2\right)\cdots E\left(u_{e_i^{s+q}+1}^{s+q}\right)$ (8)

2) 选取正整数l，满足 $l>m$。从 $Z_p^{*}$ 中选取 $l-m$ 个大于1的随机数 $r_1,r_2,\cdots ,r_{l-m}$，并计算其密文 $E\left(r_1\right),E\left(r_2\right),\cdots ,E\left(r_{l-m}\right)$ ；

3) 对密文 $E\left(U_i\right),E\left(r_1\right),E\left(r_2\right),\cdots ,E\left(r_{l-m}\right)\left(i=1,2,\cdots ,m\right)$ 的顺序进行随机置换，并按置换后的顺序发

送给Alice。

3. Alice解密收到的密文，记解密结果为 $d_k\left(1\le k\le l\right)$。若存在 $d_k=1$，Alice输出 $P\left(v_0,V\right)=1$ ；否则，输出 $P\left(v_0,V\right)=0$。

正确性分析 命题1的正确性及本文采用的ElGamal加密算法的同态性保证了协议1的正确性。

安全性分析 Alice将加密矩阵 $E\left(U\right)$ 发送给Bob，由于Bob没有私钥，因此无法获得有理数 $v_0$ 的任何信息。Bob将随机置换后的l个密文 $E\left(U_i\right),E\left(r_1\right),E\left(r_2\right),\cdots ,E\left(r_{l-m}\right)\left(i=1,2,\cdots ,m\right)$ 发送给Alice，由于Alice不知道具体置换，因此无法推得集合V中任何元素的信息；同时，由于随机数 $r_1,r_2,\cdots ,r_{l-m}$ 均大于1，则发送密文 $E\left(r_1\right),E\left(r_2\right),\cdots ,E\left(r_{l-m}\right)$ 给Alice的操作不影响协议的正确性且隐藏了集合V的势。

定理1 协议1在半诚实模型下是安全的。

证明：利用模拟范例证明协议1的安全性。在协议1中， $f_1\left(v_0,V\right)=f_2\left(v_0,V\right)=P\left(v_0,V\right)$。首先构造模拟器 $S_1$， $S_1$ 接受输入 $\left(v_0,P\left(v_0,V\right)\right)$，按照如下方式运行：

1) 随机选取有理数集 $V^{\prime }=\left\{{v^{\prime }}_1,{v^{\prime }}_2,\cdots ,{v^{\prime }}_m\right\}$ 使得 $P\left(v_0,V\right)=P\left(v_0,V^{\prime }\right)$，将 $v_0,{v^{\prime }}_i\left(i=1,2,\cdots ,m\right)$ 进行转换：

$\begin{array}{l}{v}_0\to e_0^1\cdots e_0^j\cdots e_0^{s+q}\\ {v^{\prime }}_i\to e_i^1{}^{\prime }\cdots e_i^j{}^{\prime }\cdots e_i^{s+q}{}^{\prime }\end{array}$ (9)

2) $S_1$ 将 $v_0$ 编码为矩阵U，并加密得矩阵 $E\left(U\right)$，如式(7)所示。

3) 计算 $E\left({U^{\prime }}_i\right)=E\left(u_{e_i^1{}^{\prime }+1}^1\right)E\left(u_{e_i^2{}^{\prime }+1}^2\right)\cdots E\left(u_{e_i^{s+q}{}^{\prime }+1}^{s+q}\right)$， $\left(i=1,2,\cdots ,m\right)$，生成 $l-m$ 个大于1的随机数 ${r^{\prime }}_1,{r^{\prime }}_2,\cdots ,{r^{\prime }}_{l-m}$，计算其密文 $E\left({r^{\prime }}_1\right),E\left({r^{\prime }}_2\right),\cdots ,E\left({r^{\prime }}_{l-m}\right)$。

4) 解密 $E\left({U^{\prime }}_i\right),E\left({r^{\prime }}_1\right),E\left({r^{\prime }}_2\right),\cdots ,E\left({r^{\prime }}_{l-m}\right)\left(i=1,2,\cdots ,m\right)$，记解密结果为 ${d^{\prime }}_k\left(1\le k\le l\right)$，根据 ${d^{\prime }}_k$ 可得 $P\left(v_0,V^{\prime }\right)$。

令 $S_1\left(v_0,P\left(v_0,V\right)\right)=\left\{v_0,E\left({U^{\prime }}_i\right),{r^{\prime }}_u,E\left({r^{\prime }}_u\right),P\left(v_0,V^{\prime }\right)\right\}$，其中 $i=1,2,\cdots ,m$， $u=1,2,\cdots ,l-m$。而协议执行中， $VIE{W}_1\left(v_0,V\right)=\left\{v_0,E\left(U_i\right),r_u,E\left(r_u\right),P\left(v_0,V\right)\right\}$。由于Bob没有私钥，根据ElGamal加密算法的语义安全性，对Bob来说， $E\left(U_i\right)\stackrel{c}{\equiv }E\left({U^{\prime }}_i\right)$ 以及 $E\left(r_u\right)\stackrel{c}{\equiv }E\left({r^{\prime }}_u\right)$，其中 $i=1,2,\cdots ,m$， $u=1,2,\cdots ,l-m$。由于随机数计算上不可区分，则 $r_u\stackrel{c}{\equiv }{r^{\prime }}_u$。又因为 $P\left(v_0,V\right)=P\left(v_0,V^{\prime }\right)$，因此 $\left\{S_1\left(v_0,P\left(v_0,V\right)\right)\right\}=\left\{VIE{W}_1\left(v_0,V\right)\right\}$。

$S_2$ 可用类似方法构造，此处省略。定理1得证。

3.3. 有理数域上点集成员关系的保密判定

以n维有理点为例设计点集成员关系的保密判定协议。

问题描述 Alice拥有n维有理点 $X=\left(x_1,x_2,\cdots ,x_n\right)$，Bob拥有n维有理点集合 $Y=\left\{Y_1,Y_2,\cdots ,Y_m\right\}$，其中 $Y_t=\left(y_1^t,y_2^t,\cdots ,y_n^t\right)\left(t=1,2,\cdots ,m\right)$。双方希望在不泄露X、Y中元素及Y的势的前提下合作计算函数 $P\left(X,Y\right)$ ：若 $X\in Y$， $P\left(X,Y\right)=1$ ；否则 $P\left(X,Y\right)=0$。

计算原理 Alice和Bob依据式(2)将有理点 $X=\left(x_1,x_2,\cdots ,x_n\right),Y_t=\left(y_1^t,y_2^t,\cdots ,y_n^t\right)\left(t=1,2,\cdots ,m\right)$ 的坐标

作如下转换：

$\begin{array}{l}{x}_i\to e_i^1\cdots e_i^j\cdots e_i^{s+q}\\ y_i^t\to e_i^{t1}\cdots e_i^{tj}\cdots e_i^{t\left(s+q\right)}\end{array}$ (10)

其中 $i=1,2,\cdots ,n$， $1\le j\le s+q$。对于每一个 $i=1,2,\cdots ,k$，Alice依据下式：

${}_{(i)}u{}_k^j=\{\begin{array}{l}1,e_i^j=k-1\\ r_k^j,e_i^j\ne k-1\end{array}$ (11)

将 $x_i$ 编码为矩阵 ${}_{\left(i\right)}U$，并发送给Bob。对于每一个有理点 $Y_t\left(t=1,2,\cdots ,m\right)$ 的坐标 $y_i^t\left(i=1,2,\cdots ,n\right)$，Bob依据式(10)中的 $e_i^{tj}$，从 ${}_{\left(i\right)}u{}^1$ 至 ${}_{\left(i\right)}u{}^{s\text{+}q}$ 中依次取出对应位置编码 ${}_{\left(i\right)}u{}_{e_i^{t1}+1}^1,{}_{\left(i\right)}u{}_{e_i^{t2}+1}^2,\cdots ,{}_{\left(i\right)}u{}_{e_i^{t\left(s+q\right)}+1}^{s+q}$，并计算： $U_i^t={}_{\left(i\right)}u{}_{e_i^{t1}+1}^1\cdot {}_{\left(i\right)}u{}_{e_i^{t2}+1}^2\cdot \cdots \cdot {}_{\left(i\right)}u{}_{e_i^{t\left(s+q\right)}+1}^{s+q}$。容易得到以下命题是正确的。

命题2 $P\left(X,Y\right)=1$ 当且仅当对于每个 $t=1,2,\cdots ,m$ 存在 ${\displaystyle {\prod }_{i=1}^n{U}_i^t}=1$。

协议2有理数域上点集成员关系保密判定协议

输入：Alice输入有理点 $X=\left(x_1,x_2,\cdots ,x_n\right)$，Bob输入有理数集合 $Y=\left\{Y_1,Y_2,\cdots ,Y_m\right\}$，其中 $Y_t=\left(y_1^t,y_2^t,\cdots ,y_n^t\right)\left(t=1,2,\cdots ,m\right)$。

输出： $P\left(X,Y\right)$。

准备：Alice和Bob据式(2)对有理点 $X=\left(x_1,x_2,\cdots ,x_n\right),Y_t=\left(y_1^t,y_2^t,\cdots ,y_n^t\right)\left(t=1,2,\cdots ,m\right)$ 的坐标转换得到式(10)。

1. Alice执行以下操作：

1) 产生ElGamal加密算法的密钥对 $\left(sk,pk\right)$ ；

2) 根据(11)式将 $x_i\left(i=1,2,\cdots ,n\right)$ 按位编码为矩阵 ${}_{\left(i\right)}U$ ；

3) 利用公钥 $pk$ 加密矩阵 ${}_{\left(i\right)}U\left(i=1,2,\cdots ,n\right)$ 中 ${}_{\left(i\right)}u{}_k^j=1$ 的分量，得加密矩阵：

$E\left({}_{\left(i\right)}U\right)=\left[\begin{array}{cccc}E\left({}_{\left(i\right)}u{}_1^1\right)& E\left({}_{\left(i\right)}u{}_1^1\right)& \cdots & E\left({}_{\left(i\right)}u{}_{10}^1\right)\\ E\left({}_{\left(i\right)}u{}_1^2\right)& E\left({}_{\left(i\right)}u{}_1^2\right)& \cdots & E\left({}_{\left(i\right)}u{}_{10}^2\right)\\ ⋮& ⋮& & ⋮\\ E\left({}_{\left(i\right)}u{}_1^{s+q}\right)& E\left({}_{\left(i\right)}u{}_1^{s+q}\right)& \cdots & E\left({}_{\left(i\right)}u{}_{10}^{s+q}\right)\end{array}\right]=\left[\begin{array}{cccc}{}_{\left(i\right)}\left(c_{11}^1,c_{12}^1\right)& {}_{\left(i\right)}\left(c_{21}^1,c_{22}^1\right)& \cdots & {}_{\left(i\right)}\left(c_{\left(10\right)1}^1,c_{\left(10\right)2}^1\right)\\ {}_{\left(i\right)}\left(c_{11}^2,c_{12}^2\right)& {}_{\left(i\right)}\left(c_{21}^2,c_{22}^2\right)& \cdots & {}_{\left(i\right)}\left(c_{\left(10\right)1}^2,c_{\left(10\right)2}^2\right)\\ ⋮& ⋮& & ⋮\\ {}_{\left(i\right)}\left(c_{11}^{s\text{+}q},c_{12}^{s+q}\right)& {}_{\left(i\right)}\left(c_{21}^{s\text{+}q},c_{22}^{s+q}\right)& \cdots & {}_{\left(i\right)}\left(c_{\left(10\right)1}^{s\text{+}q},c_{\left(10\right)2}^{s+q}\right)\end{array}\right]$ (12)

其中 ${}_{\left(i\right)}\left(c_{\left(e_i^j+1\right)1}^j,c_{\left(e_i^j+1\right)2}^j\right)=E\left(1\right)$， ${}_{\left(i\right)}\left(c_{\left(\ne e_i^j+1\right)1}^j,c_{\left(\ne e_i^j+1\right)2}^j\right)\in Z_p^{*}\times Z_p^{*}$ 为随机数对。Alice将矩阵 ${}_{\left(i\right)}E\left(U\right)$ 及公钥 $pk$

发送给Bob。

2. 对于每一个 $t=1,2,\cdots ,m$ 和 $i=1,2,\cdots ,n$，Bob执行以下操作：

1) 根据 $y_i^t$ 从 $E\left(U\right)$ 中按位取出密文 $E\left({}_{\left(i\right)}u{}_{e_i^{t1}+1}^1\right),E\left({}_{\left(i\right)}u{}_{e_i^{t2}+1}^2\right),\cdots ,E\left({}_{\left(i\right)}u{}_{e_i^{t\left(s+q\right)}+1}^{s+q}\right)$，计算：

$U_i^t=E\left({}_{\left(i\right)}u{}_{e_i^{t1}+1}^1\right)E\left({}_{\left(i\right)}u{}_{e_i^{t2}+1}^2\right)\cdots E\left({}_{\left(i\right)}u{}_{e_i^{t\left(s+q\right)}+1}^{s+q}\right)$ (13)

进一步计算 $U_t={\displaystyle {\prod }_{i=1}^n{U}_i^t}$。

2) 选取正整数l，满足 $l>m$。从 $Z_p^{*}$ 中选取 $l-m$ 个大于1的随机数 $r_1,r_2,\cdots ,r_{l-m}$，并计算其密文 $E\left(r_1\right),E\left(r_2\right),\cdots ,E\left(r_{l-m}\right)$ ；

3) 对密文 $E\left(U_i\right),E\left(r_1\right),E\left(r_2\right),\cdots ,E\left(r_{l-m}\right)\left(i=1,2,\cdots ,m\right)$ 的顺序进行随机置换，并按置换后的顺序发

送给Alice。

3. Alice解密收到的密文，记解密结果为 $d_k\left(1\le k\le l\right)$。若存在 $d_k=1$，Alice输出 $P\left(X,Y\right)=1$ ；否则，输出 $P\left(X,Y\right)=0$。

正确性分析 命题2的正确性以及本文采用的ElGamal加密系统的同态性保证了协议2的正确性。

安全性分析 X、Y中元素及Y的势的隐私性可类似于协议1中 $v_o$ 、V中元素及V的势的隐私性进行分析。

定理2 协议2在半诚实模型下是安全的。

定理2的证明类似于定理1的证明，故省略。

4. 协议分析与比较

本文中设计的协议用到了ElGamal同态加密算法，计算复杂性分析只考虑费时的模指数运算。用通信次数衡量协议的通信复杂性，一方发送给另一方算一次。

计算复杂性分析 每进行一次ElGamal加密(解密)操作需要2次(1次)模指数运算。协议1中Alice需加密 $s+q$ 次，解密l次；Bob需加密 $l-m$ 次。因此，协议1共需 $3l+2\left(s+q\right)-2m$ 次模指数运算。类似地进行分析可知协议2共需 $3l+2n\left(s+q\right)-2m$ 次模指数运算。

通信复杂性分析 协议1和协议2的通信次数均为2次。

将本文设计的协议与文献 [19] 中的协议进行比较，结果如表1所示。

Table 1. The comparison of protocols

表1. 协议的比较

注解：其中l均是参与方为隐藏集合的势选取的正整数。

相比文献 [19]，当参与计算的有理数按(2)式统一转换后，当 $s+q<m$ 时，协议1计算复杂性低；当 $n=2$ 且 $s+q<m/2$ 时，协议2计算复杂性低。本文协议的通信效率高于文献 [19] 中的协议。此外，协议2可用于 $n\left(n\ge 2\right)$ 维有理点。

5. 结束语

针对有理数域上集合成员关系的保密判定问题，本文借助文献 [20] 中按位编码的方法，提出了有理数集成员关系和有理点集成员关系的保密判定协议，且点集成员关系的保密判定协议适用于 $n\left(n\ge 2\right)$ 维有理点。比较分析表明本文设计的协议通信效率高于相关协议，当参与计算的有理数满足一定条件时，本文协议的计算复杂度更低。因此，未来将进一步研究高效的集合成员关系的保密判定协议。