基于橢圓曲線的ElGamal型位置隱私保護方案

賴慧彬，許力，曾雅麗，朱瑞

基于橢圓曲線的ElGamal型位置隱私保護方案

賴慧彬1,2，許力1,2，曾雅麗1,2，朱瑞1,2

（1. 福建師范大學數學與信息學院，福建 福州 350007； 2. 福建省網絡安全與密碼技術重點實驗室，福建 福州 350007）

針對協作頻譜感知場景下次用戶的位置隱私問題，提出一種基于橢圓曲線的ElGamal型位置隱私保護方案。首先，次用戶通過橢圓曲線上的ElGamal公鑰密碼體制加密原始感知報告后發送給可信第三方；其次，可信第三方對加密后的感知報告進行第一次解密，并且混淆后，發送給融合中心；再次，融合中心進行第二次解密操作后得到原始感知報告；最后，分析該方案的安全性。該方案使感知報告的加密方式基于橢圓曲線上的公鑰密碼體制，并使可信第三方對感知報告進行混淆，實現了次用戶位置隱私的保護。同時，與其他方案相比，該方案有效地降低了通信開銷和存儲開銷。此外，該方案具有容錯機制和動態機制，增強了方案的實用性。

位置隱私保護；橢圓曲線；ElGamal；協作頻譜感知

1 引言

無線頻譜是非常珍貴的通信資源。現有的靜態頻譜分配方案導致頻譜資源利用低[1]，美國聯邦通信委員會（FCC，Federal Communications Commission）調查統計發現無線頻譜的利用率在15%~85%。而且隨著智能手機和平板電腦等移動通信設備的普及，人們對無線頻譜資源的需求日益增加[2]，這使有限的頻譜資源更加緊張。為了解決這一問題，Mitola等[3]提出了認知無線電（CR，cognitive radio）技術。認知無線網絡（CRN，cognitive radio networks）是基于認知無線電技術的一種網絡。在認知無線網絡中有主用戶（PU，primary user）和次用戶（SU，secondary user）兩類用戶。主用戶擁有授權頻譜，可隨時訪問自己的頻譜資源，目前主用戶主要包括衛星通信、電視廣播等。次用戶只有在主用戶空閑時，才能使用主用戶的頻譜資源[4]。一旦主用戶上線，次用戶需立即下線；或者在不干擾主用戶正常通信的前提下[5]，可以和主用戶同時使用頻譜資源。次用戶要想使用空閑頻譜，首先需要進行頻譜感知[6]。具有認知功能的次用戶通過信號檢測方法尋找頻譜空洞。由于能量檢測方法容易實現且不需要主用戶的任何先驗信息，已成為認知無線網絡中最常用的頻譜感知方法。它通過對比接收信號強度（RSS，received signal strength）[7]和設定的門限值，來判斷主用戶的頻譜資源是否空閑。若小于門限值，則認為主用戶不在線，次用戶可接入使用頻譜；若大于門限值，則認為主用戶在線，次用戶不可接入使用頻譜。

協作頻譜感知（CSS，collaborative spectrum sensing）通過收集不同感知區域單個次用戶的頻譜感知信息并作出綜合分析，克服了多徑效應、陰影效應等隱藏終端問題，提高了頻譜感知結果的準確性。協作頻譜感知場景一般分為集中式和分布式[8]。在集中式場景下，存在一個中心控制節點，稱為融合中心（FC，fusion center）。首先，融合中心通過控制信道發布感知任務；然后，次用戶通過統一的頻譜感知方式，獲得基于自身位置的感知報告，發送給融合中心；接著，融合中心根據融合算法，整合分析頻譜感知報告并公布融合結果，次用戶根據融合結果申請接入頻譜。控制信道是融合中心和次用戶之間通信的信道。而在分布式場景下，次用戶之間互相分享頻譜感知報告，并經過協商分析得出頻譜感知結果[9]。

