一種基于對(duì)稱加密的隱私保護(hù)增量真值發(fā)現(xiàn)算法

倪凱敏 張若海 姜暢 葉繪明

摘 要：隨著信息技術(shù)的飛速發(fā)展，群智感知真值發(fā)現(xiàn)系統(tǒng)成為物聯(lián)網(wǎng)領(lǐng)域的研究熱點(diǎn)之一，保護(hù)用戶的隱私是設(shè)計(jì)真值發(fā)現(xiàn)算法的重大挑戰(zhàn)。文中設(shè)計(jì)了一種輕量級(jí)基于對(duì)稱加密的隱私保護(hù)增量真值發(fā)現(xiàn)算法。該算法中每個(gè)用戶在一個(gè)時(shí)間戳內(nèi)只需要觀察一個(gè)對(duì)象，用戶只需要上傳該對(duì)象的信息即可，無(wú)需重復(fù)上傳之前所有已觀察過(guò)的“舊對(duì)象”的信息，大大降低了用戶的計(jì)算開(kāi)銷和通信開(kāi)銷。

關(guān)鍵詞：群智感知;增量真值發(fā)現(xiàn);隱私保護(hù);對(duì)稱加密;輕量級(jí);權(quán)重

中圖分類號(hào)：TP39文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-1302（2020）11-00-04

0 引 言

近年來(lái)，隨著智能設(shè)備的普及，群智感知應(yīng)用[1-3]越來(lái)越廣泛。真值發(fā)現(xiàn)技術(shù)[4-6]被應(yīng)用于群智感知系統(tǒng)中以提高數(shù)據(jù)聚合的準(zhǔn)確度，推斷出目標(biāo)對(duì)象的真值信息。例如，為了更精確地評(píng)估某一地區(qū)當(dāng)前的溫度，第三方機(jī)構(gòu)需要對(duì)從不同傳感器上收集的數(shù)據(jù)進(jìn)行真值發(fā)現(xiàn)。由于在真值發(fā)現(xiàn)的過(guò)程中用戶的感知數(shù)據(jù)可能暴露，導(dǎo)致其隱私信息外泄，比如用戶的通訊錄、常用地址等，所以在真值發(fā)現(xiàn)過(guò)程中需要注意保護(hù)用戶的隱私。

目前已有的隱私保護(hù)真值發(fā)現(xiàn)算法大部分基于雙云服務(wù)器模型，需假設(shè)云服務(wù)器是半誠(chéng)實(shí)的，但此假設(shè)性過(guò)強(qiáng)，在實(shí)際應(yīng)用時(shí)需要付出不小的代價(jià)。也有不少基于單云服務(wù)器的隱私保護(hù)真值發(fā)現(xiàn)算法被相繼提出，但計(jì)算開(kāi)銷都較大。Miao等人[7]利用單云服務(wù)器模型提出了一種隱私保護(hù)增量真值發(fā)現(xiàn)算法I-PPTD，該算法以順序方式收集用戶的感知數(shù)據(jù)，并對(duì)用戶的感知數(shù)據(jù)和權(quán)重隱私進(jìn)行安全保護(hù)。然而，I-PPTD采用的門限Paillier同態(tài)加密算法[8]復(fù)雜度較高，導(dǎo)致用戶端和云服務(wù)器端進(jìn)行加解密運(yùn)算產(chǎn)生的開(kāi)銷較大。

本文提出了單云服務(wù)器模型下的一種基于對(duì)稱加密的隱私保護(hù)增量真值發(fā)現(xiàn)算法，該算法采用對(duì)稱同態(tài)加密[9]方式對(duì)數(shù)據(jù)進(jìn)行聚合，比門限Paillier同態(tài)加密算法更高效，且當(dāng)用戶感知到一個(gè)新對(duì)象時(shí)，用戶只須上傳對(duì)該新對(duì)象的加密信息即可。同時(shí)，云服務(wù)器端也只須估計(jì)該新對(duì)象的真值。實(shí)驗(yàn)結(jié)果表明，本文算法降低了用戶和云服務(wù)器的計(jì)算開(kāi)銷和通信開(kāi)銷，提高了隱私保護(hù)增量真值發(fā)現(xiàn)算法的實(shí)現(xiàn)效率。

