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

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

中圖分類號(hào)：TP309.2"" 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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 引言

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

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

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

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

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

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

1 基礎(chǔ)技術(shù)與問題

1.1 中心化差分隱私

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

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

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

1.2 本地化差分隱私

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

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

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

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

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

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

1.3 混洗差分隱私

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

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

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

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

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

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

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

MSE（F，F(xiàn)～）=1h∑v∈H（fv－f～v）2（5）

其中：F與F～表示原始直方圖與估計(jì)直方圖；fv與f～v表示數(shù)據(jù)的真實(shí)頻率與估計(jì)頻率。

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

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

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

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

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

2.1 OD-HP算法

算法1 OD-HP算法

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

輸出：直方圖。

用戶端：

1 for user" i=1 to n do

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

//第i個(gè)用戶使用OLH算法對(duì)本地?cái)?shù)據(jù)進(jìn)行擾動(dòng)

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

//在第i個(gè)用戶端添加m個(gè)虛擬數(shù)據(jù)

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

//第i個(gè)用戶合并擾動(dòng)后的數(shù)據(jù)和添加的虛擬數(shù)據(jù)

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

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

6 end for

混洗端：

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

//混洗器收集所有用戶數(shù)據(jù)并合并

8 shuffler randomly permutates〈Hi，Yi〉;

//混洗器將收集到的數(shù)據(jù)隨機(jī)均勻混洗

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

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

收集端：

10 for each〈Hi，Yi〉 do

11" calculate f～v;

//收集端收集數(shù)據(jù)并計(jì)算數(shù)據(jù)的估計(jì)頻率

12" F～←F～∪f～v;//計(jì)算每個(gè)數(shù)據(jù)的估計(jì)頻率

13 end for

14 F-=EM（F～）;//使用EM算法對(duì)數(shù)據(jù)進(jìn)行求精處理

15 return

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

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

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

其中：h表示哈希函數(shù)值域的大?。籱表示加入虛擬點(diǎn)的數(shù)量；|M|=nm；γ為用戶參與隨機(jī)化的概率。

證明 D和D′為兩個(gè)相鄰數(shù)據(jù)集，其中只有一條數(shù)據(jù)不同，M和M′表示兩個(gè)不同的虛擬數(shù)據(jù)集，假設(shè)第n個(gè)用戶的值從1變?yōu)?，將D和D′形式化為［x1，…，xn］和［x1，…，x′n］。在OD-HP中，每個(gè)用戶以γ的概率將其數(shù)據(jù)進(jìn)行隨機(jī)化，如果第n個(gè)用戶隨機(jī)化其數(shù)據(jù)，可以得到Pr［O（D）∨M=T］Pr［O（D′）∨M′=T］=1。虛擬點(diǎn)是從原始數(shù)據(jù)域D中隨機(jī)選取，因此虛擬點(diǎn)的分布與參與隨機(jī)化的用戶數(shù)據(jù)的分布相同，用A表示參與隨機(jī)化的用戶集合，A∨M遵循隨機(jī)均勻分布，可以得到Pr［O（D）∨M=T］≤eεPr［O（D′）∨M′=T］+δ2，其中ε=14h ln（4/δ）|A|+|M|－1。由于|A|遵循負(fù)二項(xiàng)分布NBin（n－1，γ），根據(jù)切諾夫邊界定理可以得到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進(jìn)行擾動(dòng)，并添加一定數(shù)量的虛擬點(diǎn)，所以在進(jìn)行fv的無偏估計(jì)時(shí)會(huì)產(chǎn)生誤差。使用MSE作為衡量OD-HP算法準(zhǔn)確性的指標(biāo)，定理2證明f～v是無偏的，定理3證明f～v的方差。

2.3.1 估計(jì)頻率的無偏性證明

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

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

其中γ=hh－1q，用γ代替q對(duì)f～v進(jìn)行化簡(jiǎn)，得到f～v=1n∑i∈［n］，j∈［m+1］Ixi=y－nq－nmh1－2q。在OLH擾動(dòng)中，用戶數(shù)據(jù)保持其真實(shí)值的概率為p，隨機(jī)化的概率為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的無偏估計(jì)。

2.3.2 估計(jì)頻率的方差證明

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

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

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）

證明完畢。根據(jù)對(duì)OD-HP算法的無偏性估計(jì)證明和方差證明，可以得到估計(jì)頻率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)的每個(gè)用戶使用OLH算法對(duì)其真實(shí)數(shù)據(jù)進(jìn)行擾動(dòng)，每個(gè)用戶添加m條虛擬數(shù)據(jù)，對(duì)于輸入的n個(gè)用戶數(shù)據(jù)，用戶最多輸出m+1條長度為log2h的消息。用戶端的時(shí)間開銷主要是在數(shù)據(jù)隨機(jī)化擾動(dòng)和虛擬點(diǎn)上。本文提出的OD-HP算法滿足（ε，δ）-DP，m最大為O（14h ln（4/δ）/（nε2）－γ（1-2ln（2/δ）/（γn））），當(dāng)ε接近0時(shí)，m的上界接近于O（14hln（4/δ）/（nε2））?；煜雌飨蚍治銎靼l(fā)送n（m+1）條數(shù)據(jù)，其空間復(fù)雜度為O（hlog2（n（m+1））），誤差為O（ln（1/δ）/（nε（1－γ）））。γ是用戶參與隨機(jī)化的概率，γ=heεl+h－1，εl越大，OD-HP算法的精度越高，因此算法的估計(jì)誤差為O1nε·1+heεl－1·log1δ。

3 實(shí)驗(yàn)結(jié)果與分析

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

實(shí)驗(yàn)采用均方誤差MSE作為算法誤差的度量標(biāo)準(zhǔn)，在δ=10－6的情況下，隱私預(yù)算從0.1變化到1時(shí)，將MURS、HP-SDP、mixDUMP與OD-HP算法進(jìn)行比較。下面介紹對(duì)比算法：

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

[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]劉藝菲， 王寧， 王志剛， 等. 混洗差分隱私下的多維類別數(shù)據(jù)的收集與分析 [J]. 軟件學(xué)報(bào)， 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]. 軟件學(xué)報(bào)， 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ā)， 傅培旺， 彭長根， 等. 混洗差分隱私保護(hù)的度分布直方圖發(fā)布算法 [J]. 西安電子科技大學(xué)學(xué)報(bào)， 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.