基于OLH和虛擬數據的SDP直方圖發(fā)布算法

摘 要：中心化差分隱私和本地化差分隱私下的直方圖發(fā)布技術已得到廣泛研究。為解決用戶隱私需求和發(fā)布誤差之間難以平衡的問題，在混洗差分隱私模型下提出一種直方圖發(fā)布算法OD-HP（histogram publishing based on optimized local hash and dummy points）。該算法采用優(yōu)化本地哈希擾動機制OLH對用戶數據進行編碼和擾動，解決了數據值域過大導致誤差較大的問題。為抵御混洗器和收集端的合謀攻擊，在擾動后的數據中添加虛擬數據，混洗端將擾動后的數據和虛擬數據隨機均勻混洗，并在收集端進行直方圖發(fā)布，最后使用EM算法對混洗后的數據求精優(yōu)化。從理論上分析了OD-HP算法的隱私性和可用性，并在真實數據集上對所提出的方案進行驗證。實驗結果表明OD-HP算法在保證數據隱私性的同時有效降低了發(fā)布誤差。

關鍵詞：混洗差分隱私；直方圖發(fā)布；虛擬數據；均方誤差

中圖分類號：TP309.2"" 文獻標志碼：A

文章編號：1001-3695（2024）12-041-3829-05

doi： 10.19734/j.issn.1001-3695.2024.01.0110

SDP histogram publishing algorithm based on OLH and dummy points

Cao Laicheng， Chen Li

（School of Computer amp; Communication， Lanzhou University of Technology， Lanzhou 730050， China）

Abstract：Histogram publishing techniques under both centralized differential privacy and local differential privacy have been extensively researched. Aiming at the problems of balancing user privacy requirements and publishing error， this paper proposed a histogram publishing algorithm named OD-HP （histogram publishing based on optimized local hash and dummy points）. The algorithm used the optimized local hash perturbation mechanism OLH to encode and perturb user data， addres-sing the issue of significant errors caused by large data value ranges. To mitigate collusion attacks between the shuffler and collector， it added dummy points to the perturbed data. The shuffler randomly and evenly mixed the perturbed data and dummy points， and performed histogram publishing in the collector. Finally， it employed the EM algorithm" to fine-tune the shuffled data. It theoretically analyzed the privacy and utility of the OD-HP algorithm and validated the proposed approach is" on real datasets. The experimental results demonstrate that the OD-HP algorithm effectively reduces publishing errors and ensuring data privacy.

Key words：shuffled differential privacy; histogram publishing; dummy points; MSE

0 引言

隨著互聯網和物聯網等技術的快速發(fā)展和廣泛應用，各大企業(yè)機構對用戶數據的收集和利用也變得愈加頻繁。然而，鑒于用戶隱私數據泄露事件屢見不鮮，在數據收集和使用的過程中，對用戶數據的保護顯得尤為關鍵。類別數據的頻率估計，即對用戶類別數據的直方圖發(fā)布方法在隱私保護領域也備受廣泛關注。直方圖是分析類別數據常用的技術，該技術使用分箱技術將數據集劃分為多個不相交的桶，使用頻率或者計數表示數據特征。CDP和LDP下的直方圖發(fā)布技術已經得到廣泛研究。在CDP模型中，通常使用指數機制和拉普拉斯機制對類別數據進行直方圖發(fā)布。LAP[1]、Boost[2]和NoiseFirst[3]是CDP模型下的直方圖發(fā)布的典型算法。LAP算法對直方圖的每個桶添加Laplace噪聲，達到隱私保護的目的。Boost算法以層次樹的形式記錄桶數，并結合樹的層次高度和拉普拉斯機制發(fā)布差分隱私直方圖。NoiseFirst算法對直方圖的每個桶添加Laplace噪聲，通過V-優(yōu)化直方圖技術對擾動后的直方圖進行分組。以上方法均是通過分組和重構來進行直方圖發(fā)布，但是它們無法平衡分組重構誤差和所添加的拉普拉斯噪聲誤差。近年來，Zhu等人[4]將直方圖壓縮和層次樹直方圖結合提出基于粗分割和動態(tài)預算分配的直方圖發(fā)布方法PSHPartition。對查詢范圍較大的數據集，將直方圖粗分割成簇，根據每個簇中桶的數量進行動態(tài)預算分配。Tao等人[5]提出一種對稱直方圖發(fā)布方法DPHR解決了兩種誤差帶來的發(fā)布精度低的問題。

