一种去中心化的隐私保护匿名问卷方案

王元庆，刘百祥

（1.复旦大学计算机科学技术学院上海市智能信息处理重点实验室，上海 200433；2.上海市区块链工程技术研究中心复旦−众安区块链与信息安全联合实验室，上海 200433）

0 概述

电子问卷允许研究机构、政府部门及商业公司等问卷发起方以低成本向大量用户收集问卷回应，以了解用户偏好、习惯或行为模式。近年来，用户隐私备受重视，用户期望数据隐私能被妥善保护，即问卷发起方需要取得用户对其隐私保护能力的信任，这导致不知名机构难以收集数据［1］。另外，问卷过程的非公开且不受监管特性方便了一些恶意问卷发起方伪造或跨大问卷结果［2-3］，以取得较好的问卷统计数据，影响参考这些数据所得出的结论的有效性。而即使问卷发起方诚实可信，若恶意用户可以伪造身份并多次回应问卷，也无法保证问卷结果的真确性［4-5］。

ANONIZE［5］为目前最具代表性的安全匿名问卷系统，该系统基于零知识证明技术保证用户匿名性及问卷验证性，限制了只有问卷发起方选择的用户才可提交一次匿名回应，但系统未关注各方合谋攻击。系统委托问卷发起方生成用户列表，即给予它选择用户的手段，它可与恶意用户合谋，选择某一诚实用户与恶意用户来发起问卷。诚实用户若回应问卷，合谋双方即可对该回应进行反匿名攻击，也可以与注册机构合谋实行女巫攻击，只选择由注册机构虚构并控制的用户来发起问卷，以生成虚假的问卷过程与结果。

另外，问卷系统未关注对匿名回应的公布，若回应被公布，则会增加用户隐私风险。文献［6］提出的统计手段可对网飞公司的匿名影评数据进行反匿名攻击。然而若不要求问卷发起方公布回应，则变相给予它数据造假的机会，可抵赖部分用户回应，以取得较好的问卷统计结果。对于公布数据时隐私保护的问题，文献［7］提出一种隐私保护计算方案，引入多个计算服务器为数据密文进行归总，但该方案未对数据的健壮性进行检查，也未融合差分隐私技术，隐私保护程度较低。文献［8］提出Prio 框架，以秘密共享非交互证明技术（SNIP）来保证用户输入的健壮性，但同样未令归总满足差分隐私。文献［9］提出PrivaDA 方案，以适用于定点与浮点数运算的安全多方计算，构建了分布式差分隐私模型，但方案未对用户输入的健壮性进行检查，存在输入污染问题。文献［10-11］方案兼顾了输入健壮性及差分隐私保护，但它们的模型只有单个计算服务器，适用于智能电表等实时数据流的场景。

针对合谋攻击的难题，本文提出一种去中心化的隐私保护匿名问卷方案。该方案引入多个问卷工作节点，组成一组少数合谋的计算服务器集群，利用门限签名技术为用户进行注册，抵抗女巫攻击，且以门限签名为问卷生成用户列表，抵抗反匿名攻击。针对数据公布，将用户回应进行同态加密，把密文上传至公开防篡改平台抵抗数据抵赖，将所有同态密文归总，委托问卷工作节点采用差分隐私技术与安全多方计算技术，输出隐私保护的问卷归总结果。

1 预备知识

1.1 双线性映射

设G1、G2和GT为3 个阶为素数p的乘法循环群。双线性映射e：G1×G2→GT具有以下3 个性质：

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 加密系统

ElGamal 加密系统［12］基于DDH 假设。设g为群G0的生成元，选择a，b，c∊RZp。DDH 假设代表（ga，gb，gab）的分布与（ga，gb，gc）的分布计算不可区分。ElGamal 加密系统算法如下：

1）Keygen（）：取私钥x∊RZp，对应公钥为h=gx。

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

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

1.3 加法同态加密和EC-based ElGamal 加密系统

同态加密技术使运算方可以在密文上进行运算，并保证将运算结果解密后的明文与直接在明文上进行运算的结果一致。加法同态加密提供加法运算符⊕，使得E（u）⊕E（v）=E（u+v）。本文方案使用基于椭圆曲线（EC-based）的ElGamal 加密系统［13］。设E为一Zp上的椭圆曲线，选择E上一点P，选择一个可逆线性函数f：m↦Pm。具体算法如下：