協作頻譜感知在提高感知結果準確性[10-11]的同時引入了一些安全問題。由于RSS值與位置相關，因此攻擊者可以從基于RSS值的感知報告中推斷次用戶的位置[12]，進而對次用戶的其他隱私信息進行進一步的推測，如生活習慣、宗教信仰、健康情況等，帶來嚴重的隱私泄露問題[13]。意識到這些潛在的威脅，次用戶可能不愿參與到協作感知中，從而阻礙了認知無線網絡的發展。因此，在協作感知場景下，針對次用戶位置隱私保護的問題，目前已有的解決方案是隱私保護融合技術。這種技術保證融合中心可以得到融合結果，但不會泄露每個次用戶的感知報告。Li等[12]提出的位置隱私保護的協作頻譜感知（PPSS，privacy preserving collaborative spectrum sensing）方案就是基于這種技術。在他們的方案中，任意兩個次用戶之間隨機生成一組密鑰對，最終每個次用戶的私鑰是由和其他次用戶共享的單個密鑰累加后決定的。次用戶用私鑰加密感知報告后發送給融合中心。融合中心通過窮舉法解決一個離散對數問題就可以得出最終的融合結果。在這個過程中，融合中心不知道次用戶的感知報告，因此保護了次用戶的位置隱私。但由于任意兩個次用戶之間需要共享一組密鑰對，帶來較大的通信開銷。

Wang等[14]提出的PrimCos（privacy preservation framework for multi-SP collaborative sensing）方案是基于多個服務提供商下的協作頻譜感知場景。每個服務提供商管轄特定次用戶群，收集管轄區域內每個次用戶的感知報告，多個服務提供商之間協同處理這些感知報告。PrimCos引入了差分隱私策略來保護次用戶的感知報告。

Chen等[15]指出，感知報告經過加密發送給融合中心，融合中心需要解密感知報告才能進行融合并得到感知結果。但由于融合中心可能是不可信的，為了讓融合中心得到解密后的感知報告后，并不能匹配到感知報告的隸屬者，Chen等從次用戶中輪流選擇一個次用戶作為協助者，并使用改進的ElGamal公鑰密碼體制[16]，使經過加密的感知報告通過兩次解密才能恢復。次用戶加密原始感知報告后發送給協助者，協助者先進行打亂感知報告的位置再執行第一次解密操作。第二次解密操作由融合中心執行，融合中心得到原始感知報告后再進行融合。筆者認為，經過打亂操作，融合中心并不知道其解密的感知報告屬于哪個次用戶。但打亂操作只是改變感知報告的相對位置，其里面的第一項內容還是不變的。因此，半可信的融合中心可以通過竊取加密后的所有感知報告對，再和經過協助者打亂以及第一次解密后的所有感知報告對，比較其第一項內容，匹配感知報告的隸屬者。

針對文獻[15]方案中存在的不足，本文在此基礎上提出了一種橢圓曲線和ElGamal算法相結合的位置隱私保護方案。

2 系統模型與假設

2.1 系統模型

本文考慮一種集中式的協作頻譜感知場景[17]，如圖1所示。該場景包括以下幾個實體：融合中心、主用戶、次用戶和可信第三方（TPA，trusted property authority）。可信第三方是經過FCC授權的實體[18]，具有強大的計算能力，負責生成系統參數、參與感知報告解密和混淆工作。

圖1 集中式協作頻譜感知場景

Figure 1 Centralized cooperative spectrum sensing

假設個主用戶PU(1,2,...,)各自擁有授權頻譜，個次用戶SU(1,2,...,)隨機分布在主用戶周圍，每個次用戶都能進行頻譜感知，且隨時準備接入空閑頻譜。集中式協作頻譜感知過程如下。

1) 發布感知任務：融合中心通過控制信道通知次用戶去感知主用戶的信號。

2.2 攻擊模型與假設

攻擊者的目的是獲悉次用戶的位置信息，攻擊者可能來自外部人員，也可能是內部某個惡意次用戶，甚至是半可信的融合中心。半可信的融合中心一方面會“誠實”地融合感知報告，另一方面會“好奇”地伺探次用戶的位置信息。融合中心可以通過竊聽的方式獲得一些信息，然后根據這些信息推斷出被攻擊者的位置。惡意的次用戶不僅想要獲得內部其他次用戶的位置隱私，同時可能會提交虛假的感知報告擾亂協作頻譜感知過程。此外，如果攻擊者是次用戶，本文允許次用戶之間以及次用戶和外部人員采取合謀的方式進行攻擊。

本文方案的目的是確保融合結果的有效性，同時防止攻擊者獲得次用戶的位置信息。

本文假設次用戶在較長一段時間內是靜止的，次用戶之間有直接的通信信道，此外，惡意次用戶的數量不超過次用戶總數的一半。

2.3 基于橢圓曲線的ElGamal公鑰密碼算法

2.3.1 橢圓曲線

2.3.2 橢圓曲線和ElGamal相結合

ElGamal[21]是基于有限域上離散對數問題的公鑰密碼算法，可以將ElGamal直接平移到橢圓曲線群上，形成基于橢圓曲線的ElGamal公鑰密碼算法。

3 位置隱私保護方案

