一種去中心化的隱私保護匿名問卷方案

王元慶，劉百祥

（1.復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院上海市智能信息處理重點實驗室，上海 200433；2.上海市區(qū)塊鏈工程技術(shù)研究中心復(fù)旦?眾安區(qū)塊鏈與信息安全聯(lián)合實驗室，上海 200433）

0 概述

電子問卷允許研究機構(gòu)、政府部門及商業(yè)公司等問卷發(fā)起方以低成本向大量用戶收集問卷回應(yīng)，以了解用戶偏好、習(xí)慣或行為模式。近年來，用戶隱私備受重視，用戶期望數(shù)據(jù)隱私能被妥善保護，即問卷發(fā)起方需要取得用戶對其隱私保護能力的信任，這導(dǎo)致不知名機構(gòu)難以收集數(shù)據(jù)［1］。另外，問卷過程的非公開且不受監(jiān)管特性方便了一些惡意問卷發(fā)起方偽造或跨大問卷結(jié)果［2-3］，以取得較好的問卷統(tǒng)計數(shù)據(jù)，影響參考這些數(shù)據(jù)所得出的結(jié)論的有效性。而即使問卷發(fā)起方誠實可信，若惡意用戶可以偽造身份并多次回應(yīng)問卷，也無法保證問卷結(jié)果的真確性［4-5］。

ANONIZE［5］為目前最具代表性的安全匿名問卷系統(tǒng)，該系統(tǒng)基于零知識證明技術(shù)保證用戶匿名性及問卷驗證性，限制了只有問卷發(fā)起方選擇的用戶才可提交一次匿名回應(yīng)，但系統(tǒng)未關(guān)注各方合謀攻擊。系統(tǒng)委托問卷發(fā)起方生成用戶列表，即給予它選擇用戶的手段，它可與惡意用戶合謀，選擇某一誠實用戶與惡意用戶來發(fā)起問卷。誠實用戶若回應(yīng)問卷，合謀雙方即可對該回應(yīng)進行反匿名攻擊，也可以與注冊機構(gòu)合謀實行女巫攻擊，只選擇由注冊機構(gòu)虛構(gòu)并控制的用戶來發(fā)起問卷，以生成虛假的問卷過程與結(jié)果。

另外，問卷系統(tǒng)未關(guān)注對匿名回應(yīng)的公布，若回應(yīng)被公布，則會增加用戶隱私風(fēng)險。文獻［6］提出的統(tǒng)計手段可對網(wǎng)飛公司的匿名影評數(shù)據(jù)進行反匿名攻擊。然而若不要求問卷發(fā)起方公布回應(yīng)，則變相給予它數(shù)據(jù)造假的機會，可抵賴部分用戶回應(yīng)，以取得較好的問卷統(tǒng)計結(jié)果。對于公布數(shù)據(jù)時隱私保護的問題，文獻［7］提出一種隱私保護計算方案，引入多個計算服務(wù)器為數(shù)據(jù)密文進行歸總，但該方案未對數(shù)據(jù)的健壯性進行檢查，也未融合差分隱私技術(shù)，隱私保護程度較低。文獻［8］提出Prio 框架，以秘密共享非交互證明技術(shù)（SNIP）來保證用戶輸入的健壯性，但同樣未令歸總滿足差分隱私。文獻［9］提出PrivaDA 方案，以適用于定點與浮點數(shù)運算的安全多方計算，構(gòu)建了分布式差分隱私模型，但方案未對用戶輸入的健壯性進行檢查，存在輸入污染問題。文獻［10-11］方案兼顧了輸入健壯性及差分隱私保護，但它們的模型只有單個計算服務(wù)器，適用于智能電表等實時數(shù)據(jù)流的場景。

針對合謀攻擊的難題，本文提出一種去中心化的隱私保護匿名問卷方案。該方案引入多個問卷工作節(jié)點，組成一組少數(shù)合謀的計算服務(wù)器集群，利用門限簽名技術(shù)為用戶進行注冊，抵抗女巫攻擊，且以門限簽名為問卷生成用戶列表，抵抗反匿名攻擊。針對數(shù)據(jù)公布，將用戶回應(yīng)進行同態(tài)加密，把密文上傳至公開防篡改平臺抵抗數(shù)據(jù)抵賴，將所有同態(tài)密文歸總，委托問卷工作節(jié)點采用差分隱私技術(shù)與安全多方計算技術(shù)，輸出隱私保護的問卷歸總結(jié)果。

1 預(yù)備知識

1.1 雙線性映射

設(shè)G1、G2和GT為3 個階為素數(shù)p的乘法循環(huán)群。雙線性映射e：G1×G2→GT具有以下3 個性質(zhì)：

1）雙線性：對于任意u?G1，v?G2和任意a，b?Zp，有e（ua，vb）=e（u，v）ab。