1）Keygen（）：取私钥x∈RZp，对应公钥为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 加密系统的同态性质为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 门限秘密共享方案与门限签名方案

设t、n为2 个正整数，其中t≤n。（t，n）门限秘密共享方案［14］让n名参与者共享秘密，使得由任意k名参与者组成的子集能够计算出该秘密当且仅当t≤k。本文使用一种简单的（n，n）门限方案，以及使用Pedersen 的（t，n）门限方案［15］。设Zp为有限域，其中p为素数，且n≤p。2 种方案的具体算法如下：

1）（n，n）门限方案：设x∊Zp为需要共享的秘密。任意选择x1，x2，…，xn∊RZp，但需满足x1+x2+…+xn=x，然后将xi与第i名参与者分享。

2）Pedersen 门限方案：第i位参与者生成（t−1）阶的多项 式函数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 加密系统相结合，扩展基于ElGamal 加密系统的签名方案至对应的门限签名方案［16］。本文使用基于PS 数字签名方案［17］的门限签名方案。

1.5 差分隐私与Laplace 机制

差分隐私［18］通过向数据加入噪音，使得每项数据的存在与否都不会对任意随机查询函数的输出的概率分布产生有效影响。该技术可以抵御对数据集的背景知识攻击，且可按需求调整抵御强度，以提高噪音为代价带来高度的隐私保护。

定义1（ε-差分隐私）设D1和D2为2 个相邻数据集，即它们只相异于1 项数据。随机函数f满足ε-差分隐私：

其中，Rf为f的所有可能输出的集合。

定义2（敏感度）设d为一正整数，f：D→Rd为一函数。f的敏感度S（f）定义为：

其中，max 的范围是D上所有相邻数据集D1和D2。由此S（f）衡量任意一项数据的存在与否对f的输出的最大改变。Laplace 机制［18］是一种可以令函数满足ε-差分隐私的方法。它为函数的输出加入来自分布函数形式为P(x)=1/2λ e-λ|x|的Laplace 分布Lap（λ）的噪音，其中λ ≥S(f)/ε。

1.6 安全多方计算

安全多方计算技术使分别持有秘密s1，s2，…，sn的n名参与者p1，p2，…，pn进行交互，共同计算出函数（fs1，s2，…，sn）的结果。其中SPDZ 协议［19］保证了多数恶意模型下的安全性，即攻击者即使在控制了n−1 个参与者的情况下，也不能通过协议获取诚实参与者的秘密。协议同时保证了计算的正确性，即若参与者遵循协议，则能够计算出正确结果，否则协议终止。

1.7 零知识证明

零知识证明技术［20］的应用场景涉及一个证明方和一个验证方，其中证明方可以在不泄漏知识本身的情况下声明他拥有某样知识，并把该声明的证明交予验证方验证。该技术保证验证方从证明中只能学习到声明的真确性。非交互零知识证明（NIZK）技术可使证明方在不与验证方通信的情况下证明知识。对于关系R及语言L=｛x：∃w，（x，w）∊R｝的知识证明，其中，秘密w为知识，x为声明。一般采用ZK｛w：x∊L｝的形式描述零知识证明。在实际应用中，一般使用Fiat-Shamir 启发式与Σ 协议［20］来实例化一个NIZK。

2 去中心化隐私保护匿名问卷方案

如图1 所示，本文方案共有3 组参与方，包括问卷工作节点（SWN）、问卷发起方（SA）和用户（U）。

图1 去中心化隐私保护匿名问卷方案模型Fig.1 Scheme model of decentralized privacy preserving anonymous surveying

本文方案主要有以下3 个部分组成：

1）问卷工作节点（SWN）负责维护性别、年龄、职业等用户属性，生成用户令牌碎片，主要包含回应令牌碎片的用户列表分表、负责验证回应中的证明和公布隐私保护的结果。

2）问卷发起方（SA）是收集问卷的一方，负责发布问卷面向的用户属性、问卷题目及对应的选项。

