Paillier 加密的隐私保护群智感知任务发布算法

田 静，杜云明，李 帅，刘 义

佳木斯大学 信息电子技术学院，黑龙江 佳木斯 154000

随着无线通信技术的发展以及5G 通信的正式商用，智能手机等移动通信感知设备越来越广泛地应用在各行各业，这些嵌入大量传感器（GPS、温感、陀螺仪等）的移动设备令群智感知收集信息成为可能。通常，群智感知指利用移动设备的感知能力，通过发放激励从移动设备、移动设施获得所需数据信息的分布式数据获取方法。这种数据收集方法具有数据收集者无需到达现场，可从参与感知用户获得感知结果，且能够获得实时反馈，减少了数据收集过程中的投入消耗等一系列优势。

但这种感知方式存在不可忽视的隐私安全隐患。例如：某用户需获得某一确定感知区域内的温度变化，因而将这一任务以及感知区间通过授权机构或发布平台发布给广大用户，并由这些位于感知区域内的用户将感知结果反馈给任务发布者。在这一过程中，任务发布者的感知位置信息、任务申请者的所在位置信息等都会暴露给彼此和授权机构。当部分实体不可信时，将会造成用户隐私的泄露。针对群智感知过程中存在的隐私泄露问题，Yang 等人从感知用户分布密度出发，利用差分隐私保护模型提出一种移动感知的位置隐私保护策略。但添加噪声的方式可能会造成反馈结果精确度不足的问题。其后，Yang 等人又利用分布式共识的区块链完成隐私保护的群智感知任务发布。而这种协作方式可能会因用户协作意愿而降低隐私保护成功率。近年来，一些隐私保护的群智感知应用，诸如共享公交、稀疏感知、邻近感知和成员推荐等一系列方法被相继提出。

虽然上述方法在很大程度上能够保护群智感知过程中的用户隐私，但是并未真正实现整个群智感知环境中所需要的多实体之间的信息闭环，即上述方法有的假设授权机构的完全可信（如共享公交、稀疏感知需要通过可信平台提供隐私保护处理），有的仅针对任务申请者的隐私安全（如邻近感知和成员推荐未能考虑任务发布者同样不希望发布的任务信息被不能反馈结果的用户获得）。针对这种群智感知过程中三方实体能够彼此获取隐私信息的问题，基于同态加密思想和环境网格划分，本文提出了基于Paillier 加密的隐私保护群智感知任务发布算法。

1 预备知识

1.1 系统架构

通常，群智感知的任务发布过程由图1 所示的三个实体完成，即在群智感知系统架构中存在任务发布者、授权机构和任务接收者三个实体。任务发布者指具有感知需求，并将该请求发送给授权机构，由授权机构发布任务并回收感知结果后返还给该实体；授权机构可视为任务发布和申请者之间的连接机构，由该实体完成任务位置区间的匹配计算、任务发布、激励发放等信息交换操作和计算；任务申请者是群智感知的主体，由该实体完成对所需任务、确定位置的信息感知，并将结果反馈给授权机构。

图1 群智感知的系统架构Fig.1 System architecture of crowdsensing

按照图1 所示的系统架构，可知在这种系统架构中完成一个群智感知任务的发布和回收存在三个实体之间隐私信息泄露的风险。而位置隐私的泄露普遍存在于群智感知任务发布过程中，并表现为授权机构能够精确获得任务申请者和发布者两方的位置信息；任务申请者可在获得任务发布者需求位置后构建虚假反馈结果；任务发布者恶意获得大量任务申请者位置信息并随意发布。因此，在群智感知系统下，存在较为复杂的隐私泄露风险，需要提供一种能够同时保障三方实体均无法有效获取各方精确位置的任务发布方法。

1.2 Paillier 密码体系

要满足三方之间的位置信息不被任一实体所获得，且实现位置隐私环境下的任务分配，最好的解决方法是找到一种隐私环境下的计算策略，通过秘密位置匹配计算完成任务发布。在秘密隐私计算前提下，同态加密是一个很好的密态计算方式。Paillier密码体系则能够提供同态加密计算的各种同态特性。其计算处理如下：

其解密过程为，对于密文，存在是(-1)和(-1)的最小公倍数，即=lcm((-1),(-1))，此时有明文：

