移动互联网环境下新兴技术的快速发展与应用, 使得类别数据(categorical data)的获取与收集变得尤为容易. 类别数据的收集与分析能够有效提升产品服务与设备服务的质量, 以及向用户提供个性化体验. 直方图是类别数据分析的常用技术, 该技术使用分箱结构近似描述类别数据的分布信息, 按照类别属性划分成不相交的桶, 每个桶由频率或者计数表示其特征. 例如, 图 1(a)描述了用户所拥有的类别属性(disease), 图 1(b)是基于该类别属性产生的直方图. 然而, 类别数据通常蕴含着个人的敏感信息, 在提供给收集者或者不可信第三方时, 个人隐私有可能被泄露. 例如, 图 1(b)中疾病dia的频率是2, 不可信收集者获得dia的频率并且操纵Ann后, 即可对图 1(a)中的Bob进行链接攻击与操纵攻击^[1].

本地化差分隐私技术(local differential privacy, LDP)下的直方图发布有效解决了类别数据收集过程中个人隐私泄露问题, 该技术允许每个用户扰动自身数据之后再响应收集者的需求. 然而, LDP下直方图发布方法存在一些不足: (1) LDP下的直方图发布结果达不到中心化差分隐私(central differential privacy, CDP)下的发布精度, 例如, LDP下聚集求和(SUM)误差为$ \mathit{\Theta} (\sqrt n ) $, 而CDP下的聚集求和误差仅为Θ(1); (2) 恶意收集者可用通过扰动后的值(或者消息)与用户之间的链接关系, 对目标用户的身份进行甄别^[2]; (3) LDP的隐私预算设置比CDP设置的值大, 弱化了差分隐私保护程度. 与LDP相比, 尽管CDP下的直方图发布精度高, 然而由于假设中心化收集者是可信的, 并且能够看到所有用户的原始类别数据, 则CDP不及LDP安全. 混洗差分隐私(shuffled differential privacy, SDP)是处于CDP与LDP之间的一种模型, 通过混洗操作打乱了用户身份与消息之间的对应关系, 能够为用户提供类似于LDP模型保护的力度, 也能为收集者提供类似于CDP模型提供的查询与分析精度.

目前, 基于SDP的直方图发布方法包括SH^[3]、AUE^[4]、MURS^[5]以及mixDUMP^[6]算法. SH算法结合线性组合技术对本地扰动方法GRR^[7]的输出概率进行线性分解, 利用均匀噪音掩盖真实数据. 该算法实现了隐私增强并且提升了发布精度. 然而, SH算法由于采用GRR扰动方法, 其发布精度易受较大值域的影响, 大值域会造成SH的发布精度急剧下降. 不同于SH算法, AUE算法的发布精度不受值域大小的影响. 然而, 该算法由于利用了One-Hot编码机制, 进而会导致通信代价与值域大小呈线性关系. 为了克服SH与AUE算法存在的不足, MURS算法利用对称本地哈希技术把大值域哈希到较小的地址空间中, 实现了发布精度的提升与通信代价的减小. 类似于MURS算法, mixDUMP算法结合多消息混洗模式实现了直方图的发布. 然而, 该算法的核心扰动方法依然是GRR方法, 发布精度依然受到类别数据值域大小的影响. 此外, SH、AUE、MURS与mixDUMP这4种算法均没有详细介绍如何实现消息的混洗操作.

结合文献[1−4]可知, 利用SDP发布直方图依然存在诸多挑战: (1) 本地用户在设计混洗随机应答机制时, 如何避免大值域对发布精度与通信代价的影响; (2) 混洗方如何设计高效的随机排列方法来实现用户消息的混洗操作; (3) 收集者如何设计有效的后置处理技术来提升最终的发布精度. 总而言之, 目前还没有一个行之有效且满足混洗差分隐私的直方图发布算法能够克服上述方法存在的问题. 为此, 本文基于混洗差分隐私技术提出了一种直方图发布算法——HP-SDP能够兼顾上述的问题需求.

本文的主要贡献如下:

1) 为了解决挑战1, HP-SDP算法提出了一种混洗随机应答机制SRR (shuffled randomized response), 该机制利用优化本地哈希机制的线性分解方式摆脱了值域大小的影响;

2) 为了解决挑战2, HP-SDP算法提出了一种基于堆排列方法的用户消息均匀随机排列算法MRS (message random shuffling). 混洗方利用MRS对所有用户的消息进行随机排列, 进而使得恶意收集者无法通过消息与用户之间的链接对目标用户进行身份甄别;

3) 为了解决挑战3, HP-SDP算法提出了一种基于二次规划技术的后置处理算法POP (post-process), 收集者利用POP算法对混洗方发送过来的消息进行求精处理;

4) 理论分析了HP-SDP算法满足(ε, δ)-中心化差分隐私, 以及每个桶频率的无偏性、误差边界以及最大偏差. 通过合成数据与真实数据实验分析, HP-SDP算法具有较高的可用性.

1 相关工作

基于差分隐私的直方图发布得到较为广泛的研究. CDP下直方图发布通过收集所有用户的原始数据来发布噪音直方图. LAP^[8]、Boost^[9]及NoiseFirst^[10]是CDP下直方图发布的典型代表. LAP算法直接在直方图的每个桶中添加拉普拉斯噪音来保护相应的计数值, 该算法产生的发布误差为$ {\text{O}}(\sqrt n /\varepsilon ). $ Boost算法采用层次树的节点记录桶中的计数, 再结合层次树高度与拉普拉斯机制完成直方图发布, 该算法的发布误差为$ {\text{O}}(\sqrt {\log 3n} /\varepsilon ). $不同于Boost算法, NoiseFirst算法首先利用拉普拉斯机制对每个桶添加噪音, 再利用基于动态规划的分组策略对所有噪音桶计数进行聚类分组, 然后发布重构之后的直方图, 该算法的发布误差为$ {\text{O}}(\sqrt {n - d} /\varepsilon ), $其中, d为类别属性的值域大小. LDP下的直方图发布算法通过基于用户本地扰动的数据构建直方图. Rappor^[11]、SHist^[12]与TreeHist^[13]是LDP下的直方图发布代表算法. Rappor算法结合一元编码与布隆过滤技术, 把类别属性的整个值域哈希到较小的值域中, 结合哈希值域统计每个类别属性的频率, 其发布误差为$ {\text{O}}(d/\varepsilon \sqrt n ). $ SHist方法采用随机矩阵投影技术对类别属性的值域进行编码, 随机扰动1个比特位发送给收集者, 发布误差为$ {\text{O}}(\sqrt {\log d} /\varepsilon \sqrt n ). $相比于SHist算法, 为了减少计算代价, TreeHist算法借助于计数概要与Hadamard转换技术构建满足LDP的前缀树, 遍历前缀树中的各个节点即可获得相应的直方图, 该算法的发布误差为$ {\text{O}}(\sqrt {\log (n)\log d} /\varepsilon \sqrt n ). $