3）用户（U）是问卷的回应方，回应包含问卷选择密文、密文健壮性的证明以及拥有用户令牌、回应令牌的证明。

本文方案假设问卷工作节点间存在安全通信通道，且基于某公开防篡改的平台，如以太坊区块链［21］，并在平台上发布问卷、提交回应及公布问卷结果。图1 中的步骤概括了方案的流程，对应的描述如下：

1*）问卷工作节点根据Pedersen 门限方案，生成各自的（t，n）门限签名的公私钥对，根据（n，n）门限秘密共享方案，生成同态加密公钥。

2）用户向各问卷工作节点注册，节点收集用户属性，验证用户身份，决定用户令牌碎片的发放。

3）用户收集任意t个碎片，组合成用户令牌。

4）问卷发起方在平台上发起问卷题目与选项，并确定问卷面向用户的属性。

5）各问卷工作节点根据问卷所列用户属性，为问卷生成包含回应令牌碎片的用户列表分表。

6）用户收集任意t个碎片，组合成回应令牌。

7）用户回应问卷，回应包括选择密文、密文健壮性的证明以及拥有用户令牌、回应令牌的证明。

8*）问卷工作节点验证用户回应中各证明的正确性，通过验证的回应被视为有效。

9）结束问卷，问卷发起方同态归总有效回应。

10）问卷工作节点运行安全多方计算，解密回应归总，采用Laplace 机制，公布隐私保护的问卷结果。

2.1 本文方案模型

本文方案模型包括5 个阶段，分别为初期设置、用户注册、问卷发布、问卷收集及问卷结果公布。以下对各阶段的算法进行形式化定义：

1）Setup（1λ）→（PK，｛Ai｝I，A）。由问卷工作节点｛SWNi｝i执行，生成同态加密公钥PK、｛SWNi｝i的门限签名公钥｛Ai｝i和对应的分布式公钥A。

2）Reg（id，｛attrk｝k，sid）→σU。由用户U 与各SWNi交互执行。U 以身份id、属性｛attrk｝k和秘密sid向所有SWNi注册，收集至少t个用户令牌碎片，最后组成用户令牌σU。

3）Survey（）→（Q，｛Mj｝j，｛Li｝i）。由问卷发起方SA 和各SWNi执行，SA 生成问卷Q和选择｛Mj｝j，各SWNi生成用户列表分表Li。

4）Submit（id，sid，｛mj｝j，σU，｛Li｝i）→RU。由U 执行，算法中U 以公钥PK 同态加密问卷选择｛mj｝j，提供密文健壮性的证明。另从｛Li｝i收集t个回应令牌碎片，组成回应令牌σid。再以身份id、秘密sid提供持有用户令牌σU和回应令牌σid的证明。最后组合密文和各证明，形成回应RU。

5）Announce（｛xi｝I，｛RU｝U，ε）→｛Oj，d｝j，d。由｛SWNi｝i和SA 执行。｛SWNi｝i确认所有用户回应RU的有效性，SA 同态归总所有有效回应中的问卷选择密文。｛SWNi｝i运行多方安全计算，解密同态归总，为归总加入噪音，输出隐私保护的问卷结果｛Oj，d｝j，d。

2.2 安全模型

本节构建方案的安全模型，描述在安全模型下本文方案的特性。

1）问卷工作节点集群只有少数合谋的恶意单位，它们会在各阶段不遵循方案流程并采取各种攻击。虽可在现实中监管节点，但不排除少数节点受攻击者控制。其他多数节点为诚实但好奇的单位，它们遵循方案流程，但好奇流程中的数据密文。方案委托问卷工作节点验证用户回应的有效性，回应为公开可验证的，因此假设节点会正确地验证回应。

2）问卷发起方是恶意的。为提高问卷参与率及提高问卷结果的显著性，会尝试复制、篡改、抵赖或伪造用户回应。

3）用户是恶意的。在一些有回应奖励的问卷中，它们会尝试多次提交回应和提交无效回应。

2.2.1 匿名性