基于这样一种密态环境下的加法计算，可设计一种基于该技术的群智感知任务分配方法。

2 基于Paillier 加密的任务发布

2.1 隐私保护算法的基本思想

在群智感知任务发布中，可将待感知区域划分为一个包含多个单元格的网状区域。此时位于每个单元格中的用户为备选任务申请者，当这一用户同意为任务发布者反馈感知结果时，可将所在区域的感知结果反馈给任务发布者。在这一过程中，授权机构完成对任务的发布以及反馈结果的收集工作。

因此，隐私保护的基本思想可归结为：（1）任务发布者和任务申请者首先对任务所需感知区域以及提供感知反馈区域按照预定要求设置位置取值；（2）这两个实体对设置完的取值使用相同的Paillier 公钥进行加密后并发送给授权机构；（3）授权机构在密态环境下对上述两个实体提交的结果进行匹配计算，若满足条件则由当前的申请者集合提交结果，并将结果反馈给任务发布者；（4）任务发布者按照收到的反馈信息对任务申请者发放感知激励。在这一过程中，授权机构所获得的全部信息为加密后的密态信息，在不知道Paillier 私钥的前提下无法获知具体感知区域；任务发布者不知道任何任务申请者的具体位置，最后获得的是整个区域的感知结果；而任务申请者同样不知自身是否位于感知区间，因而无法获知任务发布者的位置隐私。

2.2 隐私保护的群智感知任务发布流程

授权机构首先将所管辖范围划分为由多个单元格构成的网络区域，并将该区域在这一范围内广播，使得任务发布者和任务申请者均能获得这一区域的网格划分。

任务发布者从授权机构获得当前所在区域的网格划分，选择包含所需感知区域在内的一个矩形子区域，并基于该区域建立对应的二维矩阵（如式（4）所示）。其中，需要感知的网格在二维矩阵中标记为任意非0 数字，而不需感知的网格标记为0。在完成二维矩阵的建立之后，使用Paillier 公钥对矩阵中每个标记值进行加密，在加密完成后将加密后的矩阵以及激励保障金一同发送给授权机构。

授权机构在收到任务发布者发送过来的由感知区域构成的二维矩阵后，将感知区域框架广播给任务申请者。

任务申请者同样从授权机构获得所在区域的网格划分以及任务发布者的感知区域，首先核对自身的感知区间是否包含任务发起者所需的感知网格。若有，则按照任务发布者的感知区域构建自身的反馈区域，并基于该区域建立二维矩阵（如式（5）所示）。使用非0 数值标记能够感知的单元格，而不能感知的标记为0。同时，将建立后的二维矩阵发送给授权机构。

授权机构获得由多个任务申请者发送过来的感知矩阵，在剔除掉相同矩阵后获得申请矩阵集合B,0 ≤≤（为任务发布者可发放激励的最大值）。在计算=·+·+…+·B后，将发送给任务发布者。式（6）给出了由式（4）、式（5）经过计算后的结果。

任务发布者使用Paillier 私钥对进行解密，若解密后的矩阵包含所有需要感知的单元格，则通知授权机构获取感知结果；否则要求授权机构再次向申请者广播感知区域。授权机构将感知结果发送给任务发布者，同时将激励保障金按照预先设定分发给各个任务申请者。

在不考虑Paillier 加密的情况下，设中非零元素为需要感知的区域单元格，中非零元素为任务申请者能够感知的区域单元格，·之后获得的结果中非零元素则为两个实体可感知的匹配区域。当任务发布者综合多个任务申请者反馈的匹配区域之后，就可以找到能够反馈所有需要感知区域的任务申请者，此时可保障感知任务的顺利发布。

2.3 任务发布者的信息处理

设任务发布者建立对应的二维矩阵中，每个矩阵对应的元素可表示为a,0 ≤,≤，根据Paillier密码体系加密获得每个矩阵元素对应的加密后元素信息(a)，并将(a)发送给授权机构。算法1 描述了这一处理过程。

任务发布者的加密矩阵建立

如何建立Paillier 密码系统的公钥在1.2 节中已经详细介绍，此处不再赘述。经过算法1 的处理可获得加密后的任务发布者位置网格二维矩阵()，并将该矩阵发送给授权机构。

2.4 任务申请者的信息处理