本文提出基于橢圓曲線的ElGamal型位置隱私保護方案（LPP-ECEG，location privacy-preserving scheme based on elliptic curve ElGamal）。方案主要包括4個階段：初始化過程、次用戶加密感知報告、可信第三方解密和混淆感知報告、融合中心解密感知報告。下文中的符號說明見表1。

表1 符號說明

3.1 初始化過程

3.2 次用戶加密感知報告

算法1 次用戶加密感知報告

3.3 可信第三方解密和混淆感知報告

算法2 可信第三方解密和混淆感知報告

3.4 融合中心解密感知報告

算法3 融合中心解密感知報告

4 方案評估

4.1 有效性分析

（1）加密階段

（2）可信第三方解密和混淆階段

（3）融合中心解密階段

此外，惡意次用戶可能會提交虛假的感知報告，那么融合中心經過解密后獲得的也是虛假的感知報告。文獻[23]中指出，錯誤的感知報告所占比重小于總數一半的情況下，融合結果不受其影響。2.2節假設惡意次用戶的數量在總數一半之內，因此在這種情況下，能確保融合結果的有效性。

4.2 安全性分析

本節分析LPP-ECEG方案可以抵抗來自外部人員、內部次用戶以及半可信融合中心的攻擊。

綜上所述，LPP-ECEG方案很好地保護了次用戶的位置隱私。

4.3 性能分析

4.1節證明了次用戶無論提交正確或者虛假的感知報告，融合中心最終都會得出有效的融合結果。由于網絡故障問題，部分次用戶可能提交感知報告失敗。在這種情況下，LPP-ECEG方案還能保證融合中心得出最終的融合結果。在LPP-ECEG方案中，融合結果的得出取決于融合中心是否可以解密收到的感知報告。因為解密感知報告的兩個私鑰是由可信第三方基于橢圓曲線群生成的，并和融合中心各自保存。且所有經過公鑰加密的感知報告，可信第三方和融合中心都根據這兩個私鑰依次解密，感知報告數量的多少并不影響解密，融合中心還能得出最終的頻譜感知結果，所以LPP-ECEG方案支持容錯機制。

同理，當多個次用戶同時加入或者退出協作頻譜感知過程時，并不影響可信第三方和融合中心解密感知報告，融合中心還能進行融合，即LPP-ECEG方案支持動態機制。表2是LPP-ECEG方案與文獻[15]方案和PPSRA方案的對比。

表2 3種方案對比

4.4 開銷分析

本節分析LPP-ECEG方案的計算、通信和存儲開銷，并和其他方案進行對比。

4.4.1 計算開銷

根據文獻[24]，不同密鑰長度下的橢圓曲線點乘和點加運算時間如表3所示。假設有10個次用戶參與協作頻譜感知，所有次用戶、可信第三方以及融合中心分別的計算開銷如圖2所示。可信第三方執行主要的計算操作。由于可信第三方是系統引入的具有強大計算能力的實體，因此計算開銷在其能力允許范圍內。次用戶通常是一些移動設備，計算能力較弱，由圖2可以看出，次用戶承擔少量的計算操作。融合中心不僅要參與位置隱私保護方案，還要融合感知報告，為了避免其負擔過重，本文考慮盡量減少融合中心的計算開銷。由圖2可知，融合中心承擔的計算開銷最小。因此，LPP-ECEG方案在計算開銷方面是可行的。表4給出了LPP-ECEG方案和其他方案的計算開銷對比。LPP-ECEG方案的不足在于，引入可信第三方產生了一些額外系統開銷，因此下一步工作是考慮輕量級的位置隱私保護方案。

圖2 不同實體的計算開銷對比

Figure 2 Comparisons of computation cost for each entity

表3 不同密鑰長度下兩種密碼學運算的運行時間

4.4.2 通信開銷

表5 3個方案的通信開銷對比

表6 不同加密算法的最小安全密鑰長度

4.4.3 存儲開銷

表7對比了3個方案的存儲開銷。根據表6，LPP-ECEG方案的存儲開銷明顯低于PPSRA方案和文獻[15]中的方案。

表7 存儲開銷對比

表4 3個方案的計算開銷對比

5 結束語

