無線網(wǎng)絡(luò)安全 課件 第10章 LBS中隱私增強(qiáng)的分布式K-匿名激勵(lì)機(jī)制

LBS中隱私增強(qiáng)的分布式K-匿名激勵(lì)機(jī)制研究背景預(yù)備知識(shí)機(jī)制設(shè)計(jì)機(jī)制分析實(shí)驗(yàn)本章小結(jié)思考題目引言LBS中隱私增強(qiáng)的分布式K-匿名激勵(lì)機(jī)制用戶可以利用基于位置的服務(wù)（LocationBasedService，LBS）通過位置服務(wù)提供商（LocationServiceProvider，LSP）來獲取與空間位置相關(guān)的信息。然而，請(qǐng)求者的位置隱私受到LSP的威脅，為此，分布式K-匿名被提出，它允許請(qǐng)求者獲取K-1個(gè)協(xié)作者的位置，并由協(xié)作者和請(qǐng)求者的共計(jì)K個(gè)位置構(gòu)建匿名區(qū)域。引言考慮到為K-匿名提供協(xié)助會(huì)為協(xié)助者帶來諸多開銷、進(jìn)而產(chǎn)生消極參與情緒，研究者們提出了許多激勵(lì)機(jī)制，允許協(xié)作者得到請(qǐng)求者的補(bǔ)償，這有效地激勵(lì)了協(xié)作者。然而，現(xiàn)有的分布式K-匿名激勵(lì)機(jī)制存在一些不足引言大多依賴于可信第三方服務(wù)器構(gòu)建匿名區(qū)域，破壞了分布式K-匿名的結(jié)構(gòu)，同時(shí)，在難以找到可信第三方服務(wù)器的LBS中也無法很好地?cái)U(kuò)展忽略了用戶的惡意策略，這將威脅用戶的位置隱私，影響激勵(lì)機(jī)制的有效性協(xié)作者提交假位置請(qǐng)求者泄露位置信息為解決上述問題，本章提出了一種隱私增強(qiáng)的分布式K-匿名激勵(lì)機(jī)制引言基于拍賣理論，使LSP充當(dāng)拍賣商，并決定請(qǐng)求者與協(xié)作者之間的貨幣交易關(guān)系實(shí)現(xiàn)了從協(xié)作者到請(qǐng)求者的位置傳輸，從而實(shí)現(xiàn)了匿名區(qū)域的構(gòu)建設(shè)計(jì)了角色識(shí)別機(jī)制和追責(zé)機(jī)制來約束用戶的惡意策略引言預(yù)備知識(shí)機(jī)制設(shè)計(jì)機(jī)制分析實(shí)驗(yàn)本章小結(jié)思考題目LBS中隱私增強(qiáng)的分布式K-匿名激勵(lì)機(jī)制預(yù)備知識(shí)系統(tǒng)模型本章系統(tǒng)模型主要由三個(gè)實(shí)體組成，每個(gè)實(shí)體的角色如下所示請(qǐng)求者：尋求幫助以構(gòu)建匿名區(qū)域的請(qǐng)求者首先向LSP提交他們的身份IDs、所需匿名區(qū)域的大小（匿名需求）和愿意支付的最高價(jià)格（出價(jià)）。拍賣結(jié)束后，獲勝的請(qǐng)求者向LSP支付費(fèi)用預(yù)備知識(shí)系統(tǒng)模型LSP：誠實(shí)且好奇的LSP作為拍賣商負(fù)責(zé)確定拍賣結(jié)果。隨后，LSP向獲勝用戶頒發(fā)由其簽名的角色證書，根據(jù)預(yù)先設(shè)計(jì)的分配策略決定位置傳輸關(guān)系，并將位置傳輸關(guān)系簽名后發(fā)送給獲勝協(xié)作者預(yù)備知識(shí)系統(tǒng)模型協(xié)作者：協(xié)作者首先提交他們的IDs以及愿意接受的最低價(jià)格（要價(jià)）至LSP，拍賣結(jié)束后，獲勝的協(xié)作者根據(jù)位置傳輸關(guān)系將其位置發(fā)送給獲勝的請(qǐng)求者。最后，只有當(dāng)請(qǐng)求者確認(rèn)他們沒有提供虛假位置后，LSP才能為獲勝的協(xié)作者分發(fā)報(bào)酬預(yù)備知識(shí)問題定義定義10.1（密封雙向拍賣）密封雙向拍賣可以被視為一個(gè)元組，其中、分別是請(qǐng)求者集合和協(xié)作者集合，表示用戶的策略集，表示用戶的效用