1 系統(tǒng)模型

由于文中方案所考慮的是單云服務(wù)器模型下的隱私保護(hù)，因此需要一個(gè)可信第三方密鑰分發(fā)中心來(lái)對(duì)云服務(wù)器以及每個(gè)用戶的密鑰進(jìn)行管理，并且密鑰分發(fā)中心到用戶或者云服務(wù)器之間用來(lái)傳遞信息的通信信道不可監(jiān)聽(tīng)。系統(tǒng)模型如圖1所示。本方案的主要參與方由三個(gè)實(shí)體構(gòu)成，即可信密鑰分發(fā)中心、云服務(wù)器平臺(tái)以及用戶。各實(shí)體的具體定義如下所示。

（1）可信密鑰分發(fā)中心。密鑰分發(fā)中心是具有強(qiáng)大計(jì)算能力的第三方機(jī)構(gòu)，它是誠(chéng)實(shí)可信的。在真值發(fā)現(xiàn)過(guò)程開(kāi)始之前，密鑰分發(fā)中心會(huì)為云服務(wù)器和每個(gè)用戶安全分配用以生成密鑰的隨機(jī)數(shù)集合。

（2）云服務(wù)器。云服務(wù)器分配給用戶感知任務(wù)，收集用戶數(shù)據(jù)，并提供算力資源執(zhí)行真值發(fā)現(xiàn)算法。

（3）用戶。用戶使用自身攜帶的智能傳感設(shè)備來(lái)執(zhí)行感知任務(wù)，提供感知數(shù)據(jù)。

假設(shè)在當(dāng)前時(shí)間戳中，系統(tǒng)所有的用戶集合為U，當(dāng)前新觀測(cè)到的對(duì)象表示為ol，在這之前用戶感知過(guò)的“舊對(duì)象”表示為o1， o2， ...， ol-1，此時(shí)系統(tǒng)的對(duì)象集合假設(shè)為M。wli表示系統(tǒng)內(nèi)第i個(gè)用戶對(duì)于對(duì)象ol的權(quán)重，xli表示用戶i的智能設(shè)備感測(cè)到的對(duì)象ol的感知數(shù)據(jù)。對(duì)于每一個(gè)對(duì)象，都有一個(gè)真值xl，而這個(gè)真值對(duì)于系統(tǒng)中的所有參與方而言都屬未知。系統(tǒng)的目標(biāo)是計(jì)算當(dāng)前時(shí)間戳對(duì)象ol的真值xl。

用戶連續(xù)執(zhí)行感知任務(wù)，通過(guò)設(shè)備和云服務(wù)器平臺(tái)支持的3G/4G、無(wú)線或其他類型的安全網(wǎng)絡(luò)向云服務(wù)器發(fā)送時(shí)間序列數(shù)據(jù)。在每個(gè)時(shí)間戳內(nèi)，每個(gè)用戶使用密鑰加密自己的感知數(shù)據(jù)，并將密文上傳給云服務(wù)器，接收到所有用戶的信息后，云服務(wù)器將進(jìn)行數(shù)據(jù)聚合和增量真值發(fā)現(xiàn)過(guò)程。系統(tǒng)的目標(biāo)是計(jì)算出每個(gè)時(shí)間戳對(duì)象的估計(jì)真值，同時(shí)保護(hù)每個(gè)用戶的感知數(shù)據(jù)和權(quán)重信息不被泄露。

2 增量真值發(fā)現(xiàn)算法簡(jiǎn)介