2）非退化性：對于g1?G1，g2?G2，使e（g1，g2）≠1。

3）可計算性：對于任意u?G1，v?G2，e（u，v）可被某有效算法計算。

1.2 ElGamal 加密系統(tǒng)

ElGamal 加密系統(tǒng)［12］基于DDH 假設(shè)。設(shè)g為群G0的生成元，選擇a，b，c?RZp。DDH 假設(shè)代表（ga，gb，gab）的分布與（ga，gb，gc）的分布計算不可區(qū)分。ElGamal 加密系統(tǒng)算法如下：

1）Keygen（）：取私鑰x?RZp，對應(yīng)公鑰為h=gx。

2）Enc（m）：生 成（E1，E2）=（m˙hr，gr），其中r?RZp。

3）Dec（xE1，E2）：計算并得出m←E1（/E2）x。

1.3 加法同態(tài)加密和EC-based ElGamal 加密系統(tǒng)

同態(tài)加密技術(shù)使運算方可以在密文上進行運算，并保證將運算結(jié)果解密后的明文與直接在明文上進行運算的結(jié)果一致。加法同態(tài)加密提供加法運算符⊕，使得E（u）⊕E（v）=E（u+v）。本文方案使用基于橢圓曲線（EC-based）的ElGamal 加密系統(tǒng)［13］。設(shè)E為一Zp上的橢圓曲線，選擇E上一點P，選擇一個可逆線性函數(shù)f：m?Pm。具體算法如下：

1）Keygen（）：取私鑰x∈RZp，對應(yīng)公鑰為Y=xP。

2）Enc（m）：生成（E1，E2）=（（fm）+rY，rP），r?RZp。

3）Dec（xE1，E2）：計算Pm←E1－xE2，得m←f-（1Pm）。

EC-based ElGamal 加密系統(tǒng)的同態(tài)性質(zhì)為Enc（m1）+Enc（m2）=（（fm1）+r1Y+（fm2）+r2Y，r1P+r2P）=（f（m1+m2）+（r1+r2）Y，（r1+r2）P）=Enc（m1+m2），其 中，r1，r2?RZp。

1.4 門限秘密共享方案與門限簽名方案

設(shè)t、n為2 個正整數(shù)，其中t≤n。（t，n）門限秘密共享方案［14］讓n名參與者共享秘密，使得由任意k名參與者組成的子集能夠計算出該秘密當(dāng)且僅當(dāng)t≤k。本文使用一種簡單的（n，n）門限方案，以及使用Pedersen 的（t，n）門限方案［15］。設(shè)Zp為有限域，其中p為素數(shù)，且n≤p。2 種方案的具體算法如下：

1）（n，n）門限方案：設(shè)x?Zp為需要共享的秘密。任意選擇x1，x2，…，xn?RZp，但需滿足x1+x2+…+xn=x，然后將xi與第i名參與者分享。

2）Pedersen 門限方案：第i位參與者生成（t?1）階的多項 式函數(shù)p（ix）=a0，i+a1，ix+a2，ix2+…+at－1，ixt－1，其中ak，i?RZp，然后向其他n?1 名參與者的第j名參與者分享p（ij）。第i位參與者收到來自其他參與者的分享后計算。此時視為共享秘密，且每位參與者i擁有碎片yi。拉格朗日插值法保證可從任意t個碎片中得到，其中Ψi=。Pedersen 門限方案可與ElGamal 加密系統(tǒng)相結(jié)合，擴展基于ElGamal 加密系統(tǒng)的簽名方案至對應(yīng)的門限簽名方案［16］。本文使用基于PS 數(shù)字簽名方案［17］的門限簽名方案。

1.5 差分隱私與Laplace 機制

差分隱私［18］通過向數(shù)據(jù)加入噪音，使得每項數(shù)據(jù)的存在與否都不會對任意隨機查詢函數(shù)的輸出的概率分布產(chǎn)生有效影響。該技術(shù)可以抵御對數(shù)據(jù)集的背景知識攻擊，且可按需求調(diào)整抵御強度，以提高噪音為代價帶來高度的隱私保護。

定義1（ε-差分隱私）設(shè)D1和D2為2 個相鄰數(shù)據(jù)集，即它們只相異于1 項數(shù)據(jù)。隨機函數(shù)f滿足ε-差分隱私：

其中，Rf為f的所有可能輸出的集合。

定義2（敏感度）設(shè)d為一正整數(shù)，f：D→Rd為一函數(shù)。f的敏感度S（f）定義為：

其中，max 的范圍是D上所有相鄰數(shù)據(jù)集D1和D2。由此S（f）衡量任意一項數(shù)據(jù)的存在與否對f的輸出的最大改變。Laplace 機制［18］是一種可以令函數(shù)滿足ε-差分隱私的方法。它為函數(shù)的輸出加入來自分布函數(shù)形式為P(x)=1/2λ e-λ|x|的Laplace 分布Lap（λ）的噪音，其中λ ≥S(f)/ε。