定義10.2（位置傳輸博弈）位置傳輸博弈可以視為一個(gè)元組，其中、

分別是中的獲勝的請(qǐng)求者集合和協(xié)作者集合，表示用戶的策略，表示用戶的效用預(yù)備知識(shí)威脅模型本章機(jī)制認(rèn)為L(zhǎng)SP是一個(gè)誠實(shí)但好奇的實(shí)體，這意味著LSP將嚴(yán)格遵守拍賣協(xié)議，但可能對(duì)用戶的位置信息感興趣。此外，惡意用戶之間不存在信任關(guān)系，這意味著用戶可能會(huì)根據(jù)惡意策略最大化其個(gè)人效用。這里介紹兩個(gè)外部攻擊者，包括A和A*，A可以說服誠實(shí)但好奇的LSP泄露用戶的位置信息，A*可以說服惡意用戶威脅其他用戶的位置隱私，并影響激勵(lì)效果A可能會(huì)勸說LSP，令其推斷出所有用戶的位置信息A*可能會(huì)讓請(qǐng)求者冒充協(xié)作者參與拍賣A*可能會(huì)讓獲勝請(qǐng)求者泄露他們收到的位置信息A*可能會(huì)讓獲勝協(xié)作者在匿名區(qū)域構(gòu)建中提交虛假位置為了獲得用戶的位置，攻擊者A和A*可能會(huì)串通共謀，以交換用戶的位置信息預(yù)備知識(shí)拍賣目標(biāo)個(gè)體理性：在提交真實(shí)報(bào)價(jià)和時(shí)，用戶的效用應(yīng)該是非負(fù)的，其中，真實(shí)報(bào)價(jià)和分別等于隱私價(jià)值和協(xié)助成本真實(shí)性：請(qǐng)求者和協(xié)作者都不能通過提交虛假的和來提高其效用，也就是說，當(dāng)他們提交真實(shí)報(bào)價(jià)時(shí)，效用應(yīng)該最大化計(jì)算效率：拍賣結(jié)果應(yīng)在多項(xiàng)式時(shí)間內(nèi)確定滿意率：在拍賣中獲勝的用戶數(shù)量應(yīng)該最大化抵抗角色欺騙攻擊：謊報(bào)其角色的惡意請(qǐng)求者無法獲得任何隱私保護(hù)，這意味著隱私目標(biāo)請(qǐng)求者的隱私：獲勝請(qǐng)求者可以從協(xié)作者處收集真實(shí)位置信息，并構(gòu)建匿名區(qū)域來保護(hù)其位置隱私協(xié)作者的隱私：獲勝請(qǐng)求者不能泄露獲勝協(xié)作者的位置信息這意味著位置傳輸博弈的納什均衡是參與者的誠實(shí)策略，其中LBS中隱私增強(qiáng)的分布式K-匿名激勵(lì)機(jī)制引言預(yù)備知識(shí)機(jī)制設(shè)計(jì)機(jī)制分析實(shí)驗(yàn)本章小結(jié)思考題目機(jī)制設(shè)計(jì)盡管現(xiàn)有的激勵(lì)機(jī)制能夠激勵(lì)大多數(shù)用戶參與匿名區(qū)域構(gòu)建，但他們依賴于可信第三方服務(wù)器忽略了用戶的惡意策略為了解決上述問題，本節(jié)提出了一種激勵(lì)機(jī)制，在沒有可信第三方服務(wù)器的情況下，激勵(lì)用戶協(xié)助，同時(shí)約束用戶的惡意策略。所提機(jī)制由三個(gè)模塊組成，包括匿名區(qū)域構(gòu)建、角色識(shí)別機(jī)制和追責(zé)機(jī)制機(jī)制概述機(jī)制設(shè)計(jì)匿名區(qū)域構(gòu)建：在拍賣過程中，一旦確定了貨幣交易關(guān)系，獲勝的協(xié)作者在位置傳輸過程中直接向獲勝的請(qǐng)求者（非可信第三方服務(wù)器）提交位置。隨后，獲勝的請(qǐng)求者根據(jù)獲取到的位置信息構(gòu)建匿名區(qū)域。機(jī)制概述機(jī)制設(shè)計(jì)為了約束用戶的惡意策略，設(shè)計(jì)了如下兩種機(jī)制。（1）角色識(shí)別機(jī)制：用戶在參與匿名區(qū)域構(gòu)建模塊中的拍賣過程時(shí)，其拍賣角色會(huì)被LSP記錄，因此，只有持有由LSP簽名的請(qǐng)求者角色證書的用戶才能匿名發(fā)起LBS查詢。（2）追責(zé)機(jī)制：在匿名區(qū)域構(gòu)建模塊的位置傳輸過程中，用戶間的位置傳輸關(guān)系被LSP記錄，因此，用戶一旦發(fā)現(xiàn)其位置信息泄露，可以通過追責(zé)機(jī)制起訴和懲罰泄露其位置信息的惡意用戶。機(jī)制概述機(jī)制設(shè)計(jì)匿名區(qū)域構(gòu)建拍賣過程：①確定獲勝者②賬單計(jì)算請(qǐng)求者向LSP提交、匿名需求k以及出價(jià)，其中