隱私保護(hù)增量真值發(fā)現(xiàn)算法是由Miao等人在最近的研究[7]中提出的。在許多實(shí)際的群智感知應(yīng)用中，感知任務(wù)的持續(xù)時(shí)間可能較長(zhǎng)，多為幾天或幾個(gè)月。例如在醫(yī)療應(yīng)用程序中，患者的健康數(shù)據(jù)通常為逐日收集，待幾周或幾個(gè)月后再分析這些數(shù)據(jù)極為低效。此時(shí)不同對(duì)象的觀測(cè)值通常通過(guò)流方式從用戶方收集，然后通過(guò)增量真值發(fā)現(xiàn)算法計(jì)算真值。增量真值發(fā)現(xiàn)算法能動(dòng)態(tài)更新對(duì)象真值和用戶權(quán)重，它可以在不泄露每個(gè)用戶私人信息的情況下，通過(guò)重新訪問(wèn)之前保存的舊數(shù)據(jù)及時(shí)估計(jì)新觀測(cè)的對(duì)象真值。

在這些以流方式收集感知數(shù)據(jù)的場(chǎng)景中，用戶一個(gè)時(shí)間戳內(nèi)只觀察一個(gè)對(duì)象，因此云服務(wù)器只需計(jì)算該對(duì)象的真值即可，無(wú)需重復(fù)計(jì)算之前所有對(duì)象的數(shù)據(jù)，開(kāi)銷比以往的真值發(fā)現(xiàn)算法[10-11]更小。不同的是，增量真值發(fā)現(xiàn)算法不涉及迭代階段，并且是從真值更新開(kāi)始，然后在觀察到新對(duì)象時(shí)更新每個(gè)用戶的權(quán)重，每個(gè)用戶的權(quán)重會(huì)隨著對(duì)象數(shù)量的增加而趨于穩(wěn)定。

感知數(shù)據(jù)通常可以分為兩類，即連續(xù)數(shù)據(jù)和分類數(shù)據(jù)。連續(xù)數(shù)據(jù)的數(shù)值是連續(xù)不斷的，相鄰兩個(gè)數(shù)值可以作無(wú)限分割，例如溫度、體重等。分類數(shù)據(jù)是按照現(xiàn)象的某種屬性對(duì)其進(jìn)行分類或分組而得到反映事物類型的數(shù)據(jù)，其結(jié)果只能是其中單獨(dú)一類或者一組，例如性別、天氣類型等。

增量真值發(fā)現(xiàn)過(guò)程包含兩個(gè)步驟。

（1）真值更新。如果該新增對(duì)象ol是系統(tǒng)中的第一個(gè)對(duì)象，則它的真值由云服務(wù)器隨機(jī)初始化得到;如果該新增對(duì)象ol不是系統(tǒng)中的第一個(gè)對(duì)象，則其真值由用戶協(xié)助云服務(wù)器計(jì)算得到。

云服務(wù)器根據(jù)上一個(gè)時(shí)間戳中計(jì)算并保存的所有用戶權(quán)重，使用公式（1）計(jì)算ol的真值：

式中：當(dāng)感知數(shù)據(jù)連續(xù)時(shí)，xl*是對(duì)象ol觀測(cè)值的加權(quán)平均值;當(dāng)數(shù)據(jù)為分類數(shù)據(jù)時(shí)，xl*為向量，其中每個(gè)元素代表某個(gè)特定的真實(shí)候選結(jié)果或答案的概率，對(duì)象ol的估計(jì)真值將是向量xl*最大的結(jié)果或答案。

（2）權(quán)重更新。權(quán)重更新通常采用CRH中的對(duì)數(shù)權(quán)函數(shù)[12]。由于在增量真值發(fā)現(xiàn)過(guò)程中，在每一個(gè)時(shí)間戳內(nèi)用戶對(duì)于當(dāng)前對(duì)象都有一個(gè)權(quán)重，在這一時(shí)間戳內(nèi)，云服務(wù)器根據(jù)用戶i的感知數(shù)據(jù)和真值的差來(lái)計(jì)算它在此刻對(duì)于對(duì)象ol的權(quán)重：