1.6 安全多方計算

安全多方計算技術(shù)使分別持有秘密s1，s2，…，sn的n名參與者p1，p2，…，pn進行交互，共同計算出函數(shù)（fs1，s2，…，sn）的結(jié)果。其中SPDZ 協(xié)議［19］保證了多數(shù)惡意模型下的安全性，即攻擊者即使在控制了n?1 個參與者的情況下，也不能通過協(xié)議獲取誠實參與者的秘密。協(xié)議同時保證了計算的正確性，即若參與者遵循協(xié)議，則能夠計算出正確結(jié)果，否則協(xié)議終止。

1.7 零知識證明

零知識證明技術(shù)［20］的應(yīng)用場景涉及一個證明方和一個驗證方，其中證明方可以在不泄漏知識本身的情況下聲明他擁有某樣知識，并把該聲明的證明交予驗證方驗證。該技術(shù)保證驗證方從證明中只能學(xué)習(xí)到聲明的真確性。非交互零知識證明（NIZK）技術(shù)可使證明方在不與驗證方通信的情況下證明知識。對于關(guān)系R及語言L=｛x：?w，（x，w）?R｝的知識證明，其中，秘密w為知識，x為聲明。一般采用ZK｛w：x?L｝的形式描述零知識證明。在實際應(yīng)用中，一般使用Fiat-Shamir 啟發(fā)式與Σ 協(xié)議［20］來實例化一個NIZK。

2 去中心化隱私保護匿名問卷方案

如圖1 所示，本文方案共有3 組參與方，包括問卷工作節(jié)點（SWN）、問卷發(fā)起方（SA）和用戶（U）。

圖1 去中心化隱私保護匿名問卷方案模型Fig.1 Scheme model of decentralized privacy preserving anonymous surveying

本文方案主要有以下3 個部分組成：

1）問卷工作節(jié)點（SWN）負(fù)責(zé)維護性別、年齡、職業(yè)等用戶屬性，生成用戶令牌碎片，主要包含回應(yīng)令牌碎片的用戶列表分表、負(fù)責(zé)驗證回應(yīng)中的證明和公布隱私保護的結(jié)果。

2）問卷發(fā)起方（SA）是收集問卷的一方，負(fù)責(zé)發(fā)布問卷面向的用戶屬性、問卷題目及對應(yīng)的選項。

3）用戶（U）是問卷的回應(yīng)方，回應(yīng)包含問卷選擇密文、密文健壯性的證明以及擁有用戶令牌、回應(yīng)令牌的證明。

本文方案假設(shè)問卷工作節(jié)點間存在安全通信通道，且基于某公開防篡改的平臺，如以太坊區(qū)塊鏈［21］，并在平臺上發(fā)布問卷、提交回應(yīng)及公布問卷結(jié)果。圖1 中的步驟概括了方案的流程，對應(yīng)的描述如下：

1*）問卷工作節(jié)點根據(jù)Pedersen 門限方案，生成各自的（t，n）門限簽名的公私鑰對，根據(jù)（n，n）門限秘密共享方案，生成同態(tài)加密公鑰。

2）用戶向各問卷工作節(jié)點注冊，節(jié)點收集用戶屬性，驗證用戶身份，決定用戶令牌碎片的發(fā)放。

3）用戶收集任意t個碎片，組合成用戶令牌。

4）問卷發(fā)起方在平臺上發(fā)起問卷題目與選項，并確定問卷面向用戶的屬性。

5）各問卷工作節(jié)點根據(jù)問卷所列用戶屬性，為問卷生成包含回應(yīng)令牌碎片的用戶列表分表。

6）用戶收集任意t個碎片，組合成回應(yīng)令牌。

7）用戶回應(yīng)問卷，回應(yīng)包括選擇密文、密文健壯性的證明以及擁有用戶令牌、回應(yīng)令牌的證明。

8*）問卷工作節(jié)點驗證用戶回應(yīng)中各證明的正確性，通過驗證的回應(yīng)被視為有效。

9）結(jié)束問卷，問卷發(fā)起方同態(tài)歸總有效回應(yīng)。

10）問卷工作節(jié)點運行安全多方計算，解密回應(yīng)歸總，采用Laplace 機制，公布隱私保護的問卷結(jié)果。

2.1 本文方案模型

本文方案模型包括5 個階段，分別為初期設(shè)置、用戶注冊、問卷發(fā)布、問卷收集及問卷結(jié)果公布。以下對各階段的算法進行形式化定義：