根据上述分析可知, CDP与LDP下的直方图发布算法各自存在不同的优缺点. CDP下的直方图发布误差低, 然而收集者泄露用户隐私的风险高. LDP下的用户隐私泄露风险低, 然而直方图发布误差高. SDP模型的出现有效地平衡了中心化与本地化差分隐私的缺点. ESA^[14]是首个混洗技术与差分隐私技术融合的框架, 用户本地扰动的消息以匿名通道的方式传送给混洗方, 进而使得收集者无法重甄别目标用户的身份. 然而, 该框架没有给出混洗差分隐私的形式化定义以及误差边界. DDPS^[15]算法结合单消息混洗框架给出了混洗差分隐私的形式化定义, 并实现了二进制数据的非交互式聚集查询, 该算法将GRR算法分解成伯努利分布与均匀分布来本地扰动二进制数据. 然而, 该算法的通信代价高且可用性比较低, 相应的查询误差为$ {\text{O}}(\sqrt {\log d\log 1/\delta } /\varepsilon n). $不同于DDPS算法, DPSMS^[16]算法利用多消息扰动-混洗模型与IKOS^[17]安全协议实现了实数聚集查询, 并取得了近似于拉普拉斯机制所产生的误差O(1/ε). 然而, 该算法由于使用了安全协议导致了很高的通信代价. 类似于DPSMS算法, CESS^[18]算法采用多消息并行化扰动-混洗框架实现了[0, 1]区间上的求和查询, 该算法利用多个混洗协议与IKOS协议实现了分布式拉普拉斯机制产生的误差效果, 其查询误差为O(1/ε). 上述算法通常关注于实数域内的聚集查询, 而涉及直方图发布的研究较少. 目前, SH、AUE、MURS以及mixDUMP是SDP下直方图发布的典型的代表算法. SH算法利用单消息混洗框架实现了实数型数值上的直方图发布, 尽管该算法的发布精度与通信代价优于DDPS算法, 但其自身的发布精度受值域大小的影响, 值域越大, 发布误差越高. AUE算法结合One-Hot编码机制实现了混洗差分隐私下的直方图发布, 然而该算法的通信代价与类别属性的值域线性相关, 并且不满足本地化差分隐私. MURS与mixDUMP算法分布利用对称本地哈希编码机制与GRR算法实现了直方图发布. 尽管这两种算法借助于多消息提升了发布精度, 然而它们与SH、AUE类似, 没有给出具体的混洗排列方法以及后置处理方法. 基于上述分析, 本文提出一种基于单消息单混洗方框架且满足混洗差分隐私的直方图发布算法HP-SDP, 该算法利用快速随机排列与后置处理技术提升最终的发布精度.

2 基础知识与问题描述 2.1 混洗差分隐私

不同于CDP与LDP隐私保护技术, SDP利用拼接与排列技术处理所有用户本地扰动之后的消息向量, 确保混洗操作满足(ε, δ)-CDP, 并完成LDP向CDP的过渡. 3种差分隐私保护模型的形式化定义如下所示.

设D (D∈$\mathcal{D}$)为分布式类别数据集, D={v₁, v₂, …, v_n}由n个类别数据构成且∀v_i∈$\mathcal{D}$, d=|$\mathcal{D}$|. n个类别数据分布在n个用户手中.

定义1((ε, δ)-中心化差分隐私). 设D与D′彼此相差一条类别数据且互为近邻关系. 给定一个直方图发布协议$\mathcal{M}$, $\mathcal{Y}$为$\mathcal{M}$的输出域, 若$\mathcal{M}$在D与D′上任意输出结果的概率满足下列不等式, 则$\mathcal{M}$满足(ε, δ)-中心化差分隐私:

$ \operatorname{Pr}[\mathcal{M}(D) \in \mathcal{Y}] \leqslant \mathrm{e}^{\varepsilon} \times \operatorname{Pr}\left[\mathcal{M}\left(D^{\prime}\right) \in \mathcal{Y}\right]+\delta$

(1)

其中, ε表示隐私预算, δ为(δ∈(0, 1])隐私泄露风险概率, e表示自然对数的底数.

定义2((ε, δ)-本地化差分隐私). 设v_i与$ {v'_i} $为值域$\mathcal{D}$上任意两条不同类别数据. 给定一个直方图发布协议$\mathcal{M}$=(Ρ, ε), $\mathcal{Y}$为$\mathcal{M}$的输出域, 若$\mathcal{M}$在v_i与$ {v'_i} $上任意输出结果的概率满足下列不等式, 则$\mathcal{M}$满足(ε, δ)-本地化差分隐私:

$ \operatorname{Pr}[\mathcal{M}(v) \in \mathcal{Y}] \leqslant \mathrm{e}^{\varepsilon} \times \operatorname{Pr}\left[\mathcal{M}\left(v^{\prime}\right) \in \mathcal{Y}\right]+\delta $

(2)

其中, $\mathcal{R}$表示本地随机应答机制, ε表示隐私预算, δ为(δ∈(0, 1])隐私泄露风险概率, e表示自然对数的底数.

定义3((ε, δ)-混洗差分隐私). 设$\mathcal{M}$=($\mathcal{R}$, $\mathcal{S}$, $\mathcal{A}$). 每个用户u_i利用$\mathcal{R}$: $\mathcal{D}$→$\mathcal{Y}$扰动v_i: y_i=$\mathcal{R}$(v_i). 令M={y₁, y₂, …, y_n}, $\mathcal{S}$(M)为混洗之后的输出结果, 其值域为$\mathcal{Y}$′. 如果$\mathcal{S}$(M): $\mathcal{Y}$→$\mathcal{Y}$′满足(ε, δ)-中心化差分隐私, 则$\mathcal{M}$满足(ε, δ)-混洗差分隐私:

$ \operatorname{Pr}\left[\mathcal{S}(M) \in \mathcal{Y}^{\prime}\right] \leqslant \mathrm{e}^{\varepsilon} \times \operatorname{Pr}\left[\mathcal{S}\left(M^{\prime}\right) \in \mathcal{Y}^{\prime}\right]+\delta $

(3)

其中, $\mathcal{R}$表示本地混洗随机应答机制, $\mathcal{S}$表示混洗排列机制, $\mathcal{A}$表示收集端的直方图发布需求, ε表示隐私预算, δ为(δ∈(0, 1])隐私泄露风险概率, e表示自然对数的底数.

2.2 随机应答机制

由定义1−定义3可知: 若要实现混洗差分隐私, 需要设计合理的本地混洗随机应答协议$\mathcal{R}$以及混洗协议$\mathcal{S}$. 目前, 随机应答机制^[19]是实现本地扰动的常用技术. 在用户发送数据v_i之前, 对其进行随机扰动. 该机制

的原始思想是用户在响应敏感布尔问题查询时, 以概率p真实应答, 以q的概率给出相反的应答. 目前, 基于随机应答机制出现了以GRR与OLH^[20]为代表的本地扰动方法.

● GRR方法.

给定v_i与v_j, 且v_i, v_j∈{1, 2, …, d}, GRR方法如公式(4)所示:

$ \Pr [GRR({v_i}) = {v_j}] = \left\{ {\begin{array}{*{20}{l}} {p = \frac{{{{\text{e}}^\varepsilon }}}{{{{\text{e}}^\varepsilon } + d - 1}},{\text{ }}{v_j} = {v_i}} \\ {q = \frac{{1 - p}}{{d - 1}},{\text{ }}{v_j} \ne {v_i}} \end{array}} \right. $

(4)

其中, v_i表示用户拥有的数据; v_j表示值域{1, 2, …, d}中的其他数据; d表示类别值域的大小; e表示自然对数的底数.

● OLH方法.

给定v_i且v_i∈{1, 2, …, d}, OLH利用哈希簇$\mathcal{H}$把v_i编码成{1, 2, …, g} (g < < d)中某个哈希值, 即x=H(v_i), 且x∈{1, 2, …, g}, H∈$\mathcal{H}$. OLH本地扰动思想如公式(5)所示:

$ \Pr [OLH(x) = y] = \left\{ {\begin{array}{*{20}{l}} {p = \frac{{{{\text{e}}^\varepsilon }}}{{{{\text{e}}^\varepsilon } + g - 1}},{\text{ }}x = y} \\ {q = \frac{1}{{{{\text{e}}^\varepsilon } + g - 1}},{\text{ }}x \ne y} \end{array}} \right. $

(5)

其中, v_i表示用户拥有的数据, x表示v_i经过哈希函数H哈希之后的值, y表示哈希值域{1, 2, …, g}中的任意值, g表示哈希函数值域的大小, d表示类别值域的大小, e表示自然对数的底数.

2.3 问题描述

给定n个用户、单个可信的混洗方和一个收集者. 每个用户拥有类别数据v_i, 且∀v_i∈$\mathcal{D}$, v_i通过$\mathcal{R}$本地扰动后发送消息给混洗方$\mathcal{S}$. 混洗方混洗所有消息, 即$\mathcal{S}$($\mathcal{R}$(v₁), $\mathcal{R}$(v₂), …, $\mathcal{R}$(v_n)). 收集者基于混洗后的消息向量构建直方图, 即$\mathcal{A}$($\mathcal{S}$($\mathcal{R}$(v₁), $\mathcal{R}$(v₂), …, $\mathcal{R}$(v_n))). 本文要解决的问题是: 在发布直方图的过程中, 如何使得$\mathcal{S}$($\mathcal{R}$(v₁), …, $\mathcal{R}$(v_n))满足(ε, δ)-CDP, 且发布结果的均方差较小. 均方差MSE (mean squared error)的表达式为

$ MSE(F,\tilde F) = \frac{1}{d}\sum\limits_{v \in \mathcal{D}} {{\text{E}}{{({f_v} - {{\tilde f}_v})}^2}} $

(6)

其中, F与$ \tilde F $分别表示原始直方图与估计直方图, f_v与$ {\tilde f_v} $分别表示类别数据(或者桶)v的真实频率与估计频率, d表示类别值域的大小.

3 直方图发布算法HP-SDP 3.1 直方图发布的原则

基于相关工作的分析可知, 在设计新的基于混洗差分隐私直方图发布算法时, 需要考虑3个原则.

1) 针对现有算法无法有效地处理类别属性值域过大的问题, 所设计的算法应尽可能地利用压缩技术(例如哈希转换)将原始值域转换到较小的值域空间;

2) 针对现有算法没有顾及如何具体实现用户消息的混洗排列操作, 所设计的算法应尽可能地体现该操作的高效性;

3) 针对现有算法没有考虑收集者如何设计有效的后置处理技术问题, 所设计的算法应尽可能地体现后置处理技术在提高直方图发布精度方面的作用.

针对原则1−原则3, 本文基于文献[5]提出了结合优化本地哈希技术的单消息混洗随机应答机制, 并实现了用户消息的随机混洗. 在此基础上, 提出了一种有效的直方图发布框架HP-SDP, 如图 2所示. 其中, E(⋅)表示用户的本地编码机制、$\mathcal{R}$表示混洗随机应答机制、$\mathcal{S}$表示混洗排列机制、$\mathcal{A}$表示收集者的直方图发布需求. 该框架与CDP与LDP下的直方图发布存在本质上的区别: (1) 该框架中用户数据依然在用户端, 与(ε_c, δ)-CDP中收集者完全掌控用户的原始数据不同; (2) 该框架满足(ε_c, δ)-CDP, 且发布精度高于(ε, δ)-LDP; (3) 从定义1−定义3可知, 该框架能够实现隐私增强, 即ε越小, 隐私保护程度越高.

3.2 HP-SDP算法

本节介绍HP-SDP算法, 该算法包括混洗随机扰动、随机排列以及直方图发布等操作, 具体实现细节如算法1所示.

算法1. HP-SDP.

输入: n个用户, 每个用户的数据v, 隐私预算ε, 哈希函数的值域$\mathcal{G}$, |$\mathcal{G}$|=g, γ;

输出: 直方图$ \bar F. $

1.     M←∅, $ \tilde F \leftarrow \emptyset ; $

用户端: $\mathcal{R}$

2.     for users i=1 to n do

3.       User i computes 〈H_i, y_i〉=SRR(v_i, ε); //第i个用户利用SRR算法本地扰动v_i, 产生〈H_i, y_i〉

4.       User i sends 〈H_i, y_i〉 to the shuffler; //第i个用户将扰动结果〈H_i, y_i〉发送给混洗方

5.     end for

混洗方: $\mathcal{S}$

6.     Shuffler concatenates each pair 〈H_i, y_i〉: M←M∪〈H_i, y_i〉; //混洗方拼接所有用户发来的消息

7.     Shuffler randomly permutates σ: σ=MRS(M); //混洗方利用MRS算法均匀随机混洗所有的消息

8.     Shuffler sends σ to the collector; //混洗方将混洗后的消息向量发送给收集者

收集方: $\mathcal{A}$

9.     for each 〈H_i, y_i〉∈σ do

10.     $ {\tilde f_v} = \frac{1}{n} \cdot \frac{{\sum\limits_{i = 1}^n {{I_{\{ {H_i}(v) = {y_i}\} }} - n\gamma \frac{{g - 1}}{g}} }}{{1 - 2\gamma \frac{{g - 1}}{g}}}; $ //收集方估计每个类别数据v所对应的频率

11.     $ \tilde F \leftarrow \tilde F \cup {\tilde f_v}; $ //估计类别数据值域中每个值的频率

12. end for

13.   $ \bar F = POP(\tilde F); $ //对估计后的直方图进行后置处理

14. return $ \bar F. $

HP-SDP算法基于SDP来解决直方图的发布问题. 首先, 每个用户利用混洗随机应答机制SRR本地处理自己的数据并产生相应的消息, 然后再将消息发送给混洗方(步骤2−步骤5). 混洗方把所有的用户消息拼接成为M(步骤6), 再对M中的消息进行随机混洗排列, 然后将混洗结果发送给收集者(步骤7、步骤8). 收集者结合混洗后的消息向量σ构建相应的直方图并对其进行后置处理(步骤9−步骤13). 由算法1可知, 混洗随机应答机制SRR、混洗随机排列MRS以及后置处理POP是HP-SDP算法的核心步骤. 下面, 首先阐述SRR算法的具体实现细节.

为了有效解决类别属性值域过大带来的影响, 本文基于文献[5], 采用哈希技术对原始值域$\mathcal{D}$进行本地哈希变换, 使其映射到一个较小的值域空间$\mathcal{G}$($\mathcal{H}$: $\mathcal{D}$→$\mathcal{G}$)中, 设g=|$\mathcal{G}$|. 然后基于$\mathcal{G}$, 利用公式(5)对哈希值进行本地扰动. 基于此思路, 提出了一种混洗随机应答机制SRR. 不同于LDP下的本地扰动方法, SRR通过对GRR方法的输出概率线性分解成为两种概率的组合, 以部分噪音值融合部分真实值来输出最终的扰动结果. SRR算法输出某个消息的概率如公式(7)所示:

$ {\forall _{y \in \mathcal{G}}}\Pr [SRR(H(v)) = y] = (1 - \gamma ){I_{\{ H(v) = y\} }} + \gamma \Pr [Uniform(\mathcal{G}) = y] $

(7)

其中, I_{H(v)=y}为标识函数, 若H(v)=y, 则I_{H(v)=y}=1, 并且H(v)以(1−γ)的概率扰动成y.

由文献[3]可知, $ \gamma = \sum {\min \Pr [SRR(H(v)) = y]} = g/g + {{\text{e}}^\varepsilon } - 1, $ Pr[Uniform($\mathcal{G}$)=y]=1/g.

SRR算法的具体实现细节如算法2所示.

算法2. SRR.

输入: 用户的数据v且v∈$\mathcal{D}$, 隐私预算ε, 哈希函数的值域$\mathcal{G}$, |$\mathcal{G}$|=g, γ;

输出: M.

1. M←∅;