式中，是一個(gè)距離函數(shù)，同以往的真值發(fā)現(xiàn)算法一樣，其可用來(lái)衡量感知數(shù)據(jù)和真值的差。對(duì)于連續(xù)數(shù)據(jù)，采用平方距離函數(shù)計(jì)算。對(duì)于分類數(shù)據(jù)，感知數(shù)據(jù)代表用戶i為任務(wù)ol選擇的第q個(gè)結(jié)果或答案，此時(shí)的距離函數(shù)表示為：。

3 算法設(shè)計(jì)

3.1 算法概述

輸入：安全參數(shù)λ，當(dāng)前時(shí)間戳系統(tǒng)用戶i對(duì)第l個(gè)對(duì)象ol的感知數(shù)據(jù)為，用戶i對(duì)前（l-1）個(gè)對(duì)象的“舊信息”為Di，用戶i對(duì)第（l-1）個(gè)對(duì)象的加密權(quán)重為。

輸出：第l個(gè)對(duì)象的真值為xl*。

（1）系統(tǒng)建立?？尚诺谌矫荑€分發(fā)中心為云服務(wù)器和每個(gè)用戶分發(fā)隨機(jī)數(shù)集合。

（2）初始化。云服務(wù)器和每個(gè)用戶根據(jù)接收到的隨機(jī)數(shù)集合生成自己的密鑰。

（3）云服務(wù)器估計(jì)對(duì)象真值。用戶加密數(shù)據(jù)并輔助云服務(wù)器估計(jì)當(dāng)前時(shí)間戳新對(duì)象的真值xl*。

（4）云服務(wù)器估計(jì)用戶權(quán)重。用戶根據(jù)新對(duì)象的真值更新Di，云服務(wù)器估計(jì)每個(gè)用戶對(duì)新對(duì)象的加密權(quán)重，并保存加密權(quán)重信息。

3.2 算法設(shè)計(jì)

算法所涉及符號(hào)的相關(guān)描述見(jiàn)表1所列。

3.2.1 系統(tǒng)建立

輸入安全參數(shù)λ，可信第三方密鑰分發(fā)中心產(chǎn)生|U|份隨機(jī)且不同的集合S1， S2， ...， S|U|，每個(gè)集合中含有數(shù)量不等的隨機(jī)數(shù)。用S表示所有隨機(jī)數(shù)的集合，Si（i∈[1，|U|]）表示第i個(gè)隨機(jī)數(shù)子集，顯然。密鑰分發(fā)中心將集合S1， S2， ...， S|U|和S通過(guò)已確保安全的通信信道分別發(fā)送給每個(gè)用戶和云服務(wù)器。

3.2.2 初始化

接收到密鑰分發(fā)中心發(fā)送的隨機(jī)數(shù)集合后，用戶i計(jì)算自己的加密密鑰，云服務(wù)器計(jì)算解密密鑰。

由于每個(gè)h（fs'（t））都在{0， 1}λ上均勻分布，ski在{0， 1}λ上也均勻分布，因此加密密鑰滿足底層密碼系統(tǒng)的安全要求。假設(shè)mi表示用戶i的明文，M表示明文空間，則每個(gè)用戶加密數(shù)據(jù)為：ci=（ski+mi）modM。云服務(wù)器聚合所有用戶的密文，并減去解密密鑰sk0即可得到解密后的明文總和。驗(yàn)證過(guò)程見(jiàn)式（3）：

3.2.3 云服務(wù)器估計(jì)對(duì)象真值

如果ol是系統(tǒng)中的第一個(gè)對(duì)象，則其真值xl*由云服務(wù)器使用隨機(jī)數(shù)生成器Rand（）初始化得到，并將結(jié)果通過(guò)安全的通信信道發(fā)送給每個(gè)用戶。

如果ol不是系統(tǒng)中的第一個(gè)對(duì)象，則其初始真值由用戶協(xié)助云服務(wù)器計(jì)算得到。云服務(wù)器使用自己保存的前一個(gè)對(duì)象ol-1真值發(fā)現(xiàn)得到的用戶加密權(quán)重集合（）來(lái)估計(jì)當(dāng)前對(duì)象的真值，具體過(guò)程如下：