針對協作頻譜感知場景下次用戶位置隱私保護的問題，本文提出了一種橢圓曲線和ElGamal算法相結合的次用戶位置隱私保護方案。次用戶通過橢圓曲線上的ElGamal公鑰密碼體制加密原始感知報告后，發送給可信第三方。可信第三方對加密后感知報告進行第一次解密，然后混淆第一次解密后的感知報告，再發送給融合中心。融合中心進行第二次解密操作后得到原始感知報告。安全分析表明，通過可信第三方對感知報告進行混淆，融合中心無法將感知報告和其擁有者一一匹配。對于其他攻擊者而言，因為需要解決橢圓曲線離散對數問題，其很難獲得次用戶的感知報告。因此，LPP-ECEG方案很好地保護了次用戶的位置隱私。與其他方案對比，LPP-ECEG方案在通信開銷和存儲開銷具有明顯的優勢。與此同時，LPP-ECEG方案具有容錯機制和動態機制，增強了方案的實用性。

[1] SAMEER S, GHOSH C, DHEKNE R P, et al. Graph theoretic approach to QoS-guaranteed spectrum allocation in cognitive radio networks[C]//2008 IEEE International Performance, Computing and Communication Conference. 2008: 354-359.

[2] XU T Y, DARWAZEH I . Non-orthogonal narrowband Internet of things: a design for saving bandwidth and doubling the number of connected devices[J]. IEEE Internet of Things Journal, 2018, 5(3): 2120-2129.

[3] MITOLA J I, MAGUIRE G Q. Cognitive radio: making software radios more personal[J]. IEEE Personal Communications, 1999, 6(4): 13-18.

[4] 仝偉, 毛云龍, 陳慶軍, 等. 抗大數據分析的隱私保護: 研究現狀與進展[J]. 網絡與信息安全學報, 2016, 2(4): 44-55.

TONG W, MAO Y L, CHEN Q J, et al. Survey of big-data-analysis-resistant privacy protection[J]. Chinese Journal of Network and Information Security. 2016, 2(4): 44-55.

[5] FCC. Spectrum inventory table[EB].

[6] SESHUKUMAR K, SARAVANAN R, SURAJ M S. Spectrum sensing review in cognitive radio[C]//2013 International Conference on Emerging Trends in VLSI, Embedded System, Nano Electronics and Telecommunication System(ICEVENT). 2013: 1-4.

[7] GUNTER C A, FATEMIETH O, FARHADI A, et al. Using classification to protect the integrity of spectrum measurements in white space networks[C]//NDSS. 2011: 242-251.

[8] AKYILDIZ I F, LO B F, BALAKRISHNAN R. Cooperative spectrum sensing in cognitive radio networks: a survey[J]. Physical Communication, 2011, 4(1): 40-62.

[9] 裴慶祺, 李紅寧，趙弘洋, 等. 認知無線電網絡安全綜述[J].通信學報, 2013, (1): 144-158.

PEI Q Q, LI H N, ZHAO H Y, et al. Security in cognitive radio networks[J]. Journal on Communications. 2013, (1): 144-158.

[10] MIN A W, ZHANG X Y, SHIN K G . Detection of small-scale primary users in cognitive radio networks[J]. IEEE Journal on Selected Areas in Communications, 2011, 29(2): 349-361.

[11] LI H S. Learning the spectrum via collaborative filtering in cognitive radio networks[C]//2010 IEEE Symposium on New Frontiers in Dynamic Spectrum(DySPAN). 2010: 1-12.

[12] LI S, ZHU H J, GAO Z Y, et al. Location privacy preservation in collaborative spectrum sensing[C]//2012 Proceedings IEEE INFOCOM, 2012:729-737.

[13] GRISSA M, HAMDAOUI B, YAVUZ A A. Location privacy in cognitive radio networks: a survey[J]. IEEE Communications Surveys & Tutorials, 2017, 19(3): 1726-1760.

[14] WANG W, ZHANG Q. Privacy-preserving collaborative spectrum sensing with multiple service providers[J]. IEEE Transactions on Wireless Communications, 2015, 14(2): 1011-1019.

[15] CHEN T T, MAO Y L, ZHANG Y, et al. Protecting location information in collaborative sensing of cognitive radio networks[C]//ACM International Conference on Modeling. 2015: 219-226.

[16] SHENG Z. Privacy, integrity, and incentive-compatibility in computations with untrusted parties[R]. 2004.

[17] RIFà P, HELENA, RIFà C. Spectrum sharing models in cognitive radio[C]//International Conference on Cyber-enabled Distributed Computing & Knowledge Discovery. 2011.

[18] LIU J, ZHANG C, DING H，et al. Policy-based privacy-preserving scheme for primary users in databased-driven cognitive radio networks[C]//2016 IEEE Global Communications Conference (GLOBECOM). 2016: 1-6.