1）Setup（1λ）→（PK，｛Ai｝I，A）。由問卷工作節(jié)點｛SWNi｝i執(zhí)行，生成同態(tài)加密公鑰PK、｛SWNi｝i的門限簽名公鑰｛Ai｝i和對應(yīng)的分布式公鑰A。

2）Reg（id，｛attrk｝k，sid）→σU。由用戶U 與各SWNi交互執(zhí)行。U 以身份id、屬性｛attrk｝k和秘密sid向所有SWNi注冊，收集至少t個用戶令牌碎片，最后組成用戶令牌σU。

3）Survey（）→（Q，｛Mj｝j，｛Li｝i）。由問卷發(fā)起方SA 和各SWNi執(zhí)行，SA 生成問卷Q和選擇｛Mj｝j，各SWNi生成用戶列表分表Li。

4）Submit（id，sid，｛mj｝j，σU，｛Li｝i）→RU。由U 執(zhí)行，算法中U 以公鑰PK 同態(tài)加密問卷選擇｛mj｝j，提供密文健壯性的證明。另從｛Li｝i收集t個回應(yīng)令牌碎片，組成回應(yīng)令牌σid。再以身份id、秘密sid提供持有用戶令牌σU和回應(yīng)令牌σid的證明。最后組合密文和各證明，形成回應(yīng)RU。

5）Announce（｛xi｝I，｛RU｝U，ε）→｛Oj，d｝j，d。由｛SWNi｝i和SA 執(zhí)行。｛SWNi｝i確認(rèn)所有用戶回應(yīng)RU的有效性，SA 同態(tài)歸總所有有效回應(yīng)中的問卷選擇密文。｛SWNi｝i運行多方安全計算，解密同態(tài)歸總，為歸總加入噪音，輸出隱私保護的問卷結(jié)果｛Oj，d｝j，d。

2.2 安全模型

本節(jié)構(gòu)建方案的安全模型，描述在安全模型下本文方案的特性。

1）問卷工作節(jié)點集群只有少數(shù)合謀的惡意單位，它們會在各階段不遵循方案流程并采取各種攻擊。雖可在現(xiàn)實中監(jiān)管節(jié)點，但不排除少數(shù)節(jié)點受攻擊者控制。其他多數(shù)節(jié)點為誠實但好奇的單位，它們遵循方案流程，但好奇流程中的數(shù)據(jù)密文。方案委托問卷工作節(jié)點驗證用戶回應(yīng)的有效性，回應(yīng)為公開可驗證的，因此假設(shè)節(jié)點會正確地驗證回應(yīng)。

2）問卷發(fā)起方是惡意的。為提高問卷參與率及提高問卷結(jié)果的顯著性，會嘗試復(fù)制、篡改、抵賴或偽造用戶回應(yīng)。

3）用戶是惡意的。在一些有回應(yīng)獎勵的問卷中，它們會嘗試多次提交回應(yīng)和提交無效回應(yīng)。

2.2.1 匿名性

匿名性要求用戶的回應(yīng)過程及回應(yīng)數(shù)據(jù)不包含用戶身份的知識，在此特性下無法關(guān)聯(lián)用戶身份與回應(yīng)。具體而言，若有2 名用戶分別提交了2 個回應(yīng)，任意擁有多項式時間算力（PPT）的敵手都不能構(gòu)造出優(yōu)于猜測的算法來關(guān)聯(lián)身份與回應(yīng)。參考ANONIZE 的匿名性定義，以敵手A 和挑戰(zhàn)者C 間的游戲描述匿名性的要求。游戲中敵手A 控制SA 和｛SWNi｝i中少數(shù)節(jié)點，且可隨意虛構(gòu)新用戶提交回應(yīng)，即A 擁有預(yù)言機Submit 的訪問權(quán)。唯一限制是對于C 所構(gòu)造的用戶id，A 不能訪問Submit（id，-）。

1）A 與｛SWNi｝i中多數(shù)節(jié)點執(zhí)行Setup（1λ）。C構(gòu)造身份為id0和id1的用戶U0和U1，使U0和U1與｛SWNi｝i交互執(zhí)行Reg（idk，-，（sid）k）→（σU）k。

2）A 與｛SWNi｝i中多數(shù)節(jié)點執(zhí)行Survey（）→（Q，｛Mj｝j，｛Li｝i），使得｛Li｝i中有至少t個U0和U1回應(yīng)令牌碎片。C 生成m0、m1，選擇挑戰(zhàn)b←｛0，1｝，對于k=0和1，執(zhí)行Submit（idk，（sid）k，mk⊕b，｛Li｝i）→（RU）k⊕b。C 未對mk⊕b加密，在無機密性的情況下滿足匿名性。

3）A 可訪問Submit（id，-），但id?｛id0，id1｝。

4）A 輸出b’←｛0，1｝。若b’=b，則A 勝出。

