簡易檢索 / 詳目顯示

回結果列表
研究生： 鍾子淵
Chung, Tzu-Yuan
論文名稱： 權衡空間隱私與效能之最短路徑計算
Incentives for Spatial Privacy Tradeoff on Shortest Path Computation
指導教授： 莊坤達
Chuang, Kun-Ta
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2015
畢業學年度： 103
語文別： 英文
論文頁數： 40
中文關鍵詞： 適地性服務 、LBS 、位置隱私 、獎勵機制 、最短路徑查詢
外文關鍵詞： location-based services, LBS, location privacy, incentive mechanism, shortest path query
相關次數： 點閱：97  下載：3 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 隨著智慧型手持裝置和定位系統的發展和普及，人們可在隨時隨地獲得自己的位置訊息的同時方便地使用各種適地性服務(Location Based Service, LBS)， LBS要求使用者在向適地性服務伺服器提出服務請求時，也必須向其提供自身的位置訊息，然而人們在享受各種位置服務帶來便捷的同時，也要考慮位置隱私洩漏帶來的危害。例如，用戶尋找距離最近的醫院，由此可得知使用者的健康狀況。

    僅管在文獻上已提出許多保護位置隱私的機制，但在現實考量上仍有許多商業上的衝突。在市場上的LBS通常提供用戶免費的服務，服務提供商希望藉由免費的服務換取使用者們的喜好或行為。此外，至今為止文獻上的機制皆需要服務端付出更多的計算成本以保護用戶的位置隱私，在應用性上偏離服務提供商的期盼，乃是無法在現時中實現的原因。

    本文提供新的LBS架構，可將位置隱私視為可交換的籌碼，提供彈性的策略讓使用者自行決定洩漏的個人隱私程度，用以交換計算最短路徑查訊的成本負擔，而同時能夠不讓使用者洩漏精確的經緯度座標資訊。

    Privacy preservation has been recognized as an important concern when we access online applications. The issue becomes amplified in Location-Based Services since location-dependent search inevitably discloses personally sensitive information such as home and the working location. In this talk, we review the state-of-the-art in the literature and also discuss their advantages and disadvantages. We also discuss our idea to enhance the feasibility.

    中文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 System Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 The GRASP Processing Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1 System Model Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 The Query Generation in Personalized Privacy on the Client-side . . . . . . . . 15 3.3 GRASP-aware Query Processing Algorithms on the Server-side . . . . . . . . . . 17 3.3.1 Obfuscation-based Mechanism . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3.2 Ensemble of Regional-Shortest-Paths Mechanism . . . . . . . . . . . . . 18 3.3.3 Path Recovery Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.4 Candidate Path Filter on the Server-side . . . . . . . . . . . . . . . . . . 21 3.4 GRASP-aware Query Processing Algorithms on the Client-side . . . . . . . . . . 23 3.4.1 Interlace-based Network Expansion . . . . . . . . . . . . . . . . . . . . . 24 4 Trade-off between anonymity and QoS for users . . . . . . . . . . . . . . . . . . . . . 27 5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.1 Experimental Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.2 Evaluation of shielding factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.3 Evaluation on Grid Cell Width: 4 Trade-off between anonymity and QoS for users . . . . . . . . . . . . . . . . . . . . . 27 5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.1 Experimental Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.2 Evaluation of shielding factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.3 Evaluation on Grid Cell Width . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.4 Evaluation on Fanout. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.5 Effectiveness of Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.6 Performance of the Pseudonym Mechanism . . . . . . . . . . . . . . . . . . . . . 34 5.7 Experiments on Larger Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

    [1] S. Schoen and E. Galperin, “Iranian man-in-the-middle attack against google
    demonstrates dangerous weakness of certificate authorities,” August 2011, [Online;
    posted 29-August-2011]. [Online]. Available: https://www.eff.org/deeplinks/2011/08/
    iranian-man-middle-attack-against-google
    [2] A. Krause and E. Horvitz, “A utility-theoretic approach to privacy in online services,”
    J. Artif. Int. Res., Sep. 2010. [Online]. Available: http://dl.acm.org/citation.cfm?id=
    1946417.1946431
    [3] Y. Manolopoulos, A. Nanopoulos, A. N. Papadopoulos, and Y. Theodoridis, R-Trees:
    Theory and Applications, 1st ed. Springer, Sep. 2005.
    [4] J. KLOC, “Yahoo fought the nsa’s prism program in court,” September 2014,
    [Online; posted 9-September-2014]. [Online]. Available: http://www.newsweek.com/
    yahoo-fought-nsas-prism-program-court-270130
    [5] C. S. Jensen, H. Lu, and M. L. Yiu, “Location privacy techniques in client-server
    architectures.” in Privacy in Location-Based Applications, ser. Lecture Notes in Computer
    Science, C. Bettini, S. Jajodia, P. Samarati, and X. S. Wang, Eds. Springer. [Online].
    Available: http://dblp.uni-trier.de/db/conf/esorics/lncs5599.html#JensenLY09
    [6] J. Krumm, “A survey of computational location privacy,” Personal Ubiquitous Comput.
    [Online]. Available: http://dx.doi.org/10.1007/s00779-008-0212-5
    [7] C.-Y. Chow, M. F. Mokbel, and X. Liu, “A peer-to-peer spatial cloaking algorithm for
    anonymous location-based service,” Proc. of the ACM GIS, 2006.
    [8] G. Ghinita, P. Kalnis, and S. Skiadopoulos, “Mobihide: A mobilea peer-to-peer system for
    anonymous location-based queries,” Proc. of SSTD, 2007.
    [9] G. Ghinita, P. Kalnis, and S. Skiadopoulus, “Prive: Anonymous location-based queries in
    distributed mobile systems,” Proc. of the ACM WWW Conf., 2007.
    [10] M. Gruteser and D. Grunwald, “Anonymous usage of location-based services through spatial
    and temporal cloaking,” Proc. of the ACM MobiSys Conf., 2003.
    38
    [11] M. F. Mokbel, C.-Y. Chow, and W. G. Aref, “The new casper: Query processing for
    location services without compromising privacy,” Proc. of VLDB, 2006.
    [12] K. Mouratidis and M. L. Yiu, “Shortest path computation with no information leakage,”
    PVLDB, vol. 5, no. 8, pp. 692–703, 2012.
    [13] P. Kalnis, G. Ghinita, K. Mouratidis, and D. Papadias, “Preventing location-based identity
    inference in anonymous spatial queries.” IEEE Trans. Knowl. Data Eng., 2007. [Online].
    Available: http://dblp.uni-trier.de/db/journals/tkde/tkde19.html#KalnisGMP07
    [14] L. Sweeney, “K-anonymity: A model for protecting privacy,” Int. J. Uncertain.
    Fuzziness Knowl.-Based Syst., Oct. 2002. [Online]. Available: http://dx.doi.org/10.1142/
    S0218488502001648
    [15] M. Duckham and L. Kulik, “A formal model of obfuscation and negotiation for location
    privacy,” Proc. of the IEEE PERVASIVE, 2005.
    [16] Y. Hidetoshi Kido, Yanagisawa, and T. Satoh, “An anonymous communication technique
    using dummies for location-based services,” Proc. of the IEEE ICPS Conf., pp. 88–97,
    2005.
    [17] K. C. Lee, W.-C. Lee, H. V. Leong, and B. Zheng, “Navigational path privacy protection:
    Navigational path privacy protection,” Proc. of the ACM CIKM Conf., 2009.
    [18] H. Hu, J. Xu, C. Ren, and B. Choi, “Processing private queries over untrusted data cloud
    through privacy homomorphism,” Proc. of the IEEE ICDE Conf., 2011.
    [19] A. Khoshgozaran and C. Shahabi, “Blind evaluation of nearest neighbor queries using
    space transformation to preserve location privacy,” Proc. of SSTD, 2007.
    [20] W. K. Wong, D. W.-l. Cheung, B. Kao, and N. Mamoulis, “Secure knn computation on
    encrypted databases,” Proc. of the ACM SIGMOD, 2009.
    [21] P.-Y. Li, W.-C. Peng, T.-W. Wang, W.-S. Ku, J. Xu, J. Hamilton et al., “A cloaking
    algorithm based on spatial networks for location privacy,” in Sensor Networks, Ubiquitous
    and Trustworthy Computing, 2008. SUTC’08. IEEE International Conference on. IEEE,
    2008.
    [22] K. Mouratidis and M. L. Yiu, “Anonymous query processing in road networks.” IEEE
    Trans. Knowl. Data Eng., 2010.
    [23] T. Wang and L. Liu, “Privacy-aware mobile services over road networks,” Proc. VLDB
    Endow., Aug. 2009. [Online]. Available: http://dl.acm.org/citation.cfm?id=1687627.
    1687745
    [24] P. Williams and R. Sion, “Usable pir.” in NDSS, 2008. [Online]. Available:
    http://dblp.uni-trier.de/db/conf/ndss/ndss2008.html#WilliamsS08
    [25] P. Bright, “Gov’t, certificate authorities conspire to spy on ssl users?” 2010,
    [Online; posted 29-Mar-2010]. [Online]. Available: http://arstechnica.com/security/2010/
    03/govts-certificate-authorities-conspire-to-spy-on-ssl-users/
    [26] H. Hwang, G. Jung, K. Sohn, and S. Park, “A study on mitm (man in the middle)
    vulnerability in wireless network using 802.1x and eap,” Proc. of ICIS, 2008.
    [27] B. Gedik and L. Liu, “Protecting location privacy with personalized k-anonymity: Architecture
    and algorithms,” TMC, 2008.
    [28] K. C. Lee, W.-C. Lee, B. Zheng, and Y. Tian, “Road: A new spatial object search framework
    for road networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 24,
    no. 3, pp. 547–560, 2012.
    [29] K. C. K. Lee, W.-C. Lee, and B. Zheng, “Fast object search on road networks,” Proc. of
    EDBT, 2009.
    [30] “9th dimacs implementation challenge - shortest paths.” [Online]. Available: http:
    //www.dis.uniroma1.it/challenge9/index.shtml
    [31] F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, and S.-H. Teng, “On trip planning queries
    in spatial databases,” Proc. of SSTD, 2005.

    下載圖示 校內：2017-08-28公開
    校外：2017-08-28公開
    QR CODE