[19] MIN A W, SHIN K G, HU X. Secure cooperative sensing in IEEE 802.22 WRANs using shadow fading correlation[J]. IEEE Transactions on Mobile Computing, 2011, 10(10): 1434-1447.

[20] PRASANNA Y L, READY E M. A theoretical study of elliptic curve cryptography for location based services[C]//2017 International Conference on Big Data Analytics and Computational Intelligence(ICBDAC). 2017: 404-407.

[21] SAIKIA M, BORUAH D. Implementation of ElGamal elliptic curve cryptography over prime field using C[C]//International Conference on Information Communication and Embedded Systems(ICICES2014). 2014: 1-7.

[22] 林淑芬. 基于橢圓曲線的數據加密系統的實現[D]. 廈門: 廈門大學, 2012.

LIN S F. The Implementation of data encryption system based on elliptic curve[D]. Xiamen: Xiamen University, 2012.

[23] TEGUIG D, SCHEERS B, NIR V L. Data fusion schemes for cooperatives spectrum sensing in cognitive radio networks[C]//2012 Military Communications and Information Systems Conference(MCC). 2012: 1-7.

[24] ZENG Y L, XU L, YANG X, et alAn efficient privacy-preserving protocol for database-driven cognitive radio networks, Ad hoc networks[P]. 2018.

[25] 苗新亮, 雷波, 劉棟, 等. OpenSSL中橢圓曲線點的壓縮形式研究[J]. 網絡安全技術與應用, 2015, (10): 92-93.

MIAO X L, LEI B, LIU D, et al. Study on compression form of elliptic curve points in OpenSSL[J]. Network Security Technology & Application, 2015, (10): 92-93.

[26] 李欣，組密鑰管理技術研究及其在IPSec VPN中的應用[D]. 杭州: 浙江大學, 2006.

LI X. Research of group key management and its application in IPSec VPN[D]. Hangzhou: Zhejiang University, 2006.

Elliptic curve ElGamal encryption based location privacy-preserving scheme

LAI Huibin1,2, XU Li1,2, ZENG Yali1,2, ZHU Rui1,2

1. College of Mathematics and Informatics, Fujian Normal University, Fuzhou 350007, China 2. Fujian Provincial Key Laboratory of Network Security and Cryptology, Fuzhou 350007, China

An elliptic curve ElGamal encryption based location privacy-preserving scheme was proposed to address the location privacy problem of secondary users in collaborative spectrum sensing. Firstly, secondary users encrypted the original sensing reports using the ElGamal public key techniques on the elliptic curve and sent them to the trusted property authority. Secondly, the trusted property authority partially decrypted and randomized sensing reports and then sent the randomized sensing reports to the fusion center. Thirdly, the fusion center finally decrypted and got the original sensing reports. Finally, security of the scheme was analyzed. According to the scheme, the encryption method of sensing reports was based on public key cryptography on elliptic curve. And the trusted property authority randomized encrypted sensing reports. Thus the location privacy of secondary users can be protected. Meanwhile, this scheme effectively reduces communication and storage cost, compared with other schemes. In addition, this scheme also has fault tolerant and dynamic mechanism, which increases the practicability and feasibility.

location privacy protection, elliptic curve, ElGamal, collaborative spectrum sensing

TP309

A

10.11959/j.issn.2096?109x.2020031

2019?09?06；

2020?02?18

許力，xuli@fjnu.edu.cn

國家自然科學基金（61771140, U1905211）；福建省科技廳高校產學研項目（2017H6005）；企事業合作項目（DH-1307, DH-1412）

The National Natural Science Foundation of China (61771140, U1905211), Major Science and Technology Project in Fujian Province, China(2017H6005), IUI Cooperation Project (DH-1307, DH-1412)

賴慧彬, 許力, 曾雅麗, 等. 基于橢圓曲線的ElGamal型位置隱私保護方案[J]. 網絡與信息安全學報, 2020, 6(3): 30-38.

LAI H B, XU L, ZENG Y L, et al. Elliptic curve ElGamal encryption based location privacy-preserving scheme[J]. Chinese Journal of Network and Information Security, 2020, 6(3): 30-38.

賴慧彬（1995?），女，福建漳州人，福建師范大學碩士生，主要研究方向為網絡與信息安全。

許力（1970?），男，福建福州人，博士，福建師范大學教授，主要研究方向為網絡與信息安全、無線網絡與通信、云計算與物聯網。

曾雅麗（1990?），女，福建漳州人，福建師范大學博士生，主要研究方向為網絡與信息安全。

朱瑞（1995?），女，福建龍巖人，福建師范大學碩士生，主要研究方向為網絡與信息安全。