（1）云服務(wù)器生成隨機(jī)掩碼rc并計(jì)算，將結(jié)果通過(guò)安全的通信信道分別發(fā)送給對(duì)應(yīng)的用戶;

（2）用戶i接收到數(shù)據(jù)后，用該數(shù)據(jù)乘以自身感知數(shù)據(jù)并加密，同時(shí)加密數(shù)據(jù)ski·xli，xli，并將密文發(fā)送到云服務(wù)器;

（3）接收到所有用戶發(fā)送的密文后，云服務(wù)器解密，得到，同樣可解密得到。

（4）計(jì)算，并根據(jù)公式（1）得到當(dāng)前對(duì)象ol的估計(jì)真值xl*。

3.2.4 云服務(wù)器估計(jì)用戶權(quán)重

云服務(wù)器將初始化的對(duì)象真值或估計(jì)的對(duì)象真值通過(guò)安全的通信信道發(fā)送給每個(gè)用戶。

用戶i接收到云服務(wù)器發(fā)送的真值后，根據(jù)自己的感知數(shù)據(jù)計(jì)算當(dāng)前對(duì)象ol的距離函數(shù)，更新，等號(hào)右邊的Di表示用戶i在過(guò)去時(shí)刻觀測(cè)到的所有（l-1）個(gè)對(duì)象的感知數(shù)據(jù)的距離總和，即“舊信息”，可表示為。保存更新后的Di，作為后續(xù)新對(duì)象需要用到的“舊信息”。用戶i加密，并計(jì)算，將兩個(gè)結(jié)果發(fā)送到云服務(wù)器。

云服務(wù)器接收到所有用戶發(fā)送的密文后，聚合解密得到所有用戶對(duì)所有對(duì)象的距離函數(shù)總和，并計(jì)算，根據(jù)用戶i發(fā)送的值和公式（2）計(jì)算得到用戶i對(duì)于對(duì)象ol的加密權(quán)重。云服務(wù)器將保存加密的用戶權(quán)重信息，為估計(jì)下一個(gè)新對(duì)象的真值所用。

4 效率分析

通過(guò)實(shí)驗(yàn)將本文算法與I-PPTD算法進(jìn)行對(duì)比分析，展示本文算法的性能和效率。本實(shí)驗(yàn)代碼用Java編寫，并使用Java標(biāo)準(zhǔn)大數(shù)類BigDecimal運(yùn)算，在Eclipse上編譯。實(shí)驗(yàn)由配置了AMD A6-4455 APU with Radeon（tm）HD Graphics處理器，12 GB內(nèi)存，以及Windows 7操作系統(tǒng)的PC機(jī)運(yùn)行。

本實(shí)驗(yàn)的感知數(shù)據(jù)集由隨機(jī)數(shù)生成器Rand（）生成，對(duì)于每個(gè)對(duì)象，觀測(cè)值的取值都在r±（r×10%）以內(nèi)，其中r屬于[0，1]。實(shí)驗(yàn)只針對(duì)連續(xù)型整數(shù)，選取10個(gè)用戶，27個(gè)對(duì)象為實(shí)驗(yàn)樣本，實(shí)驗(yàn)數(shù)據(jù)均為重復(fù)運(yùn)行10次后得到的平均值。對(duì)比算法實(shí)驗(yàn)的安全參數(shù)n設(shè)為1 024，安全級(jí)別約為80 B，本文算法使用SHA-256作為加密算法，通過(guò)使用JDK自帶的java.security.MessageDigest類調(diào)用已集成的安全哈希算法digest（）實(shí)施，安全級(jí)別為128 B，即本文算法的安全級(jí)別比算法I-PPTD更高。本文算法的效率可以從計(jì)算開(kāi)銷和通信開(kāi)銷兩方面分析。

4.1 計(jì)算開(kāi)銷

圖2和圖3所示為兩種算法在用戶端和云服務(wù)器端的計(jì)算開(kāi)銷。從圖中可以看出，本文算法在用戶端和云服務(wù)器端的計(jì)算開(kāi)銷均低于I-PPTD算法。