匿名性要求用户的回应过程及回应数据不包含用户身份的知识，在此特性下无法关联用户身份与回应。具体而言，若有2 名用户分别提交了2 个回应，任意拥有多项式时间算力（PPT）的敌手都不能构造出优于猜测的算法来关联身份与回应。参考ANONIZE 的匿名性定义，以敌手A 和挑战者C 间的游戏描述匿名性的要求。游戏中敌手A 控制SA 和｛SWNi｝i中少数节点，且可随意虚构新用户提交回应，即A 拥有预言机Submit 的访问权。唯一限制是对于C 所构造的用户id，A 不能访问Submit（id，-）。

1）A 与｛SWNi｝i中多数节点执行Setup（1λ）。C构造身份为id0和id1的用户U0和U1，使U0和U1与｛SWNi｝i交互执行Reg（idk，-，（sid）k）→（σU）k。

2）A 与｛SWNi｝i中多数节点执行Survey（）→（Q，｛Mj｝j，｛Li｝i），使得｛Li｝i中有至少t个U0和U1回应令牌碎片。C 生成m0、m1，选择挑战b←｛0，1｝，对于k=0和1，执行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（匿名性）方案满足匿名性，当对于任意PPT 的敌手A，有|Pr[Awins]-1/2|≤negl(λ)，其 中，negl 为可忽略函数，λ为安全参数。

2.2.2 验证性

验证性要求只有在用户列表分表中有至少t个回应令牌碎片的用户才可能提交有效回应，也要求每个回应对用户的唯一性，即在匿名性的情况下仍可检测到用户提交多个回应。以下以游戏定义验证性，游戏中敌手A 控制SA 和｛SWNi｝i中少数节点。

1）A 与｛SWNi｝i中多数节点执行Setup（1λ）。C选择用户属性attr。

2）A 可以访问预言机Reg（id，attr，sid）→σU来注册拥有属性attr 的用户不多于p（λ）次，其中p为多项式函数。A 可以访问预言机Reg（id，｛attrk｝k，sid）→σU不多于p（λ）次，其中attr∉｛attrk｝k。

3）A 与｛SWNi｝i中多数节点执行Survey（）→（Q，｛Mj｝j，｛Li｝i），其中多数节点的Li包含U 的回应令牌碎片当且仅当U 拥有属性attr。

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

5）C 验证所有回应｛RU｝U。设R为所有有效回应，L为某多数节点的Li。若|R|>|L|，则A 胜出。

定义4（验证性）方案满足验证性，对于任意PPT 的敌手A，有Pr[A wins]≤negl(λ)。

2.2.3 机密性

机密性要求用户的回应过程及回应数据不包含问卷选择明文的知识，在此特性下无法得知回应的问卷选择。回应发布在公开平台上，若不能保密回应的选择，即使满足匿名性，也难以抵抗统计手段的反匿名攻击，因此机密性在方案中尤其重要。

机密性的定义类似于匿名性，区别在于C 只控制一个用户U0，只执行Submit（id0，（sid）0，mb，σU，｛Li｝i）→（RU）b一 次，但对mb加密。设该游戏为Game’。

定义5（机密性）方案满足机密性，任意PPT 的敌手A 在Game’中胜出的概率小于1/2+negl（λ）。

2.2.4 隐私保护

隐私保护保证问卷回应的归总满足ε-差分隐私。方案在安全多方计算协议中为归总加入噪音，为此给出符合场景的f-隐私［22］定义。

定义6（f-隐私）给定任意一个计算函数f的安全多方计算协议Π，假设协议Π 共有s个计算方，在其中有不多于s−1 个恶意计算方时，函数f的计算满足f-隐私，当存在一个以协议的公共参数P、恶意方集合I、能查询恶意方的预言机O与函数输出y=f（s1，s2，…，sn）作为输入的模拟器SI，且该模拟器可模拟协议中恶意方的计算的过程，使得模拟过程的分布与真正在协议中计算过程的分布不可区分，即｛S（IP，I，O，y）｝≡｛VIEWΠ（I）｝。

下文给出符合多工作节点场景下的不可区分性的ε-分布式差分隐私（ε-IND-DDP）定义［9，22］。