2. Uniformly pick a hash function H from $\mathcal{H}$, and obtain 〈H, H(v)〉 (H∈$\mathcal{H}$, H(v)∈$\mathcal{G}$); //利用哈希函数H对用户数据v进行编码

3. Perturb 〈H, H(v)〉 into 〈H, y〉 as $ \langle H,y\rangle = \left\{ {\begin{array}{*{20}{l}} {\langle H,H(v)\rangle ,{\text{ w}}{\text{.p}}{\text{. }}1 - \gamma \left( {\frac{{g - 1}}{g}} \right)} \\ {Uniform(\mathcal{G}),{\text{ w}}{\text{.p}}{\text{. }}\gamma \left( {\frac{{g - 1}}{g}} \right)} \end{array}} \right.; $ //对数据v所对应的哈希地址H(v)进行本地扰动, “w.p”表示“以概率”

4. return M=M∪〈H, y〉.

SRR算法首先在哈希家族$\mathcal{H}$中随机选择一个哈希函数H对用户的数据v进行本地哈希编码(步骤2), 获得〈H, H(v)〉后, 对其进行混洗随机扰动之后获得〈H, y〉, 其中, 以概率1−γ(g−1/g)扰动成〈H, H(v)〉, 以概率γ(g−1/g)扰动成值域$\mathcal{G}$中的任意值(步骤3).

由LDP中的随机应答机制可知: 每个用户使用的应答机制越具有随机性, 就越能够保护自己的数据. 而在SDP模型中, 混洗方把收集的所有消息随机排列成一个向量M, 且M中蕴含着部分真实值H(v_i). 因此, SRR比起LDP的随机应答机制向v_i添加的随机噪音相对较少. 然而, SRR与LDP下的随机扰动机制隐私保护程度相同. 由SRR算法的步骤3可知: 在整个消息向量M中, 一部分是以概率1−γ(g−1/g)生成的真实值, 另一部分是以概率γ(g−1/g)生成的随机值, 该算法正是利用部分随机值掩盖了另一部分真实值.

当混洗方$\mathcal{S}$获得M后, 需要对其中的真实值与随机值进行混洗排列. 文献[1−4]大都采用费雪耶兹(Fisher-Yates)传统随机排列算法来混洗M中的消息, 该算法一次随机排列的时间复杂度为O(n²). 尽管费雪耶兹随机排列算法的每种排列结果是等概率的(1/n!), 但当n非常大时, 相应的时间复杂度较高. 而如何在保证混洗效率的前提下设计高效的混洗算法至关重要. 本文基于堆排列技术设计了一种高效的消息向量混洗算法MRS实现{〈H₁, y₁〉, 〈H₂, y₂〉, …, 〈H_n, y_n〉}→{〈H₁, y₁〉, 〈H₂, y₂〉, …, 〈H_n, y_n〉}的映射关系. 该算法的具体细节如算法3所示.

算法3. MRS.

输入: 混洗方$\mathcal{S}$收集到的消息向量M={〈H₁, y₁〉, 〈H₂, y₂〉, …, 〈H_n, y_n〉};

输出: 消息排列结果σ.

1.   $\mathcal{Y}$′←∅; //$\mathcal{Y}$′表示全排列集合

2.   Create a integer array B of size n to control the iteration; //数组B用来控制迭代次数

3.   B[1]=1, B[2]=2, …, B[i]=i…;

4.   i=1; //i用来控制M的索引

5.   while i < n do

6.     B[i]←B[i]−1;

7.     if i is odd then

8.       j←B[i];

9.     else

10.       j←0;

11.     swapmessages(〈H_j, y_j〉, 〈H_i, y_i〉); //交换第i与第j个消息位置

12.     add (〈H_j, y_j〉, 〈H_i, y_i〉) to $\mathcal{Y}$′;

13.     i=1;

14.     while B[i]==0 do

15.       B[i]←i;

16.       i←i+1;

17.     end while

18.end while

19. Uniformly pick a permutation σ from $\mathcal{Y}$′;

20. return σ.

在MRS算法中, 混洗方收集到消息向量M后, 对M进行均匀排列, 随机均匀地生成一个消息向量σ. 具体思路是:

● 当循环遍历第i个元素时, 如果i是奇数, 则交换第1个和第i个元素; 如果i是偶数, 则交换第j(j∈ B[i])个元素和第i个元素. 其中, 数组B[i]用来控制迭代次数(步骤5−步骤11);

● 然后, 将交换后的前i−1个元素的排列附加到当前最后一个元素(第i个元素)(步骤14−步骤17).

MRS算法生成所有全排列的时间复杂度为O(n²logn), 而该算法随机输出一个排列结果的时间复杂度为O(nlogn).

3.2.1 HP-SDP算法的隐私性分析

给定分布式数据集D={v₁, v₂, …, v_n}. 经过SRR扰动与MRS混洗后, 获得σ={〈H₁, y₁〉, 〈H₂, y₂〉, …, 〈H_n, y_n〉}. 为了证明方便, 把SRR扰动操作与MRS混洗操作记作$\mathcal{S}$ο$\mathcal{R}$, 令$\mathcal{M}$(D)=$\mathcal{S}$ο$\mathcal{R}$(D). 根据HP-SDP算法分析可知, 所有用户发送的消息经过$\mathcal{S}$ο$\mathcal{R}$操作后能够满足(ε_c, δ)-CDP, 其中, ε_c表示中心化隐私预算.

定理1. $\mathcal{M}$(D)满足(ε_c, δ)-中心化差分隐私, 其中, $ {\varepsilon _c} \leqslant \sqrt {\frac{{14\ln (2/\delta )({{\text{e}}^\varepsilon } + g - 1)}}{{n - 1}}} . $

证明: 给定D及其近邻D′. $\mathcal{Y}$′表示$\mathcal{M}$的输出值域, 即由〈H_i, y_i〉组成, 其中, H_i表示$\mathcal{H}$中的第i个哈希函数, y_i=GRR(H_i(v_i)). σ表示$\mathcal{Y}$′中任意一种随机排列结果.

若要证明$\mathcal{M}$满足(ε_c, δ)-CDP, 则需要证明$ {\Pr _{y \sim \mathcal{M}(D)}}\left[ {\frac{{\Pr [\mathcal{M}(D) = y]}}{{\Pr [\mathcal{M}(D') = y]}} \geqslant {{\text{e}}^{{\varepsilon _c}}}} \right] \leqslant \delta $即可.

假设D与D′只在第n个用户的值不同, 即$ {v_n} \ne {v'_n}, $第n个用户为目标攻击用户. 假设H(v_n)被哈希到值域[g]中的第1个位置, $ H({v'_n}) $被哈希到值域[g]中的第2个位置, 则可以分两种情况证明上述不等式.

● 情况1

如果第n个用户以概率γ(g−1/g)发送随机值, 则Pr[$\mathcal{M}$(D)=y]=Pr[$\mathcal{M}$(D′)=y]. 根据差分隐私定义可知, 该情况满足(ε_c, δ)-CDP;

● 情况2

如果第n个用户以概率1−γ(g−1/g)发送真实值, 则需要$\mathcal{M}$方法对其进行保护. 该情况证明如下.

结合MRS算法可知, n个用户的消息随机排列后存在n!种σ, 则对D扰动和混洗后的概率如下所示:

$ \begin{array}{l} \Pr [\mathcal{M}(D) = y] = \sum\limits_\sigma {\Pr [\sigma ]} \Pr [\mathcal{M}(D) = y|\sigma ] \hfill \\ {\text{ }} = \sum\limits_\sigma {\frac{1}{{n!}}} \Pr [\mathcal{M}(D) = y|\sigma ] \hfill \\ {\text{ }} = \sum\limits_\sigma {\frac{1}{{n!}}} \left( {\prod\limits_{i \in [n - 1]} {\Pr [{H_{\sigma (i)}}]{I_{\{ {H_{\sigma (i)}}({v_i}) = {y_i}\} }}} \times \prod\limits_{i \in [n - 1]} {\Pr [{H_{\sigma (i)}}]\frac{1}{g}} \times \Pr [{H_{\sigma (n)}}]{I_{\{ {H_{\sigma (n)}}({v_n}) = {y_{\sigma (n)}}\} }}} \right) \hfill \\ {\text{ }} = \sum\limits_\sigma {\frac{1}{{n!}}} \left( {\prod\limits_{i \in [n - 1]} {\frac{1}{h}{I_{\{ {H_{\sigma (i)}}({v_i}) = {y_i}\} }}} \times \prod\limits_{i \in [n - 1]} {\frac{1}{h}\frac{1}{g}} \times \frac{1}{h}{I_{\{ {H_{\sigma (n)}}({v_n}) = {y_{\sigma (n)}}\} }}} \right) \hfill \\ \end{array} $

(8)

其中,

● Pr[$\mathcal{M}$(D)=y]表示以随机排列σ为条件的$\mathcal{M}$输出概率;

● h表示$\mathcal{H}$中哈希函数的个数;

● Pr[H_σ(i)]表示随机排列的第i个位置所对应的哈希函数的抽样概率;

● I为标识函数, 当H_σ(i)(v_i)=y_i时, 该值为1; 否则为0.

同理, 对D′有以下等式成立:

$ \begin{array}{l} \Pr [\mathcal{M}(D') = y] = \sum\limits_\sigma {\Pr [\sigma ]} \Pr [\mathcal{M}(D') = y|\sigma ] \hfill \\ {\text{ }} = \sum\limits_\sigma {\frac{1}{{n!}}} \Pr [\mathcal{M}(D') = y|\sigma ] \hfill \\ {\text{ }} = \sum\limits_\sigma {\frac{1}{{n!}}} \left( {\prod\limits_{i \in [n - 1]} {\Pr [{H_{\sigma (i)}}]{I_{\{ {H_{\sigma (n)}}({v_i}) = {y_i}\} }}} \times \prod\limits_{i \in [n - 1]} {\Pr [{H_{\sigma (i)}}]\frac{1}{g}} \times \Pr [{H_{\sigma (n)}}]{I_{\{ {H_{\sigma (n)}}({{v'}_n}) = {y_{\sigma (n)}}\} }}} \right) \hfill \\ {\text{ }} = \sum\limits_\sigma {\frac{1}{{n!}}} \left( {\prod\limits_{i \in [n - 1]} {\frac{1}{h}{I_{\{ {H_{\sigma (n)}}({v_i}) = {y_i}\} }}} \times \prod\limits_{i \in [n - 1]} {\frac{1}{h}\frac{1}{g}} \times \frac{1}{h}{I_{\{ {H_{\sigma (n)}}({{v'}_n}) = {y_{\sigma (n)}}\} }}} \right) \hfill \\ \end{array} $

(9)

则根据公式(8)与公式(9)可知:

$ \frac{{\Pr [\mathcal{M}(D) = y]}}{{\Pr [\mathcal{M}(D') = y]}} = \frac{{\sum\limits_\sigma {\frac{1}{{n!}}} \left( {\prod\limits_{i \in [n - 1]} {\frac{1}{h}{I_{\{ {H_{\sigma (i)}}({v_i}) = {y_i}\} }}} \times \prod\limits_{i \in [n - 1]} {\frac{1}{h}\frac{1}{g}} \times \frac{1}{h}{I_{\{ {H_{\sigma (i)}}({v_n}) = {y_{\sigma (n)}}\} }}} \right)}}{{\sum\limits_\sigma {\frac{1}{{n!}}} \left( {\prod\limits_{i \in [n - 1]} {\frac{1}{h}{I_{\{ {H_{\sigma (i)}}({v_i}) = {y_i}\} }}} \times \prod\limits_{i \in [n - 1]} {\frac{1}{h}\frac{1}{g}} \times \frac{1}{h}{I_{\{ {H_{\sigma (i)}}({{v'}_n}) = {y_{\sigma (n)}}\} }}} \right)}} = \frac{{\sum\limits_\sigma {{I_{\{ {H_{\sigma (n)}}({v_n}) = {y_{\sigma (n)}}\} }}} }}{{\sum\limits_\sigma {{I_{\{ {H_{\sigma (n)}}({{v'}_n}) = {y_{\sigma (n)}}\} }}} }} = \frac{{{n_1}}}{{{n_2}}} $

(10)

其中,

● n₁表示哈希值域[g]中第1个位置的用户计数, 该计数符合二项分布N₁~B(n−1, γ/g)+1;

● n₂表示哈希值域[g]中第2个位置的用户计数, 该计数符合二项分布N₂~B(n−1, γ/g),

则$ {\Pr _{y \sim \mathcal{M}(D)}}\left[ {\frac{{\Pr [\mathcal{M}(D) = y]}}{{\Pr [\mathcal{M}(D') = y]}} \geqslant {{\text{e}}^{{\varepsilon _c}}}} \right] = \Pr \left[ {\frac{{{N_1}}}{{{N_2}}} \geqslant {{\text{e}}^{{\varepsilon _c}}}} \right]. $

设μ=E[N₂]=γ(n−1)/g. $ {N_1}/{N_2} \geqslant {{\text{e}}^{{\varepsilon _c}}} $蕴含着$ {N_1} \geqslant \mu {{\text{e}}^{{\varepsilon _c}/2}},{\text{ }}{N_2} \leqslant \mu {{\text{e}}^{ - {\varepsilon _c}/2}}, $则根据布尔不等式可知:

$ \begin{array}{l} \Pr \left[ {\frac{{{N_1}}}{{{N_2}}} \geqslant {{\text{e}}^{{\varepsilon _c}}}} \right] = \Pr [{N_1} \geqslant \mu {{\text{e}}^{{\varepsilon _c}/2}} \cup {N_2} \leqslant \mu {{\text{e}}^{ - {\varepsilon _c}/2}}] \hfill \\ {\text{ }} = \Pr [{N_1} \geqslant \mu {{\text{e}}^{{\varepsilon _c}/2}}] + \Pr [{N_2} \leqslant \mu {{\text{e}}^{ - {\varepsilon _c}/2}}] - \Pr [({N_1} \geqslant \mu {{\text{e}}^{{\varepsilon _c}/2}}) \cap ({N_2} \leqslant \mu {{\text{e}}^{ - {\varepsilon _c}/2}})] \hfill \\ {\text{ }} \leqslant \Pr [{N_1} \geqslant \mu {{\text{e}}^{{\varepsilon _c}/2}}] + \Pr [{N_2} \leqslant \mu {{\text{e}}^{ - {\varepsilon _c}/2}}] \hfill \\ {\text{ }} = \Pr [{N_2} + 1 \geqslant \mu {{\text{e}}^{{\varepsilon _c}/2}}] + \Pr [{N_2} \leqslant \mu {{\text{e}}^{ - {\varepsilon _c}/2}}] \hfill \\ {\text{ }} = \Pr \left[ {{N_2} - \mu \geqslant \mu \left( {{{\text{e}}^{{\varepsilon _c}/2}} - 1 - \frac{1}{\mu }} \right)} \right] + \Pr [{N_2} - \mu \leqslant \mu ({{\text{e}}^{ - {\varepsilon _c}/2}} - 1)] \hfill \\ \end{array} $

(11)

根据切诺夫不等式以及文献[3]中的切诺夫边界理论可知:

$ \begin{array}{l} \Pr \left[ {{N_2} - \mu \geqslant \mu \left( {{{\text{e}}^{{\varepsilon _c}/2}} - 1 - \frac{1}{\mu }} \right)} \right] \leqslant \exp \left( { - \frac{\mu }{3}{{\left( {{{\text{e}}^{{\varepsilon _c}/2}} - 1 - \frac{1}{\mu }} \right)}^2}} \right), \\ \Pr [{N_2} - \mu \leqslant \mu ({{\text{e}}^{ - {\varepsilon _c}/2}} - 1)] \leqslant \exp \left( { - \frac{\mu }{2}{{({{\text{e}}^{ - {\varepsilon _c}/2}} - 1)}^2}} \right), \\ \end{array} $

则公式(11)可表示为

$ \Pr \left[ {\frac{{{N_1}}}{{{N_2}}} \geqslant {{\text{e}}^{{\varepsilon _c}}}} \right] \leqslant \exp \left( { - \frac{\mu }{3}{{\left( {{{\text{e}}^{{\varepsilon _c}/2}} - 1 - \frac{1}{\mu }} \right)}^2}} \right) + \exp \left( { - \frac{\mu }{2}{{(1 - {{\text{e}}^{ - {\varepsilon _c}/2}})}^2}} \right) $

(12)

为了使得$ \Pr \left[ {\frac{{{N_1}}}{{{N_2}}} \geqslant {{\text{e}}^{{\varepsilon _c}}}} \right] \leqslant \delta $成立, 当ε_c≤1时, 公式(12)右侧的两项可表示为

$ \exp \left( { - \frac{\mu }{2}{{(1 - {{\text{e}}^{ - {\varepsilon _c}/2}})}^2}} \right) \leqslant \delta /2 $

(13)

$ \exp \left( { - \frac{\mu }{3}{{\left( {{{\text{e}}^{{\varepsilon _c}/2}} - 1 - \frac{1}{\mu }} \right)}^2}} \right) \leqslant \delta /2 $

(14)

结合公式(13)、公式(14), 根据文献[3]可知$ \mu = \frac{{\gamma (n - 1)}}{g} \geqslant \frac{{14\ln (2/\delta )}}{{\varepsilon _c^2}}, $进而可知$ {\varepsilon _c} \leqslant \sqrt {\frac{{14\ln (2/\delta )({{\text{e}}^\varepsilon } + g - 1)}}{{n - 1}}} . $因此, $\mathcal{M}$满足$ \left( {\sqrt {\frac{{14\ln (2/\delta )({{\text{e}}^\varepsilon } + g - 1)}}{{n - 1}}} ,\delta } \right) $-中心化差分隐私.

3.2.2 HP-SDP算法的可用性分析

HP-SDP算法的可用性主要从直方图每个桶频率的无偏性、每个桶频率产生的方差以及每个桶频率产生的最大偏差来度量. 每个用户的类别数据经过SRR扰动与MRS混洗后会与真实值存在偏差. 收集者$\mathcal{A}$若不对每个桶的频率进行修正, 则发布结果会存在较大偏差.

定理2. 假设f_v与$ {\tilde f_v} $分别表示桶(或类别数据)v的真实频率与估计频率, 则$ E[{\tilde f_v}] = {f_v} $成立.

证明: 假设v被哈希且扰动成y的概率为$ \Pr [y] = {f_v}\left( {1 - \gamma \frac{{g - 1}}{g}} \right) + (1 - {f_v})\gamma \frac{{g - 1}}{g}, $假设v被哈希且扰动成非y(即y′)的概率为$ \Pr [y'] = {f_v}\gamma \frac{{g - 1}}{g} + (1 - {f_v})\left( {1 - \gamma \frac{{g - 1}}{g}} \right), $结合Pr[y]与Pr[y′]构造相应的极大似然函数如公式(15)所示:

$ \begin{array}{l} L({f_v}) = {[\Pr [y]]^{{m_1}}} \times {[\Pr [y']]^{n - {m_1}}} \hfill \\ {\text{ }} = {\left[ {{f_v}\left( {1 - \gamma \frac{{g - 1}}{g}} \right) + (1 - {f_v})\gamma \frac{{g - 1}}{g}} \right]^{{m_1}}} \times {\left[ {{f_v}\gamma \frac{{g - 1}}{g} + (1 - {f_v})\left( {1 - \gamma \frac{{g - 1}}{g}} \right)} \right]^{n - {m_1}}} \hfill \\ \end{array} $

(15)

其中, m₁表示相应v值被哈希且扰动成y的用户个数, g表示哈希函数的值域大小.

对公式(15)两边取对数, 可获得公式(16):

$ \ln (L({f_v})) = {m_1}\ln \left[ {{f_v}\left( {1 - \gamma \frac{{g - 1}}{g}} \right) + (1 - {f_v})\gamma \frac{{g - 1}}{g}} \right] + (n - {m_1})\ln \left[ {{f_v}\gamma \frac{{g - 1}}{g} + (1 - {f_v})\left( {1 - \gamma \frac{{g - 1}}{g}} \right)} \right] $

(16)

然后对公式(16)两边的f_v求偏导后, 可获得公式(17):

$ \frac{{\partial \ln (L({f_v}))}}{{\partial {f_v}}} = \frac{{{m_1}\left( {1 - \gamma \frac{{g - 1}}{g} - \gamma \frac{{g - 1}}{g}} \right)}}{{{f_v}\left( {1 - \gamma \frac{{g - 1}}{g}} \right) + (1 - {f_v})\gamma \frac{{g - 1}}{g}}} + \frac{{(n - {m_1})\left( {\gamma \frac{{g - 1}}{g} - 1 + \gamma \frac{{g - 1}}{g}} \right)}}{{{f_v}\gamma \frac{{g - 1}}{g} + (1 - {f_v})\left( {1 - \gamma \frac{{g - 1}}{g}} \right)}} $

(17)

令公式(17)=0, 则可获得公式(18):

$ {f_v}\left( {n - 2n\gamma \frac{{g - 1}}{g}} \right) = {m_1} - n\gamma \frac{{g - 1}}{g} $

(18)

由于无法获知桶v的真实频率f_v, 则需要根据公式(18)来表示出f_v的估计量, 如公式(19)所示:

$ \begin{array}{l} {{\tilde f}_v} = \frac{1}{n} \cdot \frac{{{m_1} - n\gamma \frac{{g - 1}}{g}}}{{1 - 2\gamma \frac{{g - 1}}{g}}} \hfill \\ {\text{ }} = \frac{1}{n} \cdot \frac{{\sum\limits_{i = 1}^n {{I_{\{ {H_i}(v) = {y_i}\} }}} - n\gamma \frac{{g - 1}}{g}}}{{1 - 2\gamma \frac{{g - 1}}{g}}} \hfill \\ \end{array} $

(19)

接下来结合公式(19)证明$ E[{\tilde f_v}] = {f_v} $成立:

$ \begin{array}{l} E[{{\tilde f}_v}] = E\left( {\frac{1}{n} \cdot \frac{{\sum\limits_{i = 1}^n {{I_{\{ {H_i}(v) = {y_i}\} }}} - n\gamma \frac{{g - 1}}{g}}}{{1 - 2\gamma \frac{{g - 1}}{g}}}} \right) = \frac{1}{n} \cdot \frac{{E\left( {\sum\limits_{i = 1}^n {{I_{\{ {H_i}(v) = {y_i}\} }}} } \right) - n\gamma \frac{{g - 1}}{g}}}{{1 - 2\gamma \frac{{g - 1}}{g}}} \hfill \\ {\text{ }} = \frac{1}{n} \cdot \frac{{\left( {n{f_v}\left( {1 - \gamma \frac{{g - 1}}{g}} \right) + (n - n{f_v})\gamma \frac{{g - 1}}{g}} \right) - n\gamma \frac{{g - 1}}{g}}}{{1 - 2\gamma \frac{{g - 1}}{g}}} \hfill \\ {\text{ }} = \frac{1}{n} \cdot \frac{{n{f_v} - n{f_v}\gamma \frac{{g - 1}}{g} - n{f_v}\gamma \frac{{g - 1}}{g}}}{{1 - 2\gamma \frac{{g - 1}}{g}}} = \frac{1}{n} \cdot n{f_v} = {f_v}. \hfill \\ \end{array} $

证明完毕.

由于SRR与MRS算法的本地扰动与混洗, 在估计$ {\tilde f_v} $的无偏性时会产生相应的误差, 而这种误差是衡量HP-SDP算法可用性的主要标准之一. 本文利用方差$ Var({\tilde f_v}) $来度量HP-SDP算法产生的误差.

定理3. 设f_v与$ {\tilde f_v} $分别表示桶v的真实频率与估计频率, 估计$ {\tilde f_v} $产生方差为$ Var[{\tilde f_v}] = \frac{{\gamma \frac{{g - 1}}{g} - {{\left( {\gamma \frac{{g - 1}}{g}} \right)}^2}}}{{n{{\left( {1 - 2\gamma \frac{{g - 1}}{g}} \right)}^2}}}. $

证明: 根据公式(17)以及方差公式可知:

$ \begin{array}{l} Var[{{\tilde f}_v}] = Var\left[ {\frac{1}{n} \cdot \frac{{\sum\limits_{i = 1}^n {{I_{\{ {H_i}(v) = {y_i}\} }}} - n\gamma \frac{{g - 1}}{g}}}{{1 - 2\gamma \frac{{g - 1}}{g}}}} \right] \hfill \\ {\text{ }} = \frac{1}{{{n^2}}} \cdot \frac{{Var\left( {\sum\limits_{i = 1}^n {{I_{\{ {H_i}(v) = {y_i}\} }}} - n\gamma \frac{{g - 1}}{g}} \right)}}{{{{\left( {1 - 2\gamma \frac{{g - 1}}{g}} \right)}^2}}} \hfill \\ {\text{ }} = \frac{1}{{{n^2}{{\left( {1 - 2\gamma \frac{{g - 1}}{g}} \right)}^2}}} \cdot \left[ {n{f_v}\left( {1 - \gamma \frac{{g - 1}}{g}} \right)\gamma \frac{{g - 1}}{g} + (n - n{f_v})\gamma \frac{{g - 1}}{g}\left( {1 - \gamma \frac{{g - 1}}{g}} \right)} \right] \hfill \\ {\text{ }} = \frac{1}{{{n^2}{{\left( {1 - 2\gamma \frac{{g - 1}}{g}} \right)}^2}}} \cdot \left[ {n\gamma \frac{{g - 1}}{g} - n{{\left( {\gamma \frac{{g - 1}}{g}} \right)}^2}} \right] \hfill \\ {\text{ }} = \frac{{\gamma \frac{{g - 1}}{g} - {{\left( {\gamma \frac{{g - 1}}{g}} \right)}^2}}}{{n{{\left( {1 - 2\gamma \frac{{g - 1}}{g}} \right)}^2}}}. \hfill \\ \end{array} $

根据定理2与定理3以及公式(6), 可以获得估计$ {\tilde f_v} $产生的均方差MSE, 如定理4所示.

定理4. 估计$ {\tilde f_v} $所产生的均方差MSE为$ Var({\tilde f_v}). $

证明: 根据公式(6)以及定理2和定理3, $ {\tilde f_v} $产生的均方差MSE为

$ MSE = \frac{1}{d}\sum\limits_{v \in \mathcal{D}} {E{{({f_v} - {{\tilde f}_v})}^2}} = \frac{1}{d}\sum\limits_{v \in \mathcal{D}} {(Var[{{\tilde f}_v}] + {{[E[{{\tilde f}_v}] - {f_v}]}^2})} = \frac{1}{d}\sum\limits_{v \in \mathcal{D}} {Var[{{\tilde f}_v}]} = Var[{\tilde f_v}]. $

根据定理2与定理3可以推理出每个桶中频率的无偏性与方差, 而如何度量f_v与$ {\tilde f_v} $之间的最大偏差是一个挑战性的问题. 接下来由定理5给出说明.

定理5. 给定f_v与$ {\tilde f_v}, $则$\mathop {\max }\limits_{v \in \mathcal{D}} |{\tilde f_v} - {f_v}| = {\text{O}}\left( {\frac{{\sqrt {\ln (1/\beta )} }}{{\varepsilon \sqrt n }}} \right)$至少以概率1−β成立, 其中, n为用户个数.

证明: 为了证明方便, 给定n中任意一个用户u_i所拥有的值为v. 经过本地哈希编码后, 若其对应的编码满足H_i(v)=y_i, 则c(v)=1. 经过本地SRR扰动之后, v的计数为c′(v). 如SRR算法中的第3行所示: 当扰动概率为1−γ(g−1/g)时, c′(v)=1. 因此, 可知c′(v)−c(v)为一个随机变量, 则以下针对c′(v)−c(v)的方差推理成立:

$ Var[c'(v) - c(v)] = Var[c'(v)] = E[{(c'(v))^2}] - E{[c'(v)]^2} = E[{(c'(v))^2}] - {(c(v))^2} \leqslant E[{(c'(v))^2}] = 1 \cdot {\left( {1 - \gamma \left( {\frac{{g - 1}}{g}} \right)} \right)^2} = O(1/{\varepsilon ^2}). $

c(v)与c′(v)的取值范围为{1, 0}, 则随机变量c′(v)−c(v)的取值范围为{−1, 0, +1}, 于是可知:

$ \left| {{c^\prime }(v) - c(v)} \right| \le {{\rm{e}}^s} - g + 1/{{\rm{e}}^s} + g - 1 < t. $

根据伯恩斯坦不等式可知如下不等式成立:

$ \begin{array}{l} \Pr [|f'(v) - f(v)| \geqslant nt] \leqslant 2 \times \exp \left( { - \frac{{{{(nt)}^2}}}{{2 \cdot \sum\nolimits_i^n {Var[{{c'}_i}(v) - {c_i}(v)]} + \frac{{2nt}}{3}\left( {\frac{{{{\text{e}}^\varepsilon } - g + 1}}{{{{\text{e}}^\varepsilon } + g - 1}}} \right)}}} \right) \hfill \\ {\text{ }} \leqslant 2 \times \exp \left( { - \frac{{n{t^2}}}{{\frac{2}{n} \cdot \sum\nolimits_i^n {Var[{{c'}_i}(v) - {c_i}(v)]} + \frac{{2t}}{3}\left( {\frac{{{{\text{e}}^\varepsilon } - g + 1}}{{{{\text{e}}^\varepsilon } + g - 1}}} \right)}}} \right) \hfill \\ {\text{ }} = 2 \times \exp \left( { - \frac{{n{t^2}}}{{{\text{O}}(1/{\varepsilon ^2}) + t \cdot {\text{O}}(1/\varepsilon )}}} \right), \hfill \\ \end{array} $

则存在$t = \sqrt {\ln (1/\beta )} /\varepsilon \sqrt n ,$使得|f′(v)−f(v)| < t以概率1−β成立.

定理2−定理5分别从无偏性、方差、均方差与最大偏差估计了HP-SDP算法的可用性. 然而, 由于SRR本地扰动的原因, 可能会导致直方图的一些桶的频率出现负值, 或者所有桶的频率之和不等于1. 由公式(19)可知: 所有桶的频率应位于区间[0, 1], 并且所有桶的频率之和为1. 基于此, 需要对所有桶的估计值进行后置处理, 而后置处理的结果需要满足一致性约束条件.

定义4(一致性约束). 如若HP-SDP算法的输出结果$ \bar F $满足: (1) $ \bar F $中的任意值属于[0, 1]; (2) $ \bar F $中的所有值之和等于1, 则HP-SDP算法满足一致性约束条件.

因此, 如何在一致性约束条件下求出$ \bar F, $是后置处理的关键问题所在. 本文把该问题转换为约束条件下的二次规划问题^[9], 其形式化表达如公式(20)所示:

$ \left\{ {\begin{array}{*{20}{l}} {{\text{minimize}}:\sum\nolimits_{v \in \mathcal{D}} {{{({{\bar f}_v} - {{\tilde f}_v})}^2}} } \\ {{\text{subject to}}:\sum\nolimits_{v \in \mathcal{D}} {{{\bar f}_v}} = 1,{\text{ }}\forall v:{{\bar f}_v} \geqslant 0} \end{array}} \right. $

(20)

其中, $ \forall v:{\tilde f_v} \in \tilde F,{\text{ }}{\bar f_v} \in \bar F. $

公式(20)即是POP后置处理算法的核心技术. 根据文献[21]中的KKT条件, 可以对公式(20)中的目标函数进行松弛处理, 如公式(21)所示:

$ \left\{ {\begin{array}{*{20}{l}} {{\text{minimize}}:\sum\nolimits_{v \in \mathcal{D}} {{{({{\bar f}_v} - {{\tilde f}_v})}^2}} + {a_1} + {a_2}} \\ {{\text{where }}\sum\nolimits_{v \in \mathcal{D}} {{{\bar f}_v}} = 1,{\text{ }}\forall v:0 \leqslant {{\bar f}_v} \leqslant 1} \\ {{a_1} = b \cdot \sum\nolimits_{v \in \mathcal{D}} {{{\bar f}_v}} } \\ {a = \sum\nolimits_{v \in \mathcal{D}} {{\lambda _v} \cdot {{\bar f}_v}} ,{\text{ }}\forall v:{\lambda _v} \cdot {{\bar f}_v} = 0} \end{array}} \right. $

(21)

根据文献[21]可知: 如果对v的值域$\mathcal{D}$进行划分$\mathcal{D}$₀∪$\mathcal{D}$₁, 并且满足∀v∈$\mathcal{D}$₀时, $ {\bar f_v} = 0; $以及∀v∈$\mathcal{D}$₁时, $ {\bar f_v} > 0 \wedge {\lambda _v} = 0. $进而可知$\mathcal{D}$₁中的$ {\bar f_v} $可行解为$ {\bar f_v} = {\tilde f_v} - \frac{1}{{|{\mathcal{D}_1}|}}(\sum\nolimits_{v \in {\mathcal{D}_1}} {{{\tilde f}_v}} - 1). $因此, HP-SDP算法中的POP后置处理的结果如公式(22)所示:

$ {\bar f_v} = \left\{ {\begin{array}{*{20}{l}} {{{\tilde f}_v} - \frac{1}{{|{\mathcal{D}_1}|}}(\sum\nolimits_{v \in {\mathcal{D}_1}} {{{\tilde f}_v}} - 1),{\text{ }}\forall v \in {\mathcal{D}_1}} \\ {0,{\text{ }}\forall v \in {\mathcal{D}_0}} \end{array}} \right. $

(22)

由文献[22]可知, 后置处理的结果同样满足(ε_c, δ)-中心化差分隐私.

4 实验结果与分析

实验平台是4核Intel CPU(4 GHz)、8 G内存、Win 7系统, 代码采用Python实现. 实验采用Normal数据集、Zipf数据集、IPUMS数据集以及Kosarak数据集. 其中,

● Normal与Zipf是两个合成数据集, 数据量为600 000, 值域为600;

● IPUMS是1940年的美国人口普查数据集, 按照1%的比例进行采样, 使用其中的城市属性, 数据中包含602 325个用户和915个城市;

● Kosarak是在匈牙利网站上点击流的数据集, 包含100万个用户, 42 178种不同的值, 对于每条数据流, 随机选取一项作为用户的数据.

4种数据集的具体信息见表 1.

结合上述数据集, 采用均方差(mean square error, MSE)度量SH、MURS、AUE、mixDUMP、pureDUMP、HP-SM、HP-SDP、Laplace算法^[22]的误差. 其中, HP-SM是HP-SDP算法去掉后置处理操作之后的算法. 隐私参数ε的选取分别为0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.9、1.0.

4.1 基于Normal和Zipf数据集的8种算法的MSE比较

图 3和图 4描述了上述8种算法在Normal和Zipf数据集上MSE值的比较结果. 由实验结果可以发现: 当ε从0.1变化到1.0时, 所有的MSE均呈下降趋势. 其原因是噪音的多少与ε成反比, ε越大, MSE越小. HP-SM和HP-SDP算法优于除Laplace算法之外的6种算法, 而HP-SDP算法的MSE接近Laplace算法的MSE. 当δ=10⁻⁶, ε从0.1变化到0.5时, SH算法的MSE在Normal与Zipf数据集上比HP-SM算法高出5个与6个数量级, 比HP-SDP算法的MSE高出6个与7个数量级. mixDUMP、pureDUMP与SH算法均采用GRR机制进行本地扰动, 然而该机制容易受到值域大小的影响, 值域越大, 精度越低. 因此, 这3种算法的精度低于HP- SDP算法. 当δ从10⁻⁶变化到10⁻⁹, ε从0.1变化到1.0时, MURS算法采用本地哈希技术所取得的精度接近HP- SM, 但却低于HP-SDP算法. 其主要原因是HP-SDP算法利用了快速混洗与后置处理技术.

4.2 基于IPUMS与Kosarak数据集的8种算法的MSE比较

图 5与图 6分别描述了上述8种算法在IPUMS与Kosarak真实数据集上的MSE变化情况. 从图 5与图 6的实验结果可以看出: 当δ从10⁻⁶变化到10⁻⁹, ε从0.1变化到1.0时, SH算法的MSE在IPUMS与Kosarak数据集上比HP-SM算法高出5个数量级, 而HP-SDP算法的精度将近是SH算法的1.7倍. 相比于合成数据集, HP-SM算法与HP-SDP算法的精度优势在Kosarak数据集上更加明显. 在ε越来越大时, HP-SDP算法的精度更接近Laplace算法. 当δ=10⁻⁶, 且ε从0.1变化到0.5时, mixDUMP算法与SH算法的MSE比HP-SDP算法高出3个与6个数量级. HP-SDP算法取得的精度是MURS算法的近3倍. 此外, 由于AUE自身不满足本地化差分隐私, 其MSE一直高于HP-SM算法与HP-SDP算法. 上述结果的主要原因是: HP-SDP算法采用了基于二次规划技术的后置处理方法, 进一步提升了直方图发布的精度.

5 结束语

本文针对混洗差分隐私行下直方图的发布问题, 结合中心化/本地化差分隐私存在的不足, 提出了一种集成本地哈希编码、快速混洗以及后置处理的直方图发布算法HP-SDP, 该算法利用线性分解的形式重构了本地哈希扰动机制, 利用类似于堆排序技术实现了随机混洗机制, 最后利用二次规划技术实现了后置处理机制. 通过4种数据集与现有7种方法进行均方误差对比分析, 其结果表明, HP-SDP算法的精度最接近中心化差分隐私下的拉普拉斯机制的精度. 这也是混洗差分隐私框架的初衷. 今后的工作考虑如下两个方面: (1) 如何在多消息单一混洗框架下实现直方图发布; (2) 如何在多消息多混洗框架下实现直方图发布.