定義3（匿名性）方案滿足匿名性，當(dāng)對于任意PPT 的敵手A，有|Pr[Awins]-1/2|≤negl(λ)，其 中，negl 為可忽略函數(shù)，λ為安全參數(shù)。

2.2.2 驗證性

驗證性要求只有在用戶列表分表中有至少t個回應(yīng)令牌碎片的用戶才可能提交有效回應(yīng)，也要求每個回應(yīng)對用戶的唯一性，即在匿名性的情況下仍可檢測到用戶提交多個回應(yīng)。以下以游戲定義驗證性，游戲中敵手A 控制SA 和｛SWNi｝i中少數(shù)節(jié)點。

1）A 與｛SWNi｝i中多數(shù)節(jié)點執(zhí)行Setup（1λ）。C選擇用戶屬性attr。

2）A 可以訪問預(yù)言機Reg（id，attr，sid）→σU來注冊擁有屬性attr 的用戶不多于p（λ）次，其中p為多項式函數(shù)。A 可以訪問預(yù)言機Reg（id，｛attrk｝k，sid）→σU不多于p（λ）次，其中attr?｛attrk｝k。

3）A 與｛SWNi｝i中多數(shù)節(jié)點執(zhí)行Survey（）→（Q，｛Mj｝j，｛Li｝i），其中多數(shù)節(jié)點的Li包含U 的回應(yīng)令牌碎片當(dāng)且僅當(dāng)U 擁有屬性attr。

4）A 可輸出RU←Submit（id，sid，｛mj｝j，σU，｛Li｝i）不多于2p（λ）次。

5）C 驗證所有回應(yīng)｛RU｝U。設(shè)R為所有有效回應(yīng)，L為某多數(shù)節(jié)點的Li。若|R|>|L|，則A 勝出。

定義4（驗證性）方案滿足驗證性，對于任意PPT 的敵手A，有Pr[A wins]≤negl(λ)。

2.2.3 機密性

機密性要求用戶的回應(yīng)過程及回應(yīng)數(shù)據(jù)不包含問卷選擇明文的知識，在此特性下無法得知回應(yīng)的問卷選擇?；貞?yīng)發(fā)布在公開平臺上，若不能保密回應(yīng)的選擇，即使?jié)M足匿名性，也難以抵抗統(tǒng)計手段的反匿名攻擊，因此機密性在方案中尤其重要。

機密性的定義類似于匿名性，區(qū)別在于C 只控制一個用戶U0，只執(zhí)行Submit（id0，（sid）0，mb，σU，｛Li｝i）→（RU）b一 次，但對mb加密。設(shè)該游戲為Game’。

定義5（機密性）方案滿足機密性，任意PPT 的敵手A 在Game’中勝出的概率小于1/2+negl（λ）。

2.2.4 隱私保護

隱私保護保證問卷回應(yīng)的歸總滿足ε-差分隱私。方案在安全多方計算協(xié)議中為歸總加入噪音，為此給出符合場景的f-隱私［22］定義。

定義6（f-隱私）給定任意一個計算函數(shù)f的安全多方計算協(xié)議Π，假設(shè)協(xié)議Π 共有s個計算方，在其中有不多于s?1 個惡意計算方時，函數(shù)f的計算滿足f-隱私，當(dāng)存在一個以協(xié)議的公共參數(shù)P、惡意方集合I、能查詢惡意方的預(yù)言機O與函數(shù)輸出y=f（s1，s2，…，sn）作為輸入的模擬器SI，且該模擬器可模擬協(xié)議中惡意方的計算的過程，使得模擬過程的分布與真正在協(xié)議中計算過程的分布不可區(qū)分，即｛S（IP，I，O，y）｝≡｛VIEWΠ（I）｝。

下文給出符合多工作節(jié)點場景下的不可區(qū)分性的ε-分布式差分隱私（ε-IND-DDP）定義［9，22］。

定義7（ε-IND-DDP）假設(shè)VΠ為協(xié)議Π 所有可能的過程的集合。涉及多數(shù)惡意計算方I的模型下的協(xié)議Π 所執(zhí)行的函數(shù)f滿足ε-IND-DDP，對于任意相鄰數(shù)據(jù)集D1和D2，以及任意過程V?VΠ，有Pr[(I)?V]≤eεPr[VIEWΠ(D2)(I)?V]+negl(λ)。

3 方案設(shè)計

設(shè)安全參數(shù)為λ。假設(shè)共有n個問卷工作節(jié)點｛SWN｝ii。方案為少數(shù)合謀模型，設(shè)定門限為t=n/2+1，采用SPDZ 安全多方計算協(xié)議。根據(jù)Elgamal同態(tài)加密方案，采用PS 數(shù)字簽名方案。PS 數(shù)字簽名方案包含以下3 個算法：