。協(xié)作者向LSP提交和要價(jià)。確定獲勝者情況①請(qǐng)求者的數(shù)量大于或等于匿名需求的大小，即m≥k在這種情況下，請(qǐng)求者可以直接構(gòu)建匿名區(qū)域，這意味著所有請(qǐng)求者都是獲勝者，所有協(xié)作者都是失敗者，即機(jī)制設(shè)計(jì)情況②請(qǐng)求者的數(shù)量小于匿名需求的大小，即m<kLSP根據(jù)請(qǐng)求者的出價(jià)按降序?qū)φ?qǐng)求者進(jìn)行排序，根據(jù)協(xié)作者的要價(jià)按遞增順序?qū)ζ渑判蛴脩粽鎸?shí)報(bào)價(jià)時(shí)的效用非負(fù)且最大，同時(shí)，獲勝請(qǐng)求者的數(shù)量x最大，應(yīng)該滿足LSP通過逆向查詢的方法，確定滿足上述條件的獲勝者集合核心出價(jià)核心要價(jià)機(jī)制設(shè)計(jì)EXAMPLE：首先假設(shè)是出價(jià)最低的獲勝請(qǐng)求者，則存在隨后假設(shè)是出價(jià)最低的獲勝請(qǐng)求者，則存在機(jī)制設(shè)計(jì)賬單計(jì)算情況①請(qǐng)求者的數(shù)量大于或等于匿名需求的大小，即m≥k在這種情況下，所有請(qǐng)求者都不需要支付任何費(fèi)用，所有協(xié)作者都無法獲得任何報(bào)酬，即情況②請(qǐng)求者的數(shù)量小于匿名需求的大小，即m<k在這種情況下，請(qǐng)求者需要通過拍賣以構(gòu)建匿名區(qū)域，LSP對(duì)每個(gè)獲勝請(qǐng)求者收取相同的費(fèi)用，每個(gè)獲勝請(qǐng)求者需要支付隨后，LSP將向誠實(shí)的協(xié)作者支付費(fèi)用，每個(gè)誠實(shí)的獲勝協(xié)作者都可以獲得機(jī)制設(shè)計(jì)位置傳輸過程：①請(qǐng)求者和協(xié)作者之間②請(qǐng)求者之間請(qǐng)求者和協(xié)作者之間的位置傳輸以下幾種情況會(huì)導(dǎo)致協(xié)作者的位置信息泄露或請(qǐng)求者的單點(diǎn)故障-協(xié)作者將其位置發(fā)送給多個(gè)可能泄露位置信息的惡意請(qǐng)求者-協(xié)作者多次將其不同時(shí)刻的位置發(fā)送給同一請(qǐng)求者，其軌跡信息將被泄露-所有協(xié)作者將其位置發(fā)送給同一請(qǐng)求者為了避免上述情況，對(duì)協(xié)作者和請(qǐng)求者之間的位置傳輸提出以下要求-每個(gè)獲勝協(xié)作者將其位置信息發(fā)送給從未收到其位置信息的獲勝請(qǐng)求者-每個(gè)獲勝請(qǐng)求者接收到的位置信息應(yīng)盡可能少機(jī)制設(shè)計(jì)為實(shí)現(xiàn)上述目標(biāo)，本節(jié)設(shè)計(jì)了相應(yīng)的位置分配策略，包括如下步驟：初始化：LSP根據(jù)歷史位置傳輸記錄對(duì)獲勝用戶進(jìn)行排序‐根據(jù)獲勝協(xié)作者發(fā)送位置信息的次數(shù)，對(duì)其進(jìn)行降序排列，并將排序后的獲勝協(xié)作者集合放入隊(duì)列‐根據(jù)獲勝請(qǐng)求者接收位置信息的次數(shù)，對(duì)其進(jìn)行升序排列，并將排序后的獲勝請(qǐng)求者集合放入隊(duì)列確定傳輸關(guān)系：為了分別在成功匹配和不成功匹配情況下展示算法執(zhí)行步驟，本節(jié)假設(shè)和、和、和之間沒有傳輸記錄，和之間存在傳輸記錄。機(jī)制設(shè)計(jì)角色識(shí)別機(jī)制拍賣過程結(jié)束后，一旦獲勝請(qǐng)求者向LSP支付了相應(yīng)的費(fèi)用，LSP就會(huì)頒發(fā)由他簽名的角色證書