在LDP模型下，直接擾動用戶的本地數據然后發(fā)布其直方圖。谷歌Chrome瀏覽器使用的RAPPOR[6]方法實現用戶瀏覽數據的隱私保護，RAPPOR結合UE編碼與Bloom filter，使用哈希算法將屬性映射到較小的值域上，在哈希后的值域上進行頻率估計。Wang等人[7]對LDP模型上一維類別數據隨機響應機制的誤差進行理論證明，并提出了OUE及OLH擾動方法。OUE和OLH分別利用一元編碼和本地哈希機制提高發(fā)布精度，適用于取值域較大的情況，但以上方法都是針對單維類別數據進行的。Ren等人[8]將LDP模型下的數據發(fā)布問題從一維屬性擴展到多維屬性，應用k長度向量的思想，將輸入轉換為帶噪的向量發(fā)給收集者，但是此模型只針對離散型數據。Wang等人[9]又提出了能處理數值屬性和類別屬性的多維數據的分段機制（PM）和混合機制（HM）。但是以上算法無法在計算效率和發(fā)布精度之間取得平衡。為解決上述問題，Xue等人[10]提出一種動態(tài)差分隱私報告機制DDRM，用于LDP下的連續(xù)頻率估計，引入差異樹來捕獲數據隨時間的變化，這很好地解決了數據變化時可能出現的隱私泄露問題。Liu等人[11]基于概率圖模型提出一種基于增量學習的PGM構建方法，對相關性弱的屬性進行修剪，將更多的數據和隱私預算分配給有用的邊緣，從而提高模型分配準確性。

CDP模型依賴完全可信的第三方服務器對數據進行處理，現實世界很難達到完全可信的條件。LDP不依賴于可信第三方，但是該模型對每一個用戶的數據進行擾動，導致數據效用較差。為克服以上兩種模型的缺點，Bittau等人[12]提出混洗差分隱私（SDP）模型，該模型是對CDP與LDP模型的平衡。該模型在用戶端和數據分析端引入洗牌器shuffler，shuffler負責對用戶端擾動后的數據進行混洗操作，混洗后將結果發(fā)送給數據收集端。shuffle操作破壞了用戶和數據的關聯，為用戶提供了接近LDP模型的隱私保護，為收集器提供了接近CDP模型的查詢和發(fā)布精度。

Cheu等人[13]提出單消息混洗模式下的隱私保護算法DDPS，并給出了混洗差分隱私的形式化定義。對于二元數據的局部攝動，該算法將GRR擾動方法分解為伯努利分布和均勻分布。但是這個算法的可用性低，查詢誤差大。Balle等人[14]對混洗操作的隱私性進行分析，并且證明了隱私預算為ε時，隱私保護程度可以提高至14 ln（2/δ）（eε+k－1）/（n－1），其中k為隨機響應機制的擾動域大小。SH算法[14]對GRR的輸出概率進行線性分解，使用添加的隨機噪聲對用戶的真實數據進行覆蓋，達到增強隱私的目的，但其發(fā)布精度容易受到值域大小的影響。MURS[15]利用本地哈希編碼技術將大值域映射到較小的值域上，提高了數據的發(fā)布精度，但是沒有涉及具體的混洗算法和后處理機制。

Li等人[16]提出了pureDUMP和mixDump方法，在用戶發(fā)送擾動值的同時發(fā)送隨機數據，mixDUMP算法在多消息模式下提升了發(fā)布精度。以上方法在洗牌放大時增加了洗牌量，從而獲得隱私收益，但在一定程度上也引入了較大的通信開銷。劉藝菲等人[17]提出SDP模型下多維類別屬性的發(fā)布算法，設計了兩種數據發(fā)布方案ARR-SS和SRR-MS，通過取值域填補技術對多維屬性的數據進行歸一化。但是上述算法都沒有涉及具體的混洗方法和后處理方法。張嘯劍等人[18]提出一種直方圖發(fā)布算法HP-SDP，該算法結合本地哈希編碼技術設計了混洗擾動機制，消除數據域大小的影響，并使用基于二次規(guī)劃的后置處理算法對混洗后的直方圖求精并發(fā)布。丁紅發(fā)等人[19]提出混洗差分隱私下的度分布直方圖發(fā)布算法，使用方波機制對本地用戶進行擾動，并利用極大似然估計對加噪后的度分布直方圖進行校正發(fā)布，從而提高數據的可用性，但是此方法是基于圖數據的隱私保護方案。Chen等人[20]提出了基于K-means++（DPHK+）的差分隱私直方圖發(fā)布，實現了對當前窗口數據的啟發(fā)式非等距直方圖發(fā)布。利用K-means++對發(fā)布數據進行聚類，自動選擇K值進行非等距分組，并結合拉普拉斯噪聲進行差分隱私直方圖發(fā)布。Takagi等人[21]提出無界洗牌的框架，通過在傳統(tǒng)的洗牌模型中加入虛擬數據進行隱私放大。Wang等人[22]消除了每個用戶只能發(fā)送一條消息所帶來的誤差，提出一個支持隨機填充的多消息混洗協(xié)議。