4.2 通信開(kāi)銷

通信開(kāi)銷比較的是兩個(gè)算法用戶端和云服務(wù)器端發(fā)送或接收的數(shù)據(jù)，實(shí)驗(yàn)結(jié)果顯示在表2和表3中。通過(guò)兩個(gè)表可以看出本文算法在用戶端和云服務(wù)器端的通信開(kāi)銷均比I-PPTD算法小。

5 結(jié) 語(yǔ)

本文構(gòu)造了一種新的隱私保護(hù)增量真值發(fā)現(xiàn)算法，針對(duì)半誠(chéng)實(shí)的雙云服務(wù)器模型假設(shè)性過(guò)強(qiáng)的問(wèn)題，采用單云服務(wù)器模型構(gòu)造隱私保護(hù)方法，能夠更加靈活地適用于實(shí)際應(yīng)用場(chǎng)景。將對(duì)稱同態(tài)加密技術(shù)應(yīng)用于增量真值發(fā)現(xiàn)算法中，可進(jìn)一步降低用戶端和云服務(wù)器端的計(jì)算開(kāi)銷和通信開(kāi)銷。

參考文獻(xiàn)

[1] HU Shaohan，SU Lu，LIU Hengchang，et al. SmartRoad：a crowd-sourced traffic regulator detection and identification system. Proceedings of the 12th International Conference on Information Processing in Sensor Networks（IPSN 2013）[C]// ACM，2013：331-332.

[2] MUN M，REDDY S，SHILTON K，et al. PEIR，the personal environmental impact report，as a platform for participatory sensing systems research. Proceedings of the 7th International Conference on Mobile Systems，Applications，and Services（MobiSys 2010）[C]// ACM，2009：55-68.

[3] RABBI M，ALI S，CHOUDHURY T，et al. Passive and in-situ assessment of mental and physical well-being using mobile sensors. Proceedings of the 13th International Conference on Ubiquitous Computing（UbiComp 2011） [C]// ACM，2011：385-394.

[4] LI Yaliang，GAO Jing，MENG Chuishi，et al. A survey on truth discovery [J]. ACM SIGKDD explorations newsletter，2016，17（2）：1-16.

[5] MA Fenglong，LI Yaliang，LI Qi，et al. FaitCrowd：Fine grained truth discovery for crowdsourced data aggregation. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining（KDD 2015） [C]// ACM，2015：745-754.

[6] MENG Chuishi，JIANG Wenjun，LI Yaliang，et al. Truth discovery on crowd sensing of correlated entities. Proceedings of the 13th ACM Conference on Embedded Networked Sensor Systems（SenSys 2015） [C]// ACM，2015：169-182.

[7] MIAO Chenglin，JIANG Wenjun，SU Lu，et al. Privacy-preserving truth discovery in crowd sensing systems [J]. ACM transactions on sensor networks（TOSN），2019，15（1）：32.

[8] CRAMER R，DAMGARD I，NIELSEN J B. Multiparty computation from threshold homomorphic encryption [J]. Basic research in computer science，2001，7（14）：280-299.

[9] LI Qinghua，CAO Guohong，LA PORTA T F. Efficient and privacy-aware data aggregation in mobile sensing [J]. IEEE transactions on dependable and secure computing，2013，11（2）：115-129.

[10] MIAO Chenglin，JIANG Wenjun，SU Lu，et al. Cloud-enabled privacy preserving truth discovery in crowd sensing systems. In Proceedings of the 13th ACM Conference on Embedded Networked Sensor Systems （SenSys 2015） [C]// ACM，2015：183-196.

[11]孫洪山，陸雪，徐嶸，等.一種高效的隱私保護(hù)群智感知真值發(fā)現(xiàn)機(jī)制[J].物聯(lián)網(wǎng)技術(shù)，2018，8（7）：20-21.

[12] LI Qi，LI Yaliang，GAO Jing，et al. Resolving conflicts in heterogeneous data by truth discovery and source reliability estimation. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data（SIGMOD 2014）[C]// ACM，2014：1187-1198.