基于彈性秘密共享的多方洗牌協議

滿子琪 張艷碩 嚴梓洋 羅樂琦 陳 穎

(北京電子科技學院 北京 100070)

數據隱私保護[1]問題已成為學術界關注的熱點.洗牌協議[2]是旨在實現安全隨機排列的協議,其將輸入的數據打亂以保證數據隱私.秘密共享技術[3]是一種秘密保護技術,其將秘密份額分發并設置恢復秘密的門限值.

基于彈性秘密共享的多方洗牌協議的主要思想為:彈性秘密共享技術將數據集拆分成多個份額,洗牌協議對份額混淆處理.只有同時擁有一定份額的參與者才能夠還原出原始數據.最后通過隱私交集計算,在參與者擁有數據集的交集達到了門限值后才能完成秘密的恢復.在此過程中,任何參與者都無法得知其他參與者所持有的數據,保證了數據的隱私性.

本文的主要創新點如下:1)引入了彈性秘密共享,增加了洗牌協議的容錯性以及抗合謀攻擊性;2)設計出一種多方下簡單且效率較高的洗牌協議,具有較好的應用性;3)將洗牌協議和隱私集合交集計算技術相結合完成秘密的恢復,提高了恢復過程的隱私性.

1 相關工作

1.1 彈性秘密共享

秘密共享最早由Shamir[4]于1979年提出,并于1986年[5]提出了(t,n)門限方案.Desmedt等人[6]于1991年提出了彈性秘密共享的概念.彈性秘密共享保證了存在一定數量惡意參與者的情況下方案的可靠性.Roy等人[7]于2014年提出了一種防止作弊行為的秘密共享方案.肖健等人[8]于2023年提出了一種基于多答案保護的彈性秘密共享協議.

與秘密共享相比,彈性秘密共享具有可恢復性強、安全性好、可擴展性強等優點.因此,本文創新地在洗牌協議中引入了彈性秘密共享,較之傳統的基于秘密共享的洗牌協議,本文協議具有更高的安全性與可擴展性.

1.2 洗牌協議

洗牌協議主要用于對數據進行隨機排序,最初由Chaum[9]于1981年提出.Chen等人[10]于2020年提出了一種基于秘密共享和洗牌的數據發布協議.Melissa等人[11]于2020年提出將加密的元素和位向量進行洗牌.粟勇等人[12]于2022年提出了一種基于安全洗牌和差分隱私的聯邦學習模型安全防護方法.

洗牌的特點在于其隨機性.數據集中的每組數據在洗牌后都等概率地出現在空間的各個位置,有效地降低了攻擊者找到某一特定元素進而展開攻擊的風險.

1.3 基于秘密共享的洗牌協議

2000年,Cramer等人[13]提出將洗牌協議和秘密共享相結合,但并未給出詳細的過程.2001年,Damgard等人[14]提出一種基于秘密共享的洗牌協議,主要特點是能夠實現公開驗證和保密性.但是,其對參與者的誠實性有較高要求.Pinkas等人[15]于2012年提出一種基于洗牌協議的安全多方計算協議,并提高了計算的效率和可擴展性.Kong等人[16]于2021年提出一種隨機化洗牌技術,用于保護參與者在協作學習過程中的隱私.

1.4 隱私集合交集計算

隱私集合交集計算[17]能夠在計算參與者私有數據集交集的同時,不泄露除交集以外的其他信息.

Meadows[18]于1986年提出首個隱私集合交集計算協議.隨后,Huberman等人[19]于1999年對Meadows[18]的方案作出了細致的描述.Freedman等人[20]于2004年基于不經意多項式求值構造了隱私集合交集計算協議.申立艷等人[21]于2017年對兩方隱私集合交集計算協議進行了簡要總結.高瑩等人[22]于2023年對基于多個參與者的隱私集合交集進行了綜述.

1.5 布隆過濾器

布隆過濾器是一種集合元素查詢工具[23],用來確定一個元素是否為集合的成員.Bloom[24]于1970年首次提出布隆過濾器,其主要功能是查詢元素是否屬于某集合.布隆過濾器可以看作將元素編碼在一個長度為m的數組中.通過使用哈希函數和位向量,對元素的哈希映射位置來間接存儲元素.

2 基于彈性秘密共享的多方洗牌協議的設計

2.1 整體思路

彈性秘密共享算法可以保證數據的機密性,確保數據不被惡意泄露.洗牌協議可以對數據進行重新排列,從而保護數據的隱私.

數據擁有者可以使用彈性秘密共享算法對數據進行共享,然后使用洗牌協議對數據進行重新排列,即使參與者竊取了部分密文也無法推斷出原始數據的內容.因此,將彈性秘密共享和洗牌協議相結合可以在保護數據隱私的同時保證數據的機密性和完整性.

2.2 詳細步驟

本文提出了一種基于彈性秘密共享的多方洗牌協議.假設本文采用的彈性秘密共享技術基于(t,n)門限,協議參與方的個數為n,參與方擁有的集合為X,每個集合的比特長度為a.本文所用的相關符號如表1所示:

表1 相關符號說明

該協議的具體流程如下:

1) 秘密份額的生成算法.

分發者選定一個秘密s,隨機性地選擇n個不同的索引作為相應的自變量{a1,a2,…,an}.

根據這些索引選擇一個最高次冪為t-1的秘密多項式f(x),滿足條件f(0)=s.

秘密份額的集合為{s1,s2,…,sn},且滿足條件si=f(ai).

2) 數據集的洗牌.

生成秘密份額后將這些秘密份額打亂順序,將秘密份額看作元素,并將這些元素組成長度為N×n的數組.

從末端元素開始向前遍歷數組.

直到第2個元素,對于每個位置i,隨機生成一個范圍在[0,i]之間的整數j.

接著將第i個位置的元素與第j個位置的元素交換.

然后繼續向前遍歷數組,重復前2段步驟,直到遍歷到第1個元素為止.

最后,打亂后的數組即為隨機打亂后的順序.

每個參與者只能看到自己所持有的數據部分,而無法看到其他參與者的數據.每個參與者可按照上述對其所持有的秘密共享數據部分進行洗牌.

3) 布隆過濾器生成算法.

假設一共有k個哈希函數.任意選擇1個參與方,如P1.P1用自己的份額構造長度為m的布隆過濾器.具體算法如下:

首先P1用哈希函數將自己的每個元素都進行仿射變換,得到n個因變量.

然后將這n個因變量作為布隆過濾器數組的自變量,并為每個因變量賦相應的隨機種子,這樣就實現了將彈性秘密共享生成的秘密份額分別放在自己集合元素映射到布隆過濾器位置的過程.

當插入1個元素到布隆過濾器中時,k個不同的哈希函數分別對該元素進行映射,所得到的k個結果的異或仍然為該元素.

同時,P1將該混淆布隆過濾器分解為n-1個子混淆布隆過濾器,滿足分解后的n-1個子混淆布隆過濾器的異或為原混淆布隆管理器.

隨后P1將n-1個子混淆布隆過濾器發給其余的參與方P2.

4) 份額收發.

在份額收發階段,參與者之間需要相互交換它們的份額,以便進行后續的計算操作.

通過異或秘密共享方案隱藏各個參與方的混淆布隆過濾器.

具體為:P2,P3,…,Pn運行1個異或秘密共享方案,并公開各自的秘密份額異或后的結果.每個參與方根據自己的秘密份額生成自己的布隆過濾器,并由此構造混淆布隆過濾器.

5) 交集計算.

利用彈性秘密共享能否重構出秘密判斷交集基數是否達到門限值.如果能達到重構值,即:交集數量達到門限值,則能夠輸出共享的秘密;否則,可以推斷出交集數量沒有達到門限值,協議終止.具體算法流程如下:

3 基于彈性秘密共享的多方洗牌協議的分析

3.1 正確性分析

如果交集數量達到門限值則能夠輸出共享的秘密;否則,可以推斷出交集數量沒有達到門限值,協議終止.

定理1.本文協議采用的彈性秘密共享滿足正確性.

當參與方P1,P2,…,Pn交集數量達到門限值t時,可以獲得足夠多的正確份額重構秘密s.彈性秘密共享能夠重構秘密需要滿足如下條件:

參與方元素的交集≥t+(n+d-t)/2.

這里的d為冗余碼的數量,n為參與方的集合元素的大小.引入冗余碼后,需要滿足

t+d=t+(n+d-t)/2,

因此d≥n+t.

因此協議的離線階段通過相同的隨機種子生成n-t個相同的偽元素.

當1個元素x是交集中的元素時P1通過元素x查詢混淆布隆過濾器可以得到.

因此,當交集數量達到門限值t時,可以獲得足夠多的秘密份額重構秘密s.本文提出的協議可以保證正確性.

定理2.本文協議采用的洗牌算法滿足正確性.

證明.洗牌算法的方法是通過數學歸納法,考慮洗牌算法在每次迭代中是否能夠產生1個等概率的排列.

假設在第i步之前已經產生了1個等概率的排列.

在第i步中,從剩余的元素中隨機選擇1個元素,并將其與第i個元素交換.這將生成另一個等概率的排列,因為每個元素都有相同的概率成為第i個元素.

當算法完成時將得到一個由原序列中的元素組成的等概率排列,因為每次都是從剩余的元素中隨機選擇1個元素來交換,而不是從已經交換過的元素中選擇.

因此,該洗牌算法的正確性可以得到證明:如果使用一個公平的隨機數生成器,那么該算法將產生一個等概率的排列.

證畢.

定理3.本文協議采用的布隆過濾器假陽性可能性很低,其潛在的誤差可以忽略不計.

假設需要處理的集合為{x1,x2,…,xn},存在k個m位的哈希函數.哈希函數將每個元素獨立且均勻地映射為隨機數.這是一個樂觀的假設,適合于實際實現.在這個假設下,在s的所有元素被散列到布隆過濾器后,某個特定位仍然為0的概率:

p′=(1-1/m)kn≈e-kn/m,

所以為了方便性,可以用p=e-kn/m來代替p′,則在p的前提條件下,假陽性的概率f為

f=(1-p)k≈(1-p′)k=(1-e-kn/m)k,

這個概率是很小的,故本文協議采用的布隆過濾器假陽性可能性很低,其潛在的誤差可忽略不計.

3.2 安全性分析

定理4.本文協議在半誠實模型中是安全的,可以抵抗合謀攻擊.

假設參與方pk是攻擊者,那么其進行如下攻擊操作:

首先選擇一個隨機值rand1和2n-t個自變量a1,a2,…,a2n-t,結合相應的因變量計算布隆過濾器Bk,并將其拆分為n-1份.

然后攻擊者Pk根據布隆過濾器Bk和交集I隨機且獨立地對布隆過濾器SBk進行采樣.最終,攻擊者Pk可以得到的信息為攻擊者Pk享有的秘密份額xk、交集I以及布隆過濾器SBk.

然而攻擊者Pk無法計算其余參與方的布隆過濾器,因為沒有其余參與方的秘密份額,同時也無法區別真實執行的和隨機生成的布隆過濾器.

在合謀攻擊中,攻擊者企圖獲取秘密s.誠實的參與者發送布隆過濾器給攻擊方后.布隆過濾器SBi是參與者Pi通過對布隆過濾器Bi和隨機數異或得到的.

由于秘密共享保證了隨機數和布隆過濾器的安全性.攻擊者無法區別真實執行的和隨機生成的布隆過濾器.所以攻擊者無法得到其余參與者的隱私信息,也無法確定協議真實的算法.故本文協議可以抵御合謀攻擊.

3.3 對比分析

本文協議還與其他基于秘密共享的洗牌協議進行了對比,具體如表2所示.

表2 本文協議與其他方案對比

本文協議所采用的洗牌算法的基本思想是從數組中隨機選擇1個元素,然后將它與數組的最后1個元素交換位置,依此類推,直到數組的第1個元素.因此洗牌算法的計算復雜度是線性的,即O(n).本文協議在生成布隆過濾器時的計算復雜度為O(nk),各方計算其布隆過濾器的計算復雜度與布隆過濾器的長度相關,為O(m).在秘密共享的重構階段,計算復雜度為O(nlogn).總體來說,本文協議的計算復雜度為O(n+nk+m+nlogn).

Cristofaro[26]提出了一種基于秘密共享的洗牌協議.該協議確保在洗牌過程中每個服務器和客戶端都只了解到洗牌結果的一部分.該方案具有較高的效率,但不能較好地抵御合謀攻擊.其構建哈希鏈的時間復雜度O(n),其中n是原始數據的大小.而哈希函數近似于O(1)的計算復雜度.故哈希鏈洗牌的計算復雜度為O(n+1).

Huang等人[25]提出了一種基于安全多方計算的洗牌協議.該協議允許參與方將其私有數據進行洗牌,可以抗合謀攻擊,但是在參與方數量增加時,計算復雜度會大幅度增加.該協議采用的洗牌算法的計算復雜度為O(n2),因為每次選擇和移除元素都需要線性時間.此外,該方法通常需要額外的空間存儲新的隨機排列數組.

4 應用前景分析

4.1 具體應用

本文提出的基于彈性秘密共享的洗牌協議在數據隱私保護方面具有一定的實用性,包括但不限于如下方面:

1) 彈性秘密共享和洗牌雙重保護數據共享.秘密共享協議將秘密分配給不同的參與方,洗牌協議隨機重組數據,以保護數據的隱私.解密需要各方協同重組消息.這種方案在醫療、金融等領域得到廣泛應用.

2) 協議支持多方下的安全計算.將參與方的數據進行隨機混淆和重組,并使用秘密共享協議將其分配給不同的參與方.最后,各方協同解密并重組數據.這種協議廣泛應用于機器學習等領域.

3) 協議應用于檢索和排序.將檢索和排序任務分配給多個參與方,各方將其擁有的數據進行洗牌處理,并使用秘密共享協議將其分配給其他參與方.

4.2 存在的問題

本文協議目前存在的一些問題主要有:

1) 秘密共享的計算復雜度略高.協議需要對數據進行多次處理,因此會增加數據處理的時間成本.

2) 隱私交集計算的通信開銷可進一步降低.洗牌協議和秘密共享需要對數據進行多次傳輸,因此會增加數據通信開銷.

3) 協議應用受到參與方個數的限制.洗牌協議和秘密共享需要多個參與方進行協同處理,因此會限制其在大規模數據處理中的應用.

5 結 語

本文提出一種基于彈性秘密共享的多方洗牌協議,充分利用了彈性秘密共享、洗牌協議等相關的密碼學技術.通過與相關協議對比,本文協議兼具實用性和安全性等特點,能夠很好地保護用戶數據隱私,有較好的應用前景.