但是以上方案沒有綜合考慮到值域過大帶來的誤差和混洗器與其他服務器或用戶合謀攻擊的問題。為了解決上述問題，在SDP模型下，提出了一種類別數據的直方圖發(fā)布算法OD-HP。使用優(yōu)化本地哈希機制OLH解決值域過大帶來的影響，并在擾動后的數據中加入隨機數量的虛擬點與真實數據混淆，混洗器對所有數據進行混洗，分析端接收所有數據，校正后發(fā)布。SD-HP算法具有較高的可用性和發(fā)布精度。

1 基礎技術與問題

1.1 中心化差分隱私

定義1 （ε，δ）-中心化差分隱私。給定相鄰數據集D和D′，D和D′中僅有一條記錄不同，隨機擾動算法M，輸出的所有值的集合y′。若算法M作用在數據集D和D′上得到的輸出結果y′的概率滿足下列不等式，則M滿足（ε，δ）-中心化差分隱私：

Pr［M（D）∈y′］≤eε×Pr［M（D′）∈y′］+δ（1）

其中：ε為隱私預算，用來衡量模型的隱私保護程度；δ（δ∈（0，1］）為隱私泄露概率。

1.2 本地化差分隱私

定義2 （ε，δ）-本地化差分隱私。給定n個用戶，每個用戶對應一條數據，v和v′為任意兩個用戶的數據。給定隨機擾動算法M。若算法M在v和v′上得到相同的輸出結果y′的概率滿足下列不等式，則M滿足（ε，δ）-本地化差分隱私：

Pr［M（v）∈y′］≤eε×Pr［M（v′）∈y′］+δ（2）

其中：ε為隱私預算，用來衡量模型的隱私保護程度；δ（δ∈（0，1］）為隱私泄露概率。

定義3 優(yōu)化本地哈希OLH[6]。假設H是一個通用哈希函數簇，使得每個H∈H輸出為［h］中的一個值。將用戶數據編碼為〈H，x〉，其中H從H中隨機選取。OLH的擾動方法為

Pr［OLH（x）=y］=p=eεeε+h－1 if x=yq=1eε+h－1 if x≠y（3）

其中：v表示用戶擁有的數據；x表示v哈希后的值，x=H（v）；y表示哈希值域［h］中的任意值，h表示哈希函數值域的大??；d表示數據值域的大小。

1.3 混洗差分隱私