同樣地，在獲勝協(xié)作者提交其位置后，LSP頒發(fā)由他簽名的角色證書角色位唯一識(shí)別身份角色位唯一識(shí)別身份只有持有該角色證書的請(qǐng)求者才能發(fā)送查詢內(nèi)容，進(jìn)而獲得匿名查詢結(jié)果只有持有該角色證書的誠實(shí)協(xié)作者才能獲得報(bào)酬機(jī)制設(shè)計(jì)追責(zé)機(jī)制有研究者指出，如果用戶的日常生活被騷擾，則可以推斷用戶的位置信息被泄露。具體而言，攻擊者通常向廣告商提供LBS用戶的位置，以獲取額外的非法收益，廣告商則根據(jù)用戶的位置，向用戶投放有針對(duì)性的廣告。此外，中國(guó)消費(fèi)者協(xié)會(huì)曾指出，被泄露位置信息的用戶可能會(huì)收到大量欺詐電話、垃圾郵件，并遭受財(cái)產(chǎn)或時(shí)間的損失。因此，在意識(shí)到其信息被泄露時(shí)，請(qǐng)求者和協(xié)作者可以通過追責(zé)機(jī)制檢測(cè)并懲罰導(dǎo)致用戶位置信息泄露的惡意用戶。在本節(jié)設(shè)計(jì)的機(jī)制中，存在如下兩種類型的惡意用戶。

機(jī)制設(shè)計(jì)

惡意協(xié)作者提交虛假位置請(qǐng)求者基于協(xié)作者的虛假位置構(gòu)建不合理的匿名區(qū)域并發(fā)起查詢后，將發(fā)現(xiàn)其位置隱私收到位置，即可向LSP報(bào)告，對(duì)此，LSP能夠采用現(xiàn)有工作中提出的虛假位置鑒別方法，檢測(cè)匿名區(qū)域中哪個(gè)位置是虛假的。被發(fā)現(xiàn)后，惡意協(xié)作者的效用為惡意請(qǐng)求者泄露位置信息-若請(qǐng)求者發(fā)現(xiàn)自己的位置信息被泄露，由于其位置僅發(fā)送給代理，則可判斷代理為惡意，LSP勒令其無法再次參與該激勵(lì)機(jī)制-若協(xié)作者發(fā)現(xiàn)自己的位置信息被泄露，由于其位置僅發(fā)送給一個(gè)目標(biāo)請(qǐng)求者，則可判斷該請(qǐng)求者為惡意，LSP勒令其無法再次參與該激勵(lì)機(jī)制考慮到請(qǐng)求者均為隱私敏感用戶，無法進(jìn)行隱私保護(hù)對(duì)其是致命的，因此效用為L(zhǎng)BS中隱私增強(qiáng)的分布式K-匿名激勵(lì)機(jī)制引言預(yù)備知識(shí)機(jī)制設(shè)計(jì)機(jī)制分析實(shí)驗(yàn)本章小結(jié)思考題目機(jī)制分析所提機(jī)制滿足設(shè)計(jì)目標(biāo)，包括個(gè)體理性計(jì)算效率抵抗角色欺騙攻擊請(qǐng)求者的位置隱私協(xié)作者的位置隱私抵抗受限空間識(shí)別抵抗位置跟蹤……