1）Keygen（）：生成密鑰sk=（x，y）與公鑰pk=（X，Y）=，其中g(shù)2?G2。

2）Sign（sk，m）：生成σ←（h，hx+ym），其中h?RG1。

3）Verfp（kσ，m）：檢查

3.1 初期設(shè)置階段

3）｛SWN｝ii以SMPC 運行算法1，生成并公布同態(tài)加密公鑰PK，且秘密共享私鑰SK。

算法1公私鑰生成算法

3.2 用戶注冊階段

3.3 問卷發(fā)布階段

3.4 問卷收集階段

3.5 問卷結(jié)果公布階段

算法2隱私保護算法

4 安全性分析

本節(jié)分析方案在匿名性、驗證性、機密性及隱私保護方面的安全性，并討論對合謀攻擊的抵御。

4.1 匿名性

定理1當(dāng)ZK 滿足零知識特性，以及偽隨機函數(shù)滿足偽隨機特性時，方案滿足匿名性。

證明游戲中對于k?｛0，1｝，C 給與A 回應(yīng)（RU）k⊕b=（mk⊕b，（πm）k⊕b，（πid）k⊕b，Ck⊕b），其中C 未對mk⊕b加密。而A 可訪問Submit，若A 能輸出b’使得b’=b，則A 勝出。設(shè)該游戲為Game0，現(xiàn)考慮新游戲Game1。Game1與Game0的區(qū)別在于回應(yīng)中的（πm）k⊕b，（πid）k⊕b被一模擬器所模擬。ZK 的零知識特性保證該模擬器可在無秘密的情況下模擬（πm）k⊕b和（πid）k⊕b，使得模擬器的輸出（πm）*、（πid）*與（πm）k⊕b、（πid）k⊕b不可區(qū)分。因此，Game1 將證明換成（πm）*、（πid）*后，A 在游戲中的勝率不會發(fā)生不可忽略的變化?，F(xiàn)考慮新游戲Game2，Game2 與Game1 的區(qū)別在于以隨機函數(shù)替代偽隨機函數(shù)來生成回應(yīng)中的Ck⊕b。根據(jù)偽隨機函數(shù)的偽隨機特性，生成的Ck⊕b與相同長度的隨機字符串str*不可區(qū)分。因此，Game2將Ck⊕b換成str*后，與Game1相比A的勝率不會發(fā)生不可忽略的變化。在Game2 中，C 給A 的回應(yīng)（RU）k⊕b=（mk⊕b，（πm）*，（πid）*，str*），除mk⊕b外的所有信息都與b無關(guān)。因此，A 在Game2 中沒有優(yōu)于猜測的算法來選擇b’使得b’=b。又因為Game2 和Game0 中A 的勝率的差異可被忽略，所以A 在Game0 中的勝率為1/2+neg（lλ），因此方案滿足匿名性。

4.2 驗證性

定理2當(dāng)ZK 滿足正確性和知識證明特性，以及門限簽名方案滿足不可偽造特性時，方案滿足驗證性。

證明以U?L表示用戶U 擁有身份id 且滿足|{i：σi,id?Li}|≥t。假設(shè)存在敵手A*可以不可忽略的概率勝出游戲，代表A*可以不可忽略的概率達成以下至少一個條件，以使得|R|>|L|。

1）A*控制的某名用戶U∈L提交了2 個回應(yīng)（RU）k=（（｛EU，j，d｝j，d）k，（πm）k，（πid）k，Ck），其中k=｛0，1｝，但C0≠C1。2 個回應(yīng)都通過了對C 的驗證。

2）A*控制的某名用戶U?L提交回應(yīng)RU=（｛EU，j，d｝j，d，πm，πid，C）并通過了對C 的驗證。

條 件1 中C0≠C1，即至少一個Cx是錯誤的且。但（RU）x通過了驗證，即（πid）x被判斷為正確。ZK 的正確特性保證此情況出現(xiàn)的概率可忽略，所以A*達成條件1 的概率可忽略。

條件2 中U?L但提交的回應(yīng)RU通過了驗證，即πid被判斷為正確。ZK 的知識證明特性保證存在一個抽取器，抽取器可以壓倒性的概率抽取出πid的知識，包括身份id、秘密sid和簽名σU、σid。但因為U?L，即|{i：σi,id?Li}|

因為A*可達成條件1 或條件2 的概率皆可忽略，根據(jù)反證法，證明了A*不存在，因此方案滿足驗證性。

4.3 機密性

定理3方案滿足機密性，當(dāng)ZK 滿足零知識特性和加密方案時滿足CPA 安全。