定義4 （ε，δ）-混洗差分隱私。給定n個用戶，每個用戶ui存在數據vi∈V，R：V→Yn表示對數據vi進行擾動，得到擾動后的數據yi=R（vi）；S：Yn→Ψ（Yn）表示洗牌器對用戶的輸出結果進行混洗操作，Ψ表示隨機混洗操作；算法A：Ψ（Yn）→Z表示分析函數?；煜床罘蛛[私協(xié)議表示為M=（R，S，A）。令M={y1，y2，…，yn}，S（M）表示混洗之后的輸出結果，其值域表示為y′。若其輸出結果S（M）滿足（ε，δ）-中心化差分隱私，則M滿足（ε，δ）-混洗差分隱私，當且僅當對于任意兩個相鄰數據集D和D′，任意輸出的集合滿足下列不等式：

Pr［M（D）∈y′］≤eε×Pr［M（D′）∈y′］+δ（4）

其中：ε為隱私預算，用來衡量模型的隱私保護程度；δ（δ∈（0，1］）為隱私泄露概率。

1.4 直方圖發(fā)布技術

數據發(fā)布是數據共享的一個重要環(huán)節(jié)，直方圖發(fā)布是一種針對類別數據的常用數據發(fā)布方式。直方圖發(fā)布指利用分箱技術，將要發(fā)布的數據集按照類別屬性劃分為多個不相交的桶，然后統(tǒng)計每個桶的計數或頻率進行發(fā)布或提供查詢。例如，圖1（a）記錄了部分用戶所患疾病信息，圖1（b）是基于用戶及所患疾病隱私數據對應的直方圖。然而，直方圖發(fā)布的過程中依然存在著隱私泄露的風險。例如，圖1（b）中的flu頻率為3，攻擊者獲得flu的頻率并操控Alice和Tina，通過鏈接攻擊和操縱攻擊即可得知圖1（a）中的Luka的隱私信息。

1.5 直方圖發(fā)布的誤差問題描述

分析OD-HP算法對直方圖發(fā)布的效用時，使用均方誤差（mean squared error，MSE）作為衡量精度的標準。假設有n個用戶，一個可信的數據混洗器和一個數據收集者。每個用戶產生一個類別數據vi∈H，選取本地擾動算法O對用戶產生的數據vi進行擾動，即O（v1），O（v2），…，O（vn），并產生服從二項分布的m條虛擬數據，混洗器收集n（m+1）條數據，并對其進行混洗操作。收集者收集混洗后的數據，校正后進行頻率估計和直方圖發(fā)布。v的頻率估計值可以通過fv=1h∑i∈［n］I{x=y}進行計算。收集者的目的是估計每個用戶v的頻率估計值f～v。精度由均方誤差MSE來表示：

MSE（F，F～）=1h∑v∈H（fv－f～v）2（5）

其中：F與F～表示原始直方圖與估計直方圖；fv與f～v表示數據的真實頻率與估計頻率。

2 基于混洗差分隱私的直方圖發(fā)布算法

OD-HP算法的總體發(fā)布框架如圖2所示，主要包含系統(tǒng)用戶（user1，user2，…，usern）、混洗器以及分析器。在用戶端對用戶的數據進行隨機化擾動，混洗器收集所有用戶數據進行，從而消除用戶和數據之間的對應關系，確保數據匿名，分析器對收集到的匿名數據集進行分析，進行直方圖發(fā)布。其中，V1，V2，…，Vn為用戶user1，user2，…，usern產生的數據，〈Hi，xi〉為使用OLH擾動算法擾動后的數據，dummy為添加的虛擬數據，其具體表示為〈Hi，y1〉，〈Hi，y2〉，…，〈Hi，ym〉且服從負二項分布?；煜雌鳎╯huffer）合并所有用戶數據和虛擬點在混洗端進行隨機混洗，分析端（analyzer）收集數據，使用EM算法進行求精，然后完成直方圖發(fā)布。每個用戶產生一條數據vi，考慮到值域過大帶來的發(fā)布誤差，用戶端使用OLH擾動算法對用戶的原始數據進行擾動，將值域d哈希到一個更小的取值空間h中，隱私預算為εl。與本地化差分隱私下的擾動機制不同，在SDP模型下使用OLH機制，使用隱私毯子的技術對算法的輸出概率進行分解。以p=eεl/（eεl+h－1）的概率發(fā)布真實值，以q=1/（eεl+h－1）的概率發(fā)布隨機值。OLH的輸出分解為

y∈HPr［OLH（x）=y］=（1－γ）I{x=y}+γPr［Uniform（H）=y］其中：I{x=y}為標識函數；γ（γ∈（0，1］）為用戶參與隨機化的概率。用戶使用OLH算法對數據擾動后得到〈Hi，xi〉，系統(tǒng)根據用戶數量、取值域大小和隱私預算計算出需要生成m個虛擬點，其中m遵循負二項分布，如下所示。

NBin（r，p）（m）=m+r－1r－1（1－p）mpr（6）

其中：r是自然數，p∈（0，1）。最后每個用戶將m個虛擬點和一條擾動后的數據發(fā)送給混洗器?；煜雌鲗κ占降膎（m+1）條用戶數據和虛擬點進行隨機排列。分析器收集混洗后的數據，生成隱私保護后的數據分布直方圖，并使用EM算法對數據分布直方圖進行校正分析，聚合得到最終的數分布直方圖。對每個值v∈H使用f～v=1n∑i∈［n］I{x=y}－1/hp－1/h計算其估計頻率。

2.1 OD-HP算法

算法1 OD-HP算法

輸入：用戶數量n；用戶數據vi；隱私預算ε；哈希函數值域H；H=h，γ。

輸出：直方圖。

用戶端：

1 for user" i=1 to n do

2" "user i computes 〈Hi，xi〉=OLH〈vi，ε〉;

//第i個用戶使用OLH算法對本地數據進行擾動

3" "generates dummy points〈Hi，y〉={〈Hi，y1〉，〈Hi，y2〉，…，〈Hi，ym〉};

//在第i個用戶端添加m個虛擬數據

4" "user i concatenates〈Hi，Yi〉=〈Hi，y〉∪〈Hi，xi〉;

//第i個用戶合并擾動后的數據和添加的虛擬數據

5" "user i sends 〈Hi，Yi〉 to the shuffler;

//用戶將合并后的數據發(fā)送到混洗器

6 end for

混洗端：

7 shuffler concatenates each pair〈Hi，Yi〉：K←K∪〈Hi，Yi〉;

//混洗器收集所有用戶數據并合并

8 shuffler randomly permutates〈Hi，Yi〉;

//混洗器將收集到的數據隨機均勻混洗

9 shuffler sends〈Hi，Yi〉 to the collector;

//混洗器將混洗后的數據發(fā)送給數據收集者

收集端：

10 for each〈Hi，Yi〉 do

11" calculate f～v;

//收集端收集數據并計算數據的估計頻率

12" F～←F～∪f～v;//計算每個數據的估計頻率

13 end for

14 F-=EM（F～）;//使用EM算法對數據進行求精處理

15 return

2.2 OD-HP算法的隱私性分析

定理1 對于任意的h，m，n∈N，算法OD-HP滿足（ε，δ）-DP，即算法滿足中心化差分隱私。其中：

ε≤14h ln（4/δ）|M|+γ（n－1）－2γ（n－1）ln（2/δ）－1（7）

其中：h表示哈希函數值域的大小；m表示加入虛擬點的數量；|M|=nm；γ為用戶參與隨機化的概率。

證明 D和D′為兩個相鄰數據集，其中只有一條數據不同，M和M′表示兩個不同的虛擬數據集，假設第n個用戶的值從1變?yōu)?，將D和D′形式化為［x1，…，xn］和［x1，…，x′n］。在OD-HP中，每個用戶以γ的概率將其數據進行隨機化，如果第n個用戶隨機化其數據，可以得到Pr［O（D）∨M=T］Pr［O（D′）∨M′=T］=1。虛擬點是從原始數據域D中隨機選取，因此虛擬點的分布與參與隨機化的用戶數據的分布相同，用A表示參與隨機化的用戶集合，A∨M遵循隨機均勻分布，可以得到Pr［O（D）∨M=T］≤eεPr［O（D′）∨M′=T］+δ2，其中ε=14h ln（4/δ）|A|+|M|－1。由于|A|遵循負二項分布NBin（n－1，γ），根據切諾夫邊界定理可以得到Pr［|A|lt;（1－λ）μ］lt;δ2，其中λ=2ln（2/δ）（n－1）γ。