定义7（ε-IND-DDP）假设VΠ为协议Π 所有可能的过程的集合。涉及多数恶意计算方I的模型下的协议Π 所执行的函数f满足ε-IND-DDP，对于任意相邻数据集D1和D2，以及任意过程V⊆VΠ，有Pr[(I)∊V]≤eεPr[VIEWΠ(D2)(I)∊V]+negl(λ)。

3 方案设计

设安全参数为λ。假设共有n个问卷工作节点｛SWN｝ii。方案为少数合谋模型，设定门限为t=n/2+1，采用SPDZ 安全多方计算协议。根据Elgamal同态加密方案，采用PS 数字签名方案。PS 数字签名方案包含以下3 个算法：

1）Keygen（）：生成密钥sk=（x，y）与公钥pk=（X，Y）=，其中g2∊G2。

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

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

3.1 初期设置阶段

3）｛SWN｝ii以SMPC 运行算法1，生成并公布同态加密公钥PK，且秘密共享私钥SK。

算法1公私钥生成算法

3.2 用户注册阶段

3.3 问卷发布阶段

3.4 问卷收集阶段

3.5 问卷结果公布阶段

算法2隐私保护算法

4 安全性分析

本节分析方案在匿名性、验证性、机密性及隐私保护方面的安全性，并讨论对合谋攻击的抵御。

4.1 匿名性

定理1当ZK 满足零知识特性，以及伪随机函数满足伪随机特性时，方案满足匿名性。

证明游戏中对于k∊｛0，1｝，C 给与A 回应（RU）k⊕b=（mk⊕b，（πm）k⊕b，（πid）k⊕b，Ck⊕b），其中C 未对mk⊕b加密。而A 可访问Submit，若A 能输出b’使得b’=b，则A 胜出。设该游戏为Game0，现考虑新游戏Game1。Game1与Game0的区别在于回应中的（πm）k⊕b，（πid）k⊕b被一模拟器所模拟。ZK 的零知识特性保证该模拟器可在无秘密的情况下模拟（πm）k⊕b和（πid）k⊕b，使得模拟器的输出（πm）*、（πid）*与（πm）k⊕b、（πid）k⊕b不可区分。因此，Game1 将证明换成（πm）*、（πid）*后，A 在游戏中的胜率不会发生不可忽略的变化。现考虑新游戏Game2，Game2 与Game1 的区别在于以随机函数替代伪随机函数来生成回应中的Ck⊕b。根据伪随机函数的伪随机特性，生成的Ck⊕b与相同长度的随机字符串str*不可区分。因此，Game2将Ck⊕b换成str*后，与Game1相比A的胜率不会发生不可忽略的变化。在Game2 中，C 给A 的回应（RU）k⊕b=（mk⊕b，（πm）*，（πid）*，str*），除mk⊕b外的所有信息都与b无关。因此，A 在Game2 中没有优于猜测的算法来选择b’使得b’=b。又因为Game2 和Game0 中A 的胜率的差异可被忽略，所以A 在Game0 中的胜率为1/2+neg（lλ），因此方案满足匿名性。

4.2 验证性

定理2当ZK 满足正确性和知识证明特性，以及门限签名方案满足不可伪造特性时，方案满足验证性。

证明以U∊L表示用户U 拥有身份id 且满足|{i：σi,id∊Li}|≥t。假设存在敌手A*可以不可忽略的概率胜出游戏，代表A*可以不可忽略的概率达成以下至少一个条件，以使得|R|>|L|。

1）A*控制的某名用户U∈L提交了2 个回应（RU）k=（（｛EU，j，d｝j，d）k，（πm）k，（πid）k，Ck），其中k=｛0，1｝，但C0≠C1。2 个回应都通过了对C 的验证。

2）A*控制的某名用户U∉L提交回应RU=（｛EU，j，d｝j，d，πm，πid，C）并通过了对C 的验证。

条 件1 中C0≠C1，即至少一个Cx是错误的且。但（RU）x通过了验证，即（πid）x被判断为正确。ZK 的正确特性保证此情况出现的概率可忽略，所以A*达成条件1 的概率可忽略。