證明游戲Game’中C給與A回應(yīng)（RU0）b=（Eb，（πm）b，（πid）0，（C）0），其中假設(shè)問卷問題數(shù)j=1 且問題選擇數(shù)d1=1，所以Eb的明文mb的值為0 或1，但m0≠m1。而A 可訪問Submit，若A 能輸出b′使得b′=b，則A 勝出?，F(xiàn)考慮新游戲Game1’，Game1’與Game’的區(qū)別在于回應(yīng)中（πm）b被模擬器所模擬。ZK 的零知識特性保證模擬器輸出的（πm）*與（πm）b不可區(qū)分。因此，Game1’在將（πm）b換成（πm）*后，A 在游戲中的勝率不會發(fā)生不可忽略的變化。在Game1’中，C給A的回應(yīng)（RU0）b=（Eb，（πm）*，（πid）0，（C）0），除Eb外的所有信息都與b無關(guān)，即A 需要確定Eb的明文為m0還是m1。加密方案的CPA 安全特性保證A 的勝率不高于1/2+neg（lλ）。又因為Game1’和Game’中A的勝率的差異可被忽略，所以A在Game’中的勝率不高于1/2+neg（lλ），因此方案滿足機密性。

4.4 隱私保護

定理4方案滿足ε-IND-DDP，安全多方計算協(xié)議保證計算的正確性且滿足f-隱私。

證明方案采用的SPDZ 安全多方計算協(xié)議已被文獻［19］證明滿足f-隱私，即存在可模擬惡意方計算過程的模擬器，以此保證協(xié)議在多數(shù)惡意模型下惡意計算方無法獲取誠實方的輸入。同時，SPDZ協(xié)議滿足正確性，即若協(xié)議正常結(jié)束，則協(xié)議只能以可忽略的概率輸出錯誤計算結(jié)果。所以，正確性保證了協(xié)議的正常輸出是由Laplace 機制在歸總上正確地執(zhí)行后所生成，且f-隱私保證了惡意計算方無法獲取有關(guān)歸總及Laplace 噪音的信息。因此，由采用Laplace 機制所達成的ε-差分隱私令協(xié)議所執(zhí)行的函數(shù)滿足ε-IND-DDP。

4.5 合謀攻擊抵御

合謀攻擊抵御有以下2 種方法：

1）反匿名攻擊。在ANONIZE 中敵手有選擇用戶的手段，可以繞開匿名性保護，因為定義只要求敵手無法分辨來自2 名誠實用戶的2 個回應(yīng)。本文方案中敵手無法選擇用戶，只能表明問卷面向的用戶屬性，由多數(shù)問卷工作節(jié)點決策最終用戶列表。而即使在極端情況下，問卷列表只包含某一誠實用戶與惡意用戶的回應(yīng)令牌，本文方案的機密性保護誠實用戶的問卷選擇，隱私保護特性保護用戶的選擇無法從差分隱私歸總中被推導(dǎo)出，所以本文方案能夠抵御反匿名攻擊。

2）女巫攻擊。本文方案中敵手只控制少數(shù)工作節(jié)點，敵手虛構(gòu)的用戶無法通過多數(shù)節(jié)點的身份驗證，不能得到至少t個用戶令牌碎片，因此無法以虛構(gòu)的用戶提交有效回應(yīng)。

5 性能分析

本節(jié)對比分析本文方案與文獻［5］、文獻［8］及文獻［9］方案的性能，然后對本文方案進行仿真實驗，各方案的性能對比如表1 所示。

表1 不同方案的性能對比Table1 Performance comparison of different schemes

從表1 可以看出，ANONIZE 方案的架構(gòu)是中心化的，只有一個注冊機構(gòu)（RA），且安全模型中所有角色都為惡意單位，所以它無法抵御RA 的女巫攻擊及SA的反匿名攻擊。而本文方案采用去中心化的架構(gòu)，且問卷工作節(jié)點集群的安全模型為少數(shù)合謀，以門限簽名抵御合謀攻擊。ANONIZE 方案構(gòu)成了單點信任的需求。若要信任問卷結(jié)果，需假設(shè)問卷發(fā)起方?jīng)]有抵賴數(shù)據(jù)，已過濾無效的數(shù)據(jù)，及歸總數(shù)據(jù)時沒有引入污染。本文方案不需單點信任，防篡改平臺可抵抗數(shù)據(jù)抵賴，節(jié)點基于多方安全計算，在解密歸總時加入適當(dāng)?shù)腖aplace 噪音，保證結(jié)果不被污染。PrivaDA 和Prio是去中心化的，同樣不需要單點信任。Prio 在歸總過程中未加入Laplace 噪音，隱私保護程度低。PrivaDA未考慮數(shù)據(jù)健壯性的驗證，無法抵抗數(shù)據(jù)污染。Prio的SNIP 協(xié)議需要向每個工作節(jié)點發(fā)送秘密共享證明，證明總長度為O（nd），其中，n為節(jié)點數(shù)量，d為輸入長度。本文方案只需上傳長度為O（d）的NIZK 至公開平臺以供驗證。PrivaDA 和Prio中用戶與節(jié)點秘密共享數(shù)據(jù)，需假設(shè)節(jié)點不會拒收碎片，本文方案中防篡改平臺保證用戶數(shù)據(jù)不被抵賴。