因此，可以得到

Pr［O（D）∨M=T］≤Pr［O（D）∨M=T∩|A|≥（n－1）γ－2（n－1）γln（2/δ）］+δ2（8）

令b=（n－1）γ－2（n－1）γln（2/δ），得到

Pr［O（D）∨M=T］≤（∑a≥bPr［O（D）∨M=T］Pr［A=a］+δ2）≤e14hln（4/δ）b+|M|－1Pr［O（D′）∨M=T］+δ=e14hln（4/δ）（n－1）γ－2（n－1）γln（2/δ）+|M|－1Pr［O（D′）∨M=T］+δ（9）

證明完畢。

2.3 OD-HP算法的可用性分析

由于OD-HP算法采用OLH進行擾動，并添加一定數量的虛擬點，所以在進行fv的無偏估計時會產生誤差。使用MSE作為衡量OD-HP算法準確性的指標，定理2證明f～v是無偏的，定理3證明f～v的方差。

2.3.1 估計頻率的無偏性證明

定理2 假設fv和f～v分別表示數據v的真實頻率和估計頻率，則Ef～v=fv成立，即f～v是fv的無偏估計。

證明 f～=∑i∈［n］，j∈［m+1］（Ixi=y－nγ（1－1h））－nmhn1－2γ1－1h