设任务申请者通过广播获得任务发布者公钥=(,)，同时按照自己能够完成的任务位置网格区间建立自身的位置响应二维矩阵，其中每个矩阵中对应的元素为b,0 ≤,≤，使用对每个元素加密后获得(b)，并将(b)发送给授权机构。算法2 给出了这一加密过程。

任务申请者的加密矩阵建立

不同的任务申请者使用算法2 对自身位置矩阵加密后，分别将加密矩阵发送给授权机构，授权机构将通过矩阵计算完成加密状态下的位置匹配。

2.5 授权机构的信息处理

授权机构是完成秘密位置矩阵匹配的中心实体，当该实体收到由多个任务申请者发送的服务位置矩阵以及由任务发布者发送的任务矩阵之后，计算=·+·+…+·B获得同态加密计算后的矩阵(c)，并将(c)反馈给任务发布者，由任务发布者解密后检验当前矩阵是否满足任务要求。

隐私保护的任务位置匹配

任务发布者在收到反馈的(c)后对其进行解密处理，若该矩阵中与初始的中每个对应位置中的元素均为非零元素，则当前矩阵可提供所有感知结果，否则不能提供全部位置感知，需要由授权机构完成二次任务申请者申请汇总，以找到足够位置的任务申请者用来完成群智感知任务。

3 安全性分析

由于在群智感知的任务发布过程中，存在两个实体提交自身信息的情况，所有在安全性分析中需要同时考虑任务发布者的安全性以及任务申请者的安全性，即这两个实体的信息是否会被另外参与发布的两个实体所获知。

3.1 任务发布者的安全性

任务发布者在整个群智感知过程中的位置隐私安全主要存在两方面的威胁，即授权机构和任务申请者，并表现为授权机构需要核定任务发布者的位置是否和任务申请者位置一致；另一方面，任务申请者也需要确认是否能够参与任务感知。对于授权机构，其获得的任务发布者信息是加密后的矩阵()，在不具有私钥=(,)的前提下，授权机构无法获知矩阵中具体位置数值。同时，由于任务发布者建立的矩阵中使用的数值并不是完全一致的，即使授权机构掌握其公钥也不能通过碰撞性尝试猜测矩阵中具体信息。

3.2 任务申请者的安全性

对于任务申请者位置，需要保障授权机构和任务发布者不会获得其精确位置。其中，由于任务申请者同样使用任务发布者公开的公钥对自身位置矩阵进行加密，授权机构在不具有私钥的情况下不能通过解密获得任务申请者精确位置信息。

而对于任务发布者，申请者的信息以及位置加密矩阵(b)并不被任务发布者所获知，整个过程中任务发布者仅可知，当前提供的加密位置矩阵()能够被加密矩阵(b)所匹配。此外，加密矩阵(b)是哪一个具体的任务申请者所提供，且每一个任务申请者能够提供哪个感知位置的任务反馈，这些信息都是授权机构在加密状态下通过Paillier 秘密系统的同态特性，在密态环境下通过矩阵点乘来完成计算的。因此整个过程中，任务发布者并不能获得任务申请者任何准确的位置信息。

因此，在整个群智感知的过程中，三方实体之间均不存在过多获取其他实体位置信息的情况，因而能够实现隐私保护下的群智感知的任务发布。

4 实验验证

4.1 实验设定

为验证算法的有效性和隐私保护能力，本文在模拟环境下对该算法和其他同类算法进行测试比较，其结果进一步支持在安全性分析中所获得的结论。模拟实验在笔记本电脑I7 处理器、8 GB 内存的环境下，使用Python 3.6 进行测试。测试使用Geolife提供的位置数据，选择同一区域进行网格划分，并假定每10 个用户中存在一个可反馈感知结果的任务申请者。参与比较的算法有基于差分隐私的DPLP（differential privacy-based location protection）算法、基于可调节路径的PAPP（preserving adjustable path privacy）算法以及基于差分和位置扭曲的Differential-distortion算法。因此，模拟实验结果将在与上述同类算法的比较和分析中给出。在算法有效性方面将从算法执行时间、感知位置匹配率以及反馈结果正确率等方面加以验证。算法隐私保护能力将从实体间数据披露程度（信息熵）和匹配位置猜测成功率两方面加以验证。

