隐私保护的群组匹配方案解析

### 隐私保护的群组匹配方案解析 在移动社交网络中，用户常常需要在不泄露个人隐私信息的前提下，找到合适的群组加入。本文将介绍一种新颖的隐私保护群组匹配方案，该方案能有效保护用户隐私，同时具备较高的效率。 #### 1. 问题定义 ##### 1.1 系统模型 本系统是一个移动社交网络，包含陌生人 S、群组 P 和半可信第三方 C。每个用户使用如智能手机和平板电脑等联网便携设备。 - 陌生人 S 发起匹配过程，其个人资料中有 n 个属性，记为 \(A_s = \{a_{s,1}, \ldots, a_{s,n}\}\)。 - 群组 P 有 d 个成员 \(P_1, \ldots, P_d\)，每个成员的个人资料中有 m 个属性，记为 \(A_i = \{a_{i,1}, \ldots, a_{i,m}\}\)，且假设每个成员的属性集大小相同，即 \(|A_i| = m\)，\(1 \leq i \leq d\)。 - 所有用户的属性都需保密，存储在各自的本地便携设备中。半可信第三方 C 是一个具有高计算能力的计算中心，帮助用户完成匹配过程，但不访问和收集用户的属性。 在匹配过程中，陌生人 S 想收集与每个群组成员的交集，以决定是否加入群组 P；当 S 申请加入时，群组成员想了解与 S 的交集大小，以决定是否同意 S 的申请。 匹配属性和匹配度的定义如下： - 若群组成员属性集中的某个属性也在陌生人 S 的属性集中，则该属性为匹配属性；否则为不匹配属性。 - 陌生人 S 个人资料中属性 \(a_{s,j}\) 的匹配度 \(D_j\) 是群组中具有该属性的成员总数。陌生人 S 了解到的匹配结果可表示为 \(D(P) = \{D_1, \ldots, D_n\}\)。 ##### 1.2 对手模型 只考虑来自匹配过程参与者的内部攻击，假设陌生人 S、群组成员 \(P_1, \ldots, P_d\) 和第三方 C 都是诚实但好奇（HBC）的，即各方会诚实地遵循方案，但可能试图获取超出允许范围的信息。同时，同一群组的用户可能会交换信息以了解更多关于陌生人的私人资料，但陌生人 S 或任何群组成员不能与半可信第三方 C 勾结。 ##### 1.3 设计目标 - **安全目标**： - **SG - 1**：方案结束时，陌生人 S 仅了解与群组 P 的匹配度 \(D(P) = \{D_1, \ldots, D_n\}\)，而不知道群组成员的任何不匹配属性和确切的匹配信息。 - **SG - 2**：若陌生人 S 不申请加入群组 P，群组成员对 S 的属性一无所知；若 S 申请加入，群组成员仅了解与 S 的交集大小，而不知道确切的匹配属性。 - **SG - 3**：在方案的任何阶段，半可信第三方 C 无法获取超出其接收到的值、输出及其对应群组成员所能推导的信息。 - **可用性和效率**：对于移动社交网络中的群组匹配，应尽量减少人工交互。陌生人 S 只需确定最适合的群组并决定是否加入，群组成员需决定是否同意 S 的申请。同时，方案应足够轻量级和高效，以适应移动社交网络中便携设备有限的计算能力。 #### 2. 新颖的隐私保护群组匹配方案 该方案基于 FNP 协议，利用半可信第三方 C 帮助计算多项式求值，无需使用加法同态加密。方案包括四个阶段：设置、计算、匹配和申请。申请阶段仅在陌生人 S 申请加入群组 P 时执行。假设各方都有用于安全通信的公私钥对，加密算法分别记为 \(Enc_c\)、\(Enc_s\)、\(Enc_1, \ldots, Enc_d\)，且每个用户的属性都编码在 \(Z_p\) 中。 ##### 2.1 设置阶段 1. 陌生人 S 构建一个 n 次多项式 \(f(x)\)，其 n 个根都在他的属性集中： \[f(x) = (x - a_{s,1})(x - a_{s,2}) \ldots (x - a_{s,n}) = \sum_{k=0}^{n} \alpha_k x^k\] 2. 对于每个群组成员 \(P_i \in P\)，陌生人 S 从 \(Z_p\) 中随机生成 \(\{r_{i,j}\}_{1\leq j\leq m}\) 和 \(\{\tau_{i,k}\}_{1\leq k\leq n}\)。 3. 陌生人 S 将加密值 \(\{Enc_c(\tau_{i,1}r_{i,j}\alpha_1), \ldots, Enc_c(\tau_{i,n}r_{i,j}\alpha_n)\}_{1\leq j\leq m}\) 发送给半可信第三方 C，将 \(\{Enc_i(r_{i,j}\alpha_0)\}_{1\leq j\leq m}\) 和 \(\{Enc_i(\tau_{i,k})\}_{1\leq k\leq n}\) 发送给群组成员 \(P_i\)。 4. 群组成员 \(P_i\) 收到值并解密后，从 \(Z_p\) 中随机生成 \(\{r'_{i,j}\}_{1\leq j\leq m}\)，然后将 \(\{Enc_c(\frac{r'_{i,j}a_{i,j}^1}{\tau_{i,1}}), \ldots, Enc_c(\frac{r'_{i,j}a_{i,j}^n}{\tau_{i,n}})\}_{1\leq j\leq m}\) 和 \(Enc_s(r_{i,j}r'_{i,j}\alpha_0 + a_{i,j})_{1\leq j\leq m}\) 发送给半可信第三方