其中γ=hh－1q，用γ代替q對f～v進行化簡，得到f～v=1n∑i∈［n］，j∈［m+1］Ixi=y－nq－nmh1－2q。在OLH擾動中，用戶數據保持其真實值的概率為p，隨機化的概率為q。

Ef～v=E1n ∑i∈［n］，j∈［m+1］Ixi=y－nq－nmh1－2q=1n·11－2q·E∑i∈［n］，j∈［m+1］Ixi=y－nq－nmh=1n·11－2q·nfv（1－q）+n（1－fv）q+nmh－nq－nmh=1n·11－2q·1－2q·nfv=fv（10）

證明完畢，Ef～v=fv成立，即f～v是fv的無偏估計。

2.3.2 估計頻率的方差證明

定理3 OD-HP中頻率估計的方差為Varf～v=1n·eεl+h－2（eεl－1）2+m（h－1）nh2·eεl+h－2eεl－12，其中εl是OLH的隱私預算。

證明 在OD-HP算法中，p=eεl/eεl+h－1，q=1/（eεl+h－1），γ=hq，使用γ代替q進行化簡，得到

Varf～v=Var1n ∑i∈［n］，j∈［m+1］Ixi=y－nm·1h－nqp－q=1n2·1p－q2·（nfvp（1－p）+n（1－fv）q（1－p）+nm·1h·h－1h）1n2·1p－q2nq（1－q）+nm·1h·h－1h=1n2·eεl+h－1eεl－12·n（eεl+h－2）（eεl+h－1）2+h－1h2·nm=1n·eεl+h－2（eεl－1）2+m（h－1）nh2·eεl+h－2eεl－12（11）

證明完畢。根據對OD-HP算法的無偏性估計證明和方差證明，可以得到估計頻率f～v的均方誤差為

MSE=1h∑v∈HE［（f～v－fv）2］=1h∑v∈H（Var［f～v］+［E（f～）－f］2）=1h∑v∈HVar［f～v］=Var［f～v］（12）

2.4 OD-HP算法的效率分析

在OD-HP算法中，系統(tǒng)的每個用戶使用OLH算法對其真實數據進行擾動，每個用戶添加m條虛擬數據，對于輸入的n個用戶數據，用戶最多輸出m+1條長度為log2h的消息。用戶端的時間開銷主要是在數據隨機化擾動和虛擬點上。本文提出的OD-HP算法滿足（ε，δ）-DP，m最大為O（14h ln（4/δ）/（nε2）－γ（1-2ln（2/δ）/（γn））），當ε接近0時，m的上界接近于O（14hln（4/δ）/（nε2））?；煜雌飨蚍治銎靼l(fā)送n（m+1）條數據，其空間復雜度為O（hlog2（n（m+1））），誤差為O（ln（1/δ）/（nε（1－γ）））。γ是用戶參與隨機化的概率，γ=heεl+h－1，εl越大，OD-HP算法的精度越高，因此算法的估計誤差為O1nε·1+heεl－1·log1δ。

3 實驗結果與分析

為驗證OD-HP算法的有效性，設計以下實驗對OD-HP算法進行評估。實驗機內存為16 GB，CPU為IntelCoreTM i5-7200U CPU@2.50" GHz，操作系統(tǒng)為Windows10，代碼基于Python實現。實驗采用IPUMS和Kosarak兩個真實數據集。IPUMS數據集是美國1940年人口普查數據集，抽取1%的用戶數據進行實驗，選取其中“城市”這一屬性，數據中包含602 325個用戶和915個城市。Kosarak數據集是匈牙利網站上100萬點擊流的數據集，包含100萬個用戶，有42 178種可能取值，對不同的數據，隨機選擇一項作為用戶數據。

實驗采用均方誤差MSE作為算法誤差的度量標準，在δ=10－6的情況下，隱私預算從0.1變化到1時，將MURS、HP-SDP、mixDUMP與OD-HP算法進行比較。下面介紹對比算法：

MURS算法[15]使用本地哈希機制將數據大值域映射到較小的地址空間中，克服了SH算法和AUE算法在大值域發(fā)布中誤差較大的缺點，但是沒有給出具體的混洗算法和后處理算法。

HP-SDP算法[18]提出隨機擾動機制SRR和基于堆排列技術的用戶消息均勻隨機排列算法MRS，并使用后置處理算法POP對混洗后的數據求精并發(fā)布。但是該算法沒有考慮到混洗器和分析端合謀攻擊的情況，隱私性較低。