条件2 中U∉L但提交的回应RU通过了验证，即πid被判断为正确。ZK 的知识证明特性保证存在一个抽取器，抽取器可以压倒性的概率抽取出πid的知识，包括身份id、秘密sid和签名σU、σid。但因为U∉L，即|{i：σi,id∊Li}|

因为A*可达成条件1 或条件2 的概率皆可忽略，根据反证法，证明了A*不存在，因此方案满足验证性。

4.3 机密性

定理3方案满足机密性，当ZK 满足零知识特性和加密方案时满足CPA 安全。

证明游戏Game’中C给与A回应（RU0）b=（Eb，（πm）b，（πid）0，（C）0），其中假设问卷问题数j=1 且问题选择数d1=1，所以Eb的明文mb的值为0 或1，但m0≠m1。而A 可访问Submit，若A 能输出b′使得b′=b，则A 胜出。现考虑新游戏Game1’，Game1’与Game’的区别在于回应中（πm）b被模拟器所模拟。ZK 的零知识特性保证模拟器输出的（πm）*与（πm）b不可区分。因此，Game1’在将（πm）b换成（πm）*后，A 在游戏中的胜率不会发生不可忽略的变化。在Game1’中，C给A的回应（RU0）b=（Eb，（πm）*，（πid）0，（C）0），除Eb外的所有信息都与b无关，即A 需要确定Eb的明文为m0还是m1。加密方案的CPA 安全特性保证A 的胜率不高于1/2+neg（lλ）。又因为Game1’和Game’中A的胜率的差异可被忽略，所以A在Game’中的胜率不高于1/2+neg（lλ），因此方案满足机密性。

4.4 隐私保护

定理4方案满足ε-IND-DDP，安全多方计算协议保证计算的正确性且满足f-隐私。

证明方案采用的SPDZ 安全多方计算协议已被文献［19］证明满足f-隐私，即存在可模拟恶意方计算过程的模拟器，以此保证协议在多数恶意模型下恶意计算方无法获取诚实方的输入。同时，SPDZ协议满足正确性，即若协议正常结束，则协议只能以可忽略的概率输出错误计算结果。所以，正确性保证了协议的正常输出是由Laplace 机制在归总上正确地执行后所生成，且f-隐私保证了恶意计算方无法获取有关归总及Laplace 噪音的信息。因此，由采用Laplace 机制所达成的ε-差分隐私令协议所执行的函数满足ε-IND-DDP。

4.5 合谋攻击抵御

合谋攻击抵御有以下2 种方法：

1）反匿名攻击。在ANONIZE 中敌手有选择用户的手段，可以绕开匿名性保护，因为定义只要求敌手无法分辨来自2 名诚实用户的2 个回应。本文方案中敌手无法选择用户，只能表明问卷面向的用户属性，由多数问卷工作节点决策最终用户列表。而即使在极端情况下，问卷列表只包含某一诚实用户与恶意用户的回应令牌，本文方案的机密性保护诚实用户的问卷选择，隐私保护特性保护用户的选择无法从差分隐私归总中被推导出，所以本文方案能够抵御反匿名攻击。

2）女巫攻击。本文方案中敌手只控制少数工作节点，敌手虚构的用户无法通过多数节点的身份验证，不能得到至少t个用户令牌碎片，因此无法以虚构的用户提交有效回应。

5 性能分析

本节对比分析本文方案与文献［5］、文献［8］及文献［9］方案的性能，然后对本文方案进行仿真实验，各方案的性能对比如表1 所示。

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

从表1 可以看出，ANONIZE 方案的架构是中心化的，只有一个注册机构（RA），且安全模型中所有角色都为恶意单位，所以它无法抵御RA 的女巫攻击及SA的反匿名攻击。而本文方案采用去中心化的架构，且问卷工作节点集群的安全模型为少数合谋，以门限签名抵御合谋攻击。ANONIZE 方案构成了单点信任的需求。若要信任问卷结果，需假设问卷发起方没有抵赖数据，已过滤无效的数据，及归总数据时没有引入污染。本文方案不需单点信任，防篡改平台可抵抗数据抵赖，节点基于多方安全计算，在解密归总时加入适当的Laplace 噪音，保证结果不被污染。PrivaDA 和Prio是去中心化的，同样不需要单点信任。Prio 在归总过程中未加入Laplace 噪音，隐私保护程度低。PrivaDA未考虑数据健壮性的验证，无法抵抗数据污染。Prio的SNIP 协议需要向每个工作节点发送秘密共享证明，证明总长度为O（nd），其中，n为节点数量，d为输入长度。本文方案只需上传长度为O（d）的NIZK 至公开平台以供验证。PrivaDA 和Prio中用户与节点秘密共享数据，需假设节点不会拒收碎片，本文方案中防篡改平台保证用户数据不被抵赖。