PPT此處不做過多展示，詳情請(qǐng)見正文10.4節(jié)LBS中隱私增強(qiáng)的分布式K-匿名激勵(lì)機(jī)制引言預(yù)備知識(shí)機(jī)制設(shè)計(jì)機(jī)制分析實(shí)驗(yàn)本章小結(jié)思考題目實(shí)驗(yàn)

實(shí)驗(yàn)設(shè)置參數(shù)和數(shù)據(jù)集設(shè)置：分別采用了模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集。在模擬實(shí)驗(yàn)中，假設(shè)隨機(jī)區(qū)域中有1000個(gè)用戶，包括500個(gè)請(qǐng)求者和500個(gè)協(xié)作者在真實(shí)實(shí)驗(yàn)中，使用了兩個(gè)真實(shí)數(shù)據(jù)集，包括Gowalla和UrbanDataReleaseV2對(duì)比指標(biāo)：激勵(lì)有效性：本章機(jī)制激勵(lì)用戶參與匿名區(qū)域的構(gòu)建，還放棄了惡意策略。第一個(gè)激勵(lì)由拍賣成功率決定，只有拍賣成功才能激勵(lì)協(xié)作者。第二個(gè)激勵(lì)反映在用戶效用上，如果惡意用戶的效用低于誠實(shí)用戶的效用，惡意用戶的惡意策略將被約束設(shè)計(jì)有效性：本章機(jī)制設(shè)計(jì)了位置傳輸過程，該過程可能導(dǎo)致協(xié)作者的軌跡信息泄露和請(qǐng)求者的沉重負(fù)載。因此，為了驗(yàn)證其有效性，本節(jié)測(cè)試了協(xié)作者的軌跡信息泄露率，以及請(qǐng)求者接收位置的平均最大數(shù)量計(jì)算開銷：本節(jié)測(cè)試了本章機(jī)制的計(jì)算開銷，并進(jìn)一步將其與現(xiàn)有機(jī)制進(jìn)行對(duì)比，以反映上述工作的計(jì)算可行性實(shí)驗(yàn)

激勵(lì)有效性–拍賣成功率（a）在仿真中k=150，r=1000（b）在仿真中m,n=120，r=1000（c）數(shù)據(jù)集Gowalla，k=35，r=1000（d）數(shù)據(jù)集Gowalla，m,n=25，r=1000（e）數(shù)據(jù)集UrbanDataReleaseV2，k=35，r=1000（f）數(shù)據(jù)集UrbanDataReleaseV2m,n=25，r=1000實(shí)驗(yàn)

激勵(lì)有效性–用戶效用（a）請(qǐng)求者的個(gè)人效用（b）請(qǐng)求者的總效用（c）協(xié)作者的個(gè)人效用（d）協(xié)作者的總效用實(shí)驗(yàn)

設(shè)計(jì)有效性–軌跡信息泄露率（a）在仿真中k=150，r=10000（b）在仿真中m,n=120，k=150（c）數(shù)據(jù)集Gowalla，k=35，r=1000（d）數(shù)據(jù)集Gowalla，m,n=25，k=35（e）數(shù)據(jù)集UrbanDataReleaseV2，k=35，r=1000（f）數(shù)據(jù)集UrbanDataReleaseV2m,n=25，k=32實(shí)驗(yàn)

設(shè)計(jì)有效性–接收位置的平均最大數(shù)量（a）在仿真中k=150，r=5000（b）在仿真中m,n=120，k=150（c）數(shù)據(jù)集Gowalla，k=35，r=1000（d）數(shù)據(jù)集Gowalla，m,n=25，k=35（e）數(shù)據(jù)集UrbanDataReleaseV2，k=35，r=1000（f）數(shù)據(jù)集UrbanDataReleaseV2m,n=25，k=35實(shí)驗(yàn)

設(shè)計(jì)有效性–接收位置的平均最大數(shù)量（a）n=25，k=35，r=1000（b）m=25，k=35，r=1000（c）m=25，n=25，r=1000（d）m=25，n=25，k=35LBS中隱私增強(qiáng)的分布式K-匿名激勵(lì)機(jī)制引言預(yù)備知識(shí)機(jī)制設(shè)計(jì)機(jī)制分析實(shí)驗(yàn)本章小結(jié)思考題目本章小結(jié)

總結(jié)本章提出了一種隱私增強(qiáng)的激勵(lì)機(jī)制，能夠在沒有可信第三方服務(wù)器的情況下實(shí)現(xiàn)K-匿名