mixDUMP算法[16]使用GRR機制對用戶數據擾動，并提出虛擬毯的概念，在擾動后的數據中添加一定數量的虛擬數據，混洗器隨機均勻混洗擾動后的數據和添加的虛擬數據，從而提高算法的隱私性。算法的隱私性由隨機擾動算法和虛擬數據一起提供。但是mixDUMP算法在收集端沒有對混洗后的數據進行求精處理，數據的可用性不高，且算法使用GRR機制進行擾動，不適用于大值域上的數據發(fā)布。

圖3描述了MURS、HP-SDP、mixDUMP與OD-HP算法在IPUMS數據集上MSE值的變化；圖4描述了MURS、HP-SDP、mixDUMP與OD-HP算法在Kosarak數據集上MSE值的變化。通過實驗可以發(fā)現，當隱私預算ε從0.1到1變化時，四種方法的MSE均呈下降趨勢。因為隱私預算ε越大，加入的噪聲越少，所以MSE的值越小。OD-HP算法優(yōu)于MURS、HP-SDP和mixDUMP這三種算法。MURS采用本地哈希技術進行擾動，mixDUMP算法采用GRR機制對數據進行擾動，發(fā)布精度易受值域大小的影響，發(fā)布精度沒有OD-HP算法低。HP-SDP算法沒有考慮到混洗器與收集端的合謀攻擊，隱私性會降低。OD-HP算法使用OLH對數據進行擾動，并使用EM算法進行后置求精處理，所以OD-HP算法在隱私性和發(fā)布精度方面都比上述方案具有優(yōu)勢。

采用時間開銷來衡量算法的效率，在δ=10－6，ε=0.1的情況下對比MURS、HP-SDP、mixDUMP與OD-HP算法在IPUMS和Kosarak數據集上的時間開銷，實驗結果如圖5所示。

4 結束語

針對混洗差分隱私下的直方圖發(fā)布問題，本文在混洗差分隱私模型下提出了一種OD-HP（optimized local hashing and dummy points）的直方圖發(fā)布算法。該算法結合了優(yōu)化本地哈希技術和插入虛擬數據的方法，旨在解決大值域帶來的誤差問題，并抵御混洗器與服務器或用戶之間的合謀攻擊。算法采用優(yōu)化的本地哈希機制OLH對用戶原始數據擾動，將用戶數據從大值域哈希到較小的值域，改善了值域過大帶來的誤差問題。同時，為了防止混洗器與收集端的合謀攻擊，添加虛擬數據與擾動后的數據一起混洗，并校正發(fā)布。對算法的隱私性和可用性進行理論分析和證明，并在真實數據集IPUMS和Kosarak上對比分析OD-HP算法和已有的MURS、HP-SDP、mixDUMP三種算法的均方誤差，實驗結果表明本文算法具有較低的誤差。今后的研究考慮以下兩個方面：a）如何設計快速高效的混洗算法；b）本文是靜態(tài)數據下的直方圖發(fā)布，如何在動態(tài)數據集上進行滿足差分隱私的直方圖發(fā)布算法研究。

參考文獻：

[1]

Dwork C. Differential privacy [C]// Proc of International Colloquium on Automata， Languages， and Programming. Berlin： Springer， 2006： 1-12.

[2]Hay M， Rastogi V，Miklau G， et al. Boosting the accuracy of diffe-rentially-private histograms through consistency [J]. Proceedings of the VLDB Endowment， 2010， 3 （1）： 1021-1032.

[3]Xu Jia， Zhang Zhenjie， Xiao Xiaokui， et al. Differentially private histogram publication [J]. The VLDB Journal， 2013， 22 （6）： 797-822.

[4]Zhu Hui， Yin Fan， Peng Shuangrong， et al. Differentially private hierarchical tree with high efficiency [J]. Computers amp; Security， 2022， 118： 102727.

[5]Tao Tao， Li Siwen， Huang Jun， et al. A Symmetry histogram publi-shing method based on differential privacy [J]. Symmetry， 2023， 15 （5）： 1099-1113.

[6]Erlingsson ，Pihur V， Korolova A. RAPPOR： randomized aggrega-table privacy-preserving ordinal response [C]// Proc of ACM SIGSAC Conference on Computer and Communications Security. New York： ACM Press， 2014： 1054-1067.