仿真實驗使用了AWS 上類型為t2-large 的EC2機器，配置為3.0 GHz 的Intel CPU 處理器和8 GB 的內(nèi)存，環(huán)境為64 位的Ubuntu 16.04。實驗使用C 語言v0.5.14 版本的PBC 庫進行方案各階段的雙線性密碼運算，同時使用支持SPDZ 安全多方計算協(xié)議的SCALE-MAMBA 庫進行算法部分（算法1 和算法2）的運算。

實驗?zāi)M方案有N=100 個用戶與n=3 個問卷工作節(jié)點的場景，其中簽名的門限為t=2，問卷的題目數(shù)為Q=10，題目的選擇數(shù)為D=4，差分隱私參數(shù)ε=1。表2為對方案各階段運算100 次的平均計算時間開銷和數(shù)據(jù)存儲開銷?？梢钥闯?，以SMPC 運行的算法部分時間開銷較其他階段高，其中運行算法1 前需進入SMPC時間開銷最高的預(yù)處理階段，生成隨機參數(shù)，以供算法1和算法2 的線上運行階段使用。SMPC 的運算不需用戶參與，因此對實時性的要求不高，實驗中算法部分的時間開銷為秒至分鐘級別，符合實際應(yīng)用的需求。

表2 方案各階段的時間和存儲開銷Table 2 Time and storage costs of each stage in the scheme

表2 列出了算法各階段理論上的計算開銷，其中，E表示群上指數(shù)運算耗時，P表示雙線性配對運算耗時，H表示哈希運算耗時。在問卷發(fā)布階段，假設(shè)所有用戶都能參與問卷，所以每個節(jié)點都生成N個回應(yīng)令牌碎片。在問卷收集階段，每個用戶需在各個長度為N的令牌碎片列表中找出t個可用的碎片，因此平均需遍歷并比對tN/2 個碎片。而在問卷結(jié)果階段，節(jié)點共同檢查回應(yīng)中的零知識證明，即平均每個節(jié)點需處理N/n個回應(yīng)。實驗需檢查零知識證明的問卷結(jié)果公布階段耗時較高，但此階段由節(jié)點負(fù)責(zé)，不影響系統(tǒng)對用戶的響應(yīng)。對實時性要求較高的為用戶注冊及問卷收集階段，其中用戶注冊階段忽略網(wǎng)絡(luò)的開銷需0.041 7 s，問卷收集階段主要耗時在找出可用碎片以組成回應(yīng)令牌，此過程平均需1.575 s，加上構(gòu)造零知識證明的耗時共需2.18 s，可滿足用戶使用需求。在存儲開銷方面，初期設(shè)置與問卷結(jié)果公布階段只需少量存儲，且與用戶數(shù)N無關(guān)。問卷發(fā)布與問卷收集階段平均對每個用戶的存儲開銷為0.774 KB 和27.452 KB，適合于區(qū)塊鏈等公開平臺上存儲的量級。

圖2 為問卷發(fā)布階段及問卷收集階段的時間開銷隨用戶數(shù)變化的數(shù)據(jù)。從圖2 可以看出，時間開銷隨用戶數(shù)的線性增長較為緩慢，即使在用戶數(shù)為5 000 時的大型問卷中，問卷發(fā)布階段中各節(jié)點需33 s 完成回應(yīng)令牌碎片的生成，而用戶在問卷收集階段中需79 s找出可用碎片以生成回應(yīng)令牌，即用戶從問卷發(fā)布至確認(rèn)可以進行問卷回應(yīng)前的延遲約為2 min，可見方案在大型問卷中具備較好的實用性。

圖2 多用戶場景下主要階段的時間開銷Fig.2 Time cost of the main stages in multi-user scenario

6 結(jié)束語

本文基于門限簽名方案和差分隱私技術(shù)，提出一種去中心化的隱私保護的匿名問卷方案。采用同態(tài)加密技術(shù)為回應(yīng)加密，將密文上傳至公開防篡改平臺抵抗數(shù)據(jù)抵賴，借助安全多方計算技術(shù)使差分隱私歸總過程安全，并融入零知識證明技術(shù)保證方案的正確性。實驗結(jié)果表明，該方案的時間和存儲開銷符合實際應(yīng)用需求，在大型問卷中具有較好的實用性。下一步將研究本文方案在以太坊等區(qū)塊鏈平臺上部署時需要面對的挑戰(zhàn)，包括安全多方計算協(xié)議和智能合約的集成問題。