仿真实验使用了AWS 上类型为t2-large 的EC2机器，配置为3.0 GHz 的Intel CPU 处理器和8 GB 的内存，环境为64 位的Ubuntu 16.04。实验使用C 语言v0.5.14 版本的PBC 库进行方案各阶段的双线性密码运算，同时使用支持SPDZ 安全多方计算协议的SCALE-MAMBA 库进行算法部分（算法1 和算法2）的运算。

实验模拟方案有N=100 个用户与n=3 个问卷工作节点的场景，其中签名的门限为t=2，问卷的题目数为Q=10，题目的选择数为D=4，差分隐私参数ε=1。表2为对方案各阶段运算100 次的平均计算时间开销和数据存储开销。可以看出，以SMPC 运行的算法部分时间开销较其他阶段高，其中运行算法1 前需进入SMPC时间开销最高的预处理阶段，生成随机参数，以供算法1和算法2 的线上运行阶段使用。SMPC 的运算不需用户参与，因此对实时性的要求不高，实验中算法部分的时间开销为秒至分钟级别，符合实际应用的需求。

表2 方案各阶段的时间和存储开销Table 2 Time and storage costs of each stage in the scheme

表2 列出了算法各阶段理论上的计算开销，其中，E表示群上指数运算耗时，P表示双线性配对运算耗时，H表示哈希运算耗时。在问卷发布阶段，假设所有用户都能参与问卷，所以每个节点都生成N个回应令牌碎片。在问卷收集阶段，每个用户需在各个长度为N的令牌碎片列表中找出t个可用的碎片，因此平均需遍历并比对tN/2 个碎片。而在问卷结果阶段，节点共同检查回应中的零知识证明，即平均每个节点需处理N/n个回应。实验需检查零知识证明的问卷结果公布阶段耗时较高，但此阶段由节点负责，不影响系统对用户的响应。对实时性要求较高的为用户注册及问卷收集阶段，其中用户注册阶段忽略网络的开销需0.041 7 s，问卷收集阶段主要耗时在找出可用碎片以组成回应令牌，此过程平均需1.575 s，加上构造零知识证明的耗时共需2.18 s，可满足用户使用需求。在存储开销方面，初期设置与问卷结果公布阶段只需少量存储，且与用户数N无关。问卷发布与问卷收集阶段平均对每个用户的存储开销为0.774 KB 和27.452 KB，适合于区块链等公开平台上存储的量级。

图2 为问卷发布阶段及问卷收集阶段的时间开销随用户数变化的数据。从图2 可以看出，时间开销随用户数的线性增长较为缓慢，即使在用户数为5 000 时的大型问卷中，问卷发布阶段中各节点需33 s 完成回应令牌碎片的生成，而用户在问卷收集阶段中需79 s找出可用碎片以生成回应令牌，即用户从问卷发布至确认可以进行问卷回应前的延迟约为2 min，可见方案在大型问卷中具备较好的实用性。

图2 多用户场景下主要阶段的时间开销Fig.2 Time cost of the main stages in multi-user scenario

6 结束语

本文基于门限签名方案和差分隐私技术，提出一种去中心化的隐私保护的匿名问卷方案。采用同态加密技术为回应加密，将密文上传至公开防篡改平台抵抗数据抵赖，借助安全多方计算技术使差分隐私归总过程安全，并融入零知识证明技术保证方案的正确性。实验结果表明，该方案的时间和存储开销符合实际应用需求，在大型问卷中具有较好的实用性。下一步将研究本文方案在以太坊等区块链平台上部署时需要面对的挑战，包括安全多方计算协议和智能合约的集成问题。