[7]Wang Tianhao， Blocki J， Li Ninghui， et al. Locally differentially private protocols for frequency estimation [C]// Proc of the 26th USENIX Security Symposium. Berkeley， CA： USEMIX Association， 2017： 729-745.

[8]Ren Xuebin， Yu C M， Yu Weiren， et al. LoPub： high-dimensional crowdsourced data publication with local differential privacy [J]. IEEE Trans on Information Forensics and Security， 2018， 13 （9）： 2151-2166.

[9]Wang Ning， Xiao Xiaokui， Yang Ying， et al. Collecting and analyzing multidimensional data with local differential privacy [C]// Proc of the 35th IEEE International Conference on Data Engineering. Piscataway， NJ： IEEE Press， 2019： 638-649.

[10]Xue Qiao， Ye Qingqing， Hu Haibo， et al. DDRM： a continual frequency estimation mechanism with local differential privacy [J]. IEEE Trans on Knowledge and Data Engineering， 2023， 35 （7）： 6784-6797.

[11]Liu Gaoyuan， Tang Peng， Hu Chengyu， et al. Multi-dimensional data publishing with local differential privacy [C]// Proc of the 26th International Conference on Extending Database Technology. Berlin： Springer， 2023，2023： 183-194.

[12]Bittau A， Erlingsson ， Maniatis P， et al. Prochlo： strong privacy for analytics in the crowd [C]//Proc of the 26th Symposium on Opera-ting Systems Principles. New York： ACM Press， 2017： 441-459.

[13]Cheu A， Smith A， Ullman J， et al. Distributed differential privacy via shuffling [C]// Proc of Advances in Cryptology： the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2019： 375-403.

[14]Balle B， Bell J， Gascón A， et al. The privacy blanket of the shuffle model [C]// Proc of Advances in Cryptology： the 39th Annual International Cryptology Conference. Berlin： Springer， 2019： 638-667.

[15]Wang Tianhao， Xu Min， Ding Bolin， et al. MURS： practical and robust privacy amplification with multi-party differential privacy [C]// Proc of Annual Computer Security Applications Conference. Piscata-way， NJ： IEEE Press， 2019.

[16]Li Xiaochen， Liu Weiran， Feng Hanwen， et al. Privacy enhancement via dummy points in the shuffle model [J]. IEEE Trans on Dependable and Secure Computing， 2023，21（3）：1001-1016.

[17]劉藝菲， 王寧， 王志剛， 等. 混洗差分隱私下的多維類別數據的收集與分析 [J]. 軟件學報， 2022， 33 （3）： 1093-1110. （Liu Yifei， Wang Ning， Wang Zhigang， et al. Collecting and analyzing multidimensional categorical data under shuffled differential privacy [J] Journal of Software， 2022， 33 （3）： 1093-1110.）

[18]張嘯劍， 徐雅鑫， 夏慶榮. 基于混洗差分隱私的直方圖發(fā)布方法 [J]. 軟件學報， 2022， 33 （6）： 2348-2363. （Zhang Xiaojian， Xu Yaxin， Xia Qingrong. Histogram publication under shuffled differential privacy [J]. Journal of Software， 2022， 33 （6）： 2348-2363.）

[19]丁紅發(fā)， 傅培旺， 彭長根， 等. 混洗差分隱私保護的度分布直方圖發(fā)布算法 [J]. 西安電子科技大學學報， 2023， 50（6）： 1-18. （Ding Hongfa， Fu Peiwang， Peng Changgen， et al. Histogram publishing algorithm for degree distribution via shuffled differential privacy [J]. Journal of Xidian University， 2023， 50 （6）： 1-18.）

[20]Chen Qian， Ni Zhiwei， Zhu Xuhui， et al. Differential privacy histogram publishing method based on dynamic sliding window [J]. Frontiers of Computer Science， 2023， 17 （4）： 174809.

[21]Takagi S， Kato F， Cao Yang， et al. From bounded to unbounded： privacy amplification via shuffling with dummies [C]// Proc of the 36th IEEE Computer Security Foundations Symposium. Piscataway， NJ： IEEE Press， 2023： 457-472.

[22]Wang Shaowei， Luo Xuandi， Qian Yuqiu， et al. Shuffle differential private data aggregation for random population [J]. IEEE Trans on Parallel and Distributed Systems， 2023， 34 （5）： 1667-1681.