4.2 实验结果及成因分析

在算法有效性方面，主要验证算法与其他同类算法在时间、任务匹配以及结果准确性方面的能力。通常，在群智感知中，算法的执行时间是按照发布感知到反馈结果的整个处理过程。在模拟实验中，假设选定的用户都是可以反馈感知结果的用户，图2 给出了不同算法在执行时间上的差异。从该图中可以看出，本文算法尽管采用了加密措施来完成各个申请用户与发布用户之间的区域匹配，但加密过程可以在线下进行，授权机构仅需要进行有限的加密后同态计算即可完成匹配过程。此外，该算法执行时间较短还包括以下原因：首先，矩阵计算是利用矩阵点乘的方法计算的，并没有达到的三次方这样高的复杂度；其次，矩阵计算关注点是非零元素的个数而不是具体非零元素的值，因此使用异或运算可代替乘法运算，而异或运算的计算耗时极低；最后，用于分配任务的网格规模有限，进而导致使用的矩阵规模较小，这也是计算开销较低的一个原因。而其他算法或者添加了满足差分隐私的噪声数据影响匹配结果，或者对整个感知过程中的数据传递进行了路径传递变化，因而任务申请者的自身位置是经过各种变化处理的，这种变化扰乱了匹配的真实性，在很大程度上存在匹配冗余，这种冗余增加了算法处理时间，因而这些算法的执行时间要高于本文算法。

图2 不同算法的执行时间Fig.2 Running time of various algorithms

图3 给出了不同算法感知位置的匹配成功概率。从该图中可以看出，本文算法不仅具有较高的感知匹配率，且这种匹配率能够保持均衡稳定。这是由于本文算法并未对申请用户以及任务发布用户进行噪声与扭曲处理，所有操作均在原始位置区间通过同态加密特性完成匹配操作，因而相对于其他通过添加噪声、位置变换、位置扭曲等算法具有更好的感知匹配率。

图3 不同算法的感知位置匹配率Fig.3 Matching probability of crowdsensing locations of various algorithms

图4 不同算法的反馈结果正确率Fig.4 Accuracy of feedback results of various algorithms

图4 给出了不同算法获得由任务申请者反馈结果产生的结果正确率。同样由于本文算法采用的位置匹配特性，使得任务申请者反馈的结果能够真实地反映任务发布者所需要的任务集合，因而本文算法的反馈结果正确率最高。而其他几种算法则由于位置扭曲，造成部分结果不准确的情况，影响结果反馈。

在算法隐私保护能力方面，将从攻击者对各实体位置猜测的成功率以及成功率基础上由信息熵表示实体间信息披露两方面加以验证。

图5 给出了攻击者对各个实体位置猜测的成功率。从该图中可以看出，已有算法在任务申请者数量增加的情况下，被攻击者准确识别猜测的概率逐渐降低，这是由于任务申请者用户数量增加产生了泛化作用，而这种泛化增加了准确猜测的难度。但是，本文算法由于采用加密手段，在密态环境下完成任务匹配发布，整个过程中并没有任何位置信息被明文使用，因此具有更为严格的隐私保护效果，攻击者猜测成功的概率最低，且并不因任务申请者数量而有所变换。

图5 不同算法猜测实体位置的成功率（攻击者）Fig.5 Success ratio of guessing real locations of various algorithms(adversary)

图6 不同算法的实体间信息披露Fig.6 Entropy of information disclosure of various algorithms

综上，通过与同类算法在有效性和隐私保护能力两个主要方面的比较，可以看出本文算法具有一定优势，优于目前主流算法。

5 结束语

对于群智感知的任务发布隐私问题，本文提出了一种在Pailier 加密基础上利用位置区域网格矩阵完成密态下的任务发布算法。该算法能够有效保障群智感知参与各方实体之间的隐私不会在感知过程中被泄露。同时，通过安全性分析和在模拟环境的实验验证进一步证明了所提出的算法的优越性。

尽管本文算法很好地解决了群智感知任务发布过程中的位置信息隐私保护的问题，但该算法存在一些问题未能有效解决。如感知用户不能满足所需区间情况下，再次发布任务的频率问题以及感知过程中结果反馈中可能存在的任务申请者造假问题。今后的工作将主要解决这两个问题。