隱私保護的網約出行的研究綜述

于海寧,張宏莉, 余翔湛, 曲家興

隱私保護的網約出行的研究綜述

于海寧1,張宏莉1, 余翔湛1, 曲家興2

1哈爾濱工業大學網絡空間安全學院 哈爾濱 中國 1500012黑龍江省網絡空間研究中心 哈爾濱 中國 150001

為高效利用交通資源, 在線網約出行(ORH)服務整合車輛供給和乘客請求信息, 派遣符合條件的車輛提供非巡游的出行服務。人們在享受ORH服務帶來的便利時, 也面臨著嚴重的隱私泄露風險。為此, 許多研究利用密碼學技術設計隱私保護的ORH服務。首先, 本文介紹了隱私保護的ORH服務主要面臨的城市動態場景下高效計算密態行程開銷、實時動態規劃密態行程、安全共享不同ORH服務的運力資源等挑戰。然后, 回顧了歐式距離、路網距離和行駛時間三類行程開銷的安全計算方法, 其中, 歐式距離計算效率高, 但誤差大, 現有路網距離和行駛時長的安全計算方法多數面向靜態路網場景, 針對城市動態路網場景的安全計算方法有待進一步研究。分析了面向司機、乘客、ORH平臺的行程規劃問題的求解方法, 現有研究往往僅針對司機、乘客或ORH平臺的單一目標進行行程規劃, 事實上行程規劃不但要考慮ORH平臺自身收益, 更要同時兼顧乘客和司機的用戶體驗。綜述了隱私感知的行程預處理方法, 單車單客模式、單車多客模式的行程安全共享方法, 并總結了其不足與啟示。多車單客、多車多客動態模式的行程安全共享有待進一步研究。最后, 從城市動態路網下高效的密態行程開銷的安全計算與比較、多方隱私保護的大規模密態行程動態規劃與安全保障、跨服務域的去中心化密態行程協作共享、ORH服務的法律法規合規保證四方面展望了隱私保護的ORH服務的未來研究方向。本文旨在保護多方隱私的前提下, 提高ORH服務質量、促進多ORH服務合作, 使得網約出行更加智慧、更加安全。

位置隱私; 多方安全計算; 網約出行服務; 行程動態共享

1 引言

交通擁堵一直是困擾當代城市發展的主要難題之一, 其增加了人們的出行支出, 損害了人們的身心健康, 且帶來了巨大的社會成本和經濟損失, 例如, 時間價值損失、額外燃料消耗、環境污染加劇、交通事故增加等。交通信息分析公司INRIX的報告指出, 僅2018年美國由堵車造成的經濟損失約為870億美元。北京市交通發展研究中心發布的《2020北京市交通發展年度報告》顯示, 2019年北京市日均擁堵時間超6h。據百度公司測算, 北京市每年因交通擁堵造成數以千億計的經濟損失, 約占北京市GDP的5%。治理交通擁堵已經成為全世界共同關注的問題, 從車輛端進行改革與優化是緩解交通擁堵最直接和最高效的途徑之一。為此, 在移動互聯網與普適計算的推動下, 大量在線網約出行服務(Online Ride Hailing, ORH)紛紛涌現, 例如, Uber, Lyft和滴滴出行。ORH服務是以移動互聯網技術為依托構建的服務平臺, 其整合車輛供給和乘客需求信息, 派遣符合條件的車輛提供非巡游的出行服務。如表1所示, ORH支持多種模式的出行服務, 其中, 出行共享也被稱為“共乘”、“拼車”、“行程共享”, 指多位起點/終點不同的乘客, 經過協商共同乘坐同一輛車并分擔費用的共享出行方式。出行共享讓有限的網約車供給和城市道路資源得到最大化利用, 為構建智慧、高效、綠色的出行生態提供巨大助力。出行共享因其社會和經濟價值已得到廣泛的關注, 用戶規模也呈爆炸式增長。2019年11月29日滴滴出行公司發布數據顯示, 自2015年滴滴拼車上線以來累計有29億人次使用, 最近一年累計行駛45億km, 平均每天為乘客節省等待時間276萬min。

人們在享受ORH服務帶來的便利出行時, 面臨著嚴峻的隱私泄露問題。為使用ORH服務, 用戶需向平臺提交其行程信息, 然而, 行程信息包含了大量的用戶隱私, 例如, 用戶的上下車位置和時段。獲取這些隱私信息后, 攻擊者能夠實時地跟蹤目標用戶, 或者結合背景知識推斷出用戶的生活/工作地址、興趣愛好和經濟狀況等隱私。在ORH服務中, 潛在的攻擊者包括:半可信/惡意的乘客、司機、ORH平臺和外部敵手, 例如, ORH平臺為了獲得額外廣告推送收益, 收集用戶行程信息用來推斷用戶的住址和興趣愛好等; 司機為了跟蹤特定的乘客, 偽造自身狀態向ORH平臺騙取乘客行程; ORH平臺為了贏得商業競爭, 作為外部敵手竊聽或攻擊其他ORH平臺。

表1 ORH 服務的出行服務模式

(注: 1.單車單客靜態模式可視為一種特殊的單車多客靜態出行共享模式, 故未單獨列出。2.多車多客模式可視為多車單客模式的進一步擴展)

已有研究[1-4]揭示了目前主流的ORH服務都存在著不同程度隱私泄露風險, 這些隱私威脅不但會危害用戶個人權益, 而且很可能因違反《數據安全法》和《個人信息保護法》等法律規定導致處罰, 損害平臺聲譽。針對這些隱私威脅, 可以運用隱私保護技術處理原始數據, 改變其形式, 進而避免原始數據中敏感信息的泄露。如圖1所示, 為保護敏感信息, 原始數據可以被變換為去標識化數據、脫敏數據、匿名化數據或加密數據等形式, 一般來說, 雖然它們對應的處理開銷遞增, 但同時也達到了更高的隱私保護強度。相應地, ORH服務的隱私保護解決方案可分為兩類: 一類解決方案是使用-匿名,-多樣性、-近似性或差分隱私等非加密的方法來保護用戶隱私, 但這類方法往往僅能提供有限的隱私保護強度, 且引入的噪聲數據會影響ORH服務質量, 導致行程安排存在誤差或錯誤; 另一類解決方案是采用加密技術, 將乘客請求和車輛狀態加密后上傳至ORH平臺, 數據以密文形式進行傳輸和存儲, ORH平臺/外部敵手無法獲取用戶真實的行程信息, 即使ORH平臺被攻擊后造成數據泄露, 用戶也不擔心自身隱私泄露。此外, 基于加密的方法提供了更高的隱私保護強度, 且避免了噪聲數據添加對服務精度的影響?？紤]到ORH服務對行程規劃的高精度要求, 本文重點關注基于加密技術的隱私保護解決方案。

圖1 隱私保護下的數據形式

Figure 1 Data format with privacy preservation

本文通過全面總結分析了ORH服務行程動態共享與隱私保護的相關理論和技術, 力圖探索如何在滿足在ORH服務多方隱私保護需求的前提下, 最大化地利用ORH服務的運力資源和城市道路資源。本文主要的研究工作如下。

1) 總結分析了行程開銷的安全計算方法, 具體包括歐式距離的安全計算、路網距離和行駛時長的安全計算。

2) 總結分析了行程共享的規劃問題求解方法, 具體從面向司機、乘客、ORH平臺三方面分析各類規劃目標和約束的求解方法。

3) 總結分析了隱私保護的行程共享方法, 具體包括隱私感知的行程預處理、單車單客模式和單車多客模式的行程安全共享。

本文結構組織如下: 第2節定義系統模型和服務模式; 第3節介紹構建隱私保護的ORH服務面臨的挑戰; 第4節總結分析行程開銷的安全計算方法; 第5節總結分析行程共享的規劃問題求解方法; 第6節總結分析隱私保護的行程共享方法; 第7節描述研究挑戰與未來展望; 最后, 總結全文。

2 系統模型與服務模式

在ORH服務中, 用戶主要包括乘客與司機, 他們通過ORH平臺建立聯系, 構成雙邊市場的供給與需求。如圖2所示, ORH服務的工作流程如下:

1) 請求提交: 乘客向ORH平臺發送包含其行程信息的網約請求, 包括行程起點/終點、上車/下車時間窗口、最大容忍的繞路開銷、乘客人數等。

2) 狀態更新: 車輛以一定頻率向ORH平臺更新其狀態, 包括當前位置、當前行程表、當前空閑座位等, 其中行程表記錄了車輛未來的目的地(上客/落客地點)的時序安排, 以及到達各目的地容許的時間窗口。

圖2 ORH系統模型

Figure 2 System model of an ORH service

3) 行程規劃: 基于乘客請求和車輛狀態, ORH平臺將請求分配給相應車輛并調整車輛行程表, 使車輛在滿足行程共享的約束條件下, 達成一定的優化目標, 并生成行程費用。

4) 匹配結果派發: ORH平臺將匹配結果發送給相關用戶進行確認, 乘客收到司機和車輛信息、預計上車/下車時間、支付費用等, 司機收到乘客信息、新的行程表、酬勞等。

5) 接送行程執行: 經雙方確認后, 司機按照新的行程表, 在容許的時間窗口內將乘客由起點位置送達終點位置。

6) 費用支付與服務評價: 行程執行結束后, 乘客向ORH平臺支付相應費用, 并對司機做出評價。

7) 報酬發放: ORH平臺扣除部分收益后, 向司機發放行程酬勞。

按照業務場景不同, 網約出行共享分為靜態共享和動態共享兩類:在行程靜態共享中, 所有網約請求提前預知, 出發前一次性完成行程規劃, 出發后車輛不能改變行程; 在行程動態共享中, 網約請求僅在發布時才能獲知, 出發后仍可以重新動態規劃行程, 隨時調整車輛行程。本質上, 靜態共享是動態共享在某一時刻收到所有網約請求的特殊情況。明顯地, 行程動態共享能夠合理利用車上的每一個座位, 最大化地利用有限的網約車供給和城市道路資源。本文關注的業務場景是城市動態場景下大規模網約出行動態共享, 即表5中的1、3、5、7項。

3 面臨的挑戰

采用加密技術實現隱私保護的行程動態共享仍面臨著以下挑戰:

1) 在城市動態場景下如何高效地計算密態行程開銷?任意位置間的行程開銷計算是ORH平臺進行行程共享規劃的基礎依據?？紤]到歐式距離密態計算的簡易性, 多數隱私保護的ORH服務方案[2-3,5-6]用歐式距離度量行程開銷, 但這忽視了車輛沿路網行駛這一關鍵特征。歐式距離無法準確地體現真實的行程開銷, 例如, 使用歐式距離代替路網距離進行KNN查詢存在約25%的錯誤率[4]。計算密態路網距離本質上是基于加密圖的最短路徑計算問題, 現有安全最短路徑算法[4,7-10]的效率難以支持大規模行程動態規劃需求。在城市動態路網下, 基于密態的乘客請求和車輛狀態實時計算行程開銷以支持大規模行程動態規劃是一個亟待解決的挑戰問題。

2) 在城市動態場景下如何實時地動態規劃密態行程?行程動態規劃是ORH平臺完成行程共享的核心環節, 除了單車單客的出行模式(這類問題求解相當于二分圖匹配問題, 在多項式時間內可求最優解), 其他行程共享模式的規劃問題已證明是NP難問題[11],這類問題求解相當于擴展旅行商問題, 即多項式復雜程度的非確定性問題。因此, 求解行程共享的規劃問題即使在明文下也是具有相當難度的, 例如, 滴滴拼車指出其每一次成功的行程共享平均需要額外的18.6萬次計算, 每日處理數據超過4875TB。目前, 多數隱私保護的ORH服務方案關注單車單客的行程動態匹配[2-6]或單車多客的行程靜態規劃問題的同態求解[12-16]。僅有Yu等[17]提出的PSRide首次實現了單車多客的行程動態規劃問題的同態求解。針對單車單客、單車多客、多車單客、多車多客4類出行動態共享模式, 高效地同態求解行程共享的動態規劃問題是一個極具難度的挑戰問題。

3) 在城市動態場景下如何安全地共享不同ORH服務的運力資源?目前, 網約車市場處于群雄逐鹿的態勢, 各公司紛紛推出各自的ORH服務, 例如, Uber, 滴滴出行、嘀嗒出行、首汽約車、曹操出行等。這些ORH服務擁有各自的用戶群體和運力資源, 且互不連通共享。在城市出行高峰時段, 乘客經常面臨著約車難的痛點。如果能夠整合不同ORH服務的運力資源實現跨服務域的行程共享, 這將進一步提升運力資源的利率和用戶體驗。然而, ORH服務提供商往往擔心商業隱私泄露和支付糾紛, 使得弱信任的ORH服務之間難以實現跨服務域的行程共享。構建去中心化多ORH服務間的行程安全共享體系, 多ORH服務跨域協作完成行程安全動態共享是一個前瞻性的挑戰問題。

4 行程開銷的安全計算

城市路網下起點和終點之間的行程開銷是指車輛由起點到終點所行駛的路網距離或時長, 每一次行程共享需要進行大量的行程開銷計算, 以判斷行程規劃方案的可行性和優劣程度。因此, 密態行程開銷的計算與比較開銷決定了后續行程動態規劃的效率。目前, 行程開銷的安全計算主要包括: 歐式距離的安全計算、路網距離或行駛時長的安全計算。

4.1 歐式距離的安全計算

歐式距離的安全計算多利用同態加密算法[18-19]、多方安全計算協議[20-21]實現, 其計算方法已相對成熟, 且效率較高。Pham等[3]采用類同態加密(SHE)算法[18]實現了多個歐式距離的并行同態計算; Liu等[22]采用部分同態加密(PHE)算法[19]和姚氏協議[20]實現了歐式距離的安全計算; Bringer等[23]采用擴展的茫然傳輸(OT)協議[24]實現了歐式距離的安全計算。上述算法最大的優勢是效率高, 支持大規模并發運算, 但以歐式距離衡量行程開銷忽視了車輛沿路網行駛這一關鍵特征, 使其無法準確地體現真實的行程開銷。事實上, 歐式距離不宜作為行程開銷的測量標準, Luo等[4]和Yu等[17,25]通過真實的城市路網驗證發現使用歐式距離代替路網距離進行KNN查詢存在約25%的錯誤率。

4.2 路網距離和行駛時長的安全計算

路網距離和行駛時長的安全計算本質上是圖論中最短路徑的安全計算, 路網距離和行駛時長在速度已知的前提下可相互轉換。最短路徑查詢作為圖結構加密[9]中的基本操作, 可以利用可搜索加密(SSE)技術[26-27]、茫然數據結構[10,28]、多方安全計算(SMC)技術[29]實現最短路徑安全計算。但這類方法的計算和通信開銷極高, 無法適用于城市網路場景, 例如, Carter等[30]提出基于姚氏協議[20]的最短路徑算法在100個節點的路網中需幾分鐘計算一次最短路徑; Liu等[31]提出的基于ORAM(Oblivious RAM)的最短路徑算法在1024個節點的路網中計算一次最短路徑需要GB級的通信量。

近年來, 針對大規模圖結構, 已提出了一些效率提升的最短路徑算法。Shen等[8]使用類同態加密算法和保序加密(ORE)算法[32]在加密的圖結構上實現了近似最短距離的安全查詢, 但ORE僅能提供有限的隱私保護; Meng等[7]使用類同態加密算法和距離預言機[33]實現了三種類型的近似最短距離安全查詢算法, 但算法的準確率和效率有待提高; Liu等[34]設計了一種新的圖結構對稱加密方案以支持高效的最短距離查詢, 該方案構造2HCL(2-hop cover labeling)[35], 以快速判斷兩頂點之間是否可達, 并求兩頂點之間的近似距離; Luo等[4]利用路網嵌入技術將路網嵌入到高維空間, 而后利用部分同態加密算法和姚氏協議在高維空間中計算近似的網路距離, 該方法需要在互不串通的雙服務器場景下使用, 且服務器端的計算和通信開銷較高; 針對文獻[4]的不足, Yu等[36]在路網嵌入的高維空間中利用一種改進的部分同態加密算法和密文雙重致盲方法實現了單一服務器的近似最短路網距離安全計算, 且極大地降低了服務器端的計算和通信開銷。上述方法實現了近似最短路網距離的安全計算, 其精度往往正比于計算和通信開銷, 即當對結果精度要求較高時, 會帶來更高的開銷。為此, 一些研究聚焦于精確路網距離的安全計算。Wang等[9]采用部分同態加密算法和姚氏協議實現了隱私保護的Dijkstra’ s最短路徑算法, 并利用斐波那契堆來提高計算效率, 但該方案需要為用戶部署可信代理協助計算; 在文獻[34]的基礎上, Zhang等[37]提出了一種基于部分同態加密[38]的圖加密方案, 以支持精準最短距離的安全計算。Yu等[25]提出了基于超立方體路網嵌入的最短路網距離精確計算方法, 該方法的性能明顯優于現有方法。然而, 上述方案也需要在互不串通的雙服務器場景下使用。

上述最短路網距離安全計算方法主要存在兩個局限性, 使其難以直接應用于城市動態路網下的密態行程動態規劃: 1) 上述方法僅支持靜態路網下的最短路網距離安全計算, 然而在動態路網下最短路網距離經常動態變化, 而這些方法難以支持路網的實時更新, 導致路網距離計算失效; 2) 上述方法在計算若干次最短路網距離時效率尚可, 但其開銷難以滿足行程動態規劃中大規模最短路網距離實時計算的需求。

在隱私保護的實時導航領域, 一些安全導航方案[38-39]支持動態路網距離的安全計算。然而, 導航對路網距離計算的效率需求要遠低于行程動態共享, 例如, Wu等[39]利用私密信息檢索(PIR)技術[29]和姚氏協議實現了一個隱私保護的實時導航協議, 在使用下一跳矩陣壓縮技術提升效率后, 每更新一跳仍需要1.5s計算時長和100KB通信開銷。過高的開銷導致這些方案難以適用于城市場景下的行程動態共享。針對行程動態共享對行程開銷計算的實時性需求, Yu等[17]提出了一種基于區域錨點的最短行駛時長估計算法, 并利用部分同態加密算法和姚氏協議實現了密態行駛時長的安全計算, 但當路網的路況變化較快時, 該方法需要更多的通信開銷保持算法準確性。

4.3 不足與啟示

基于加密數據的行程開銷計算能夠有效地避免起止點位置隱私泄露。利用類同態加密技術及其密文打包技術, 歐式距離的安全計算效率極高, 一般情況下, 通過若干次同態乘法和加法能夠同時計算出數千個歐式距離?；诩用軘祿穆肪W距離或行駛時長的計算更為復雜, 開銷更大, 其通常需要利用路網嵌入技術將二維空間中無法密態計算的問題在高維空間中密態求解, 但其效率能夠支持大規模的KNN密態實時查詢操作。歐式距離難以有效地體現真實的行程開銷。目前, 多數路網距離/行駛時長的安全計算方法僅面向靜態路網場景。而針對動態路網場景, 能夠支持行程動態共享的路網距離/行駛時長的安全計算方面的相關研究成果較少。針對動態路網距離/行駛時長的安全計算, 可將復雜的計算問題分解為可同態計算的簡單問題, 并通過構建安全的索引結構提升效率。

5 行程共享的規劃問題求解

行程共享的規劃問題求解是: 給定路網上的車輛集合和乘客請求集合, 將不同的乘客請求分配給不同的車輛并安排車輛行程表, 使車輛在滿足共享的約束條件下, 達成一定的優化目標。

5.1 面向司機的行程規劃

司機通常期望以最短的距離服務乘客請求, 或在最短的時間完成乘客請求, 因此, 面向司機的行程規劃常用的優化目標包括最小化車輛行駛總距離和最小化車輛最大完工時間。針對靜態場景下的行程共享問題, 一些研究[44,46-47]提出了最小化車輛行駛總距離的近似算法。目前, 研究更關注動態場景, 多數研究[41,45,48]采用插隊操作, 以最小化車輛行駛總距離為優化目標計算行程動態規劃問題的近似解。Ma等[41]提出一種基于枚舉的貪婪插隊算法, 針對新的乘客請求, 該算法不重新規劃車輛行程表, 而是將新請求貪婪地插入到行駛距離增加最少的車輛行程表, 該算法提高了求解的實時性, 但損失了求解的最優性。Huang等[48]設計了一種基于字典樹的數據結構(活動樹)記錄車輛的可行路徑和開銷, 乘客請求可以遞歸地插入到活動樹中, 而車輛每條可行的路徑對應著活動樹中由根節點到葉節點的一條路徑, 車輛選擇總距離最小的路徑行駛。Santi等[45]提出了一種基于批次處理的插隊算法, 該算法將乘客請求聚合成組, 而后按批次地盡可能多地將每個組內的乘客請求插入到當前車輛行程表。Tong等[49]提出了一種基于動態規劃的插隊算法,極大地降低了計算開銷, 并進一步提出了基于線性時間插隊操作的通用框架,大幅減少了冗余的最短路徑查詢。此外, 還有一些研究[50-51]關注最小化所有司機完成最后一個訂單的時間, 例如, Ascheuer等[50]提出的重新規劃框架和暫時遺忘框架, 前者當新請求到來時重新規劃車輛行程表, 而后者在積攢一定的請求后批次規劃行程表; Feuerstein等[51]也提出了一種類似于重新規劃框架的算法。有效地將插隊操作與時空索引結合, 是未來進一步提升行程規劃效率的可行方法。

5.2 面向乘客的行程規劃

乘客通常期望盡快到達終點, 此外, 還期望能夠與彼此間友好的乘客/司機共享行程。因此,面向乘客的行程規劃常用的優化目標包括最小化等待時間和最大化社會效用。Xu等[52]提出了最小化乘客最大等待時間的插隊算法, 通過動態規劃將查詢最優插隊位置的操作轉化為查詢特定區間最小值的操作, 并采用動態區間的查詢索引達到線性時間復雜度。針對最小化乘客平均等待時間的優化目標, Waisanen等[53]提出了一種基于先到先服務的策略以及基于旅行銷售商問題的行程規劃算法; Alonso等[54]提出了一種基于訂單打包的數據結構(RTV圖), RTV圖中若干位乘客間相互組合可枚舉構成所有可行路徑, 每條可行路徑與其候選車輛間連邊, 而后將行程共享問題轉化為整數規劃問題進行求近似解。Kameswaran等[55]調研發現社交關系在行程共享中的重要性, 例如, 乘客希望能夠與性格相似的人同行, 此外, 有些乘客能夠接受經過風景名勝所產生的繞路開銷?？紤]到乘客的出行體驗, 近年的研究[56,57]開始關注乘客之間、司機與乘客之間的社交關系, 通過定義社會效用模型來表示是否適宜共享行程、是否具有相同偏好等社交關系。Cheng等[56]在社會效用模型中同時考慮了乘客之間、乘客與司機之間的社交關系, 提出了以最大化社會效用為優化目標的行程靜態規劃問題, 并采用基于插隊操作的啟發式算法求解問題; Fu等[57]提出了基于社會效用的Top-行程靜態規劃問題, 即為每位乘客提供社會效用最大的條候選路徑, 由乘客根據自己的偏好進一步選擇。遺憾的是上述兩個研究僅適用于靜態場景。有效度量且高效計算社會效用, 并將其引入到行程動態規劃成為了新的挑戰。

5.3 面向ORH平臺的行程規劃

ORH平臺通常關注乘客請求成功完成數量以及平臺總盈利。因此, 面向ORH平臺的行程規劃常用的優化目標包括最大化平臺的乘客請求完成數和最大化平臺的總收入。由于受到時空約束和車輛數量的限制, ORH平臺無法保證完成全部乘客請求, 為此, 有研究[58-61]力圖在滿足約束條件下為盡可能多的乘客提供服務, 即最大化平臺的乘客請求完成數。Eleiner等[58]計算每輛車接送若干位乘客的路網距離矩陣, 然后利用匈牙利算法規劃行程, 確定車輛接送乘客的先后順序; Santos等[59]采用了基于插隊操作的局部搜索算法在最大化乘客請求完成數量的同時最小化乘客花費; Cici等[60]證明了最大化乘客請求完成數量的優化目標實際等價于最小化所需車輛數量; Vazifeh等[61]提出了一個基于交通網絡的算法求解最小化所需車輛數量這一等價問題。從商業利益的角度來看, 最大化平臺的總收入也是一個重要的優化目標[62-64]。在實際系統中, 平臺的總收入被定義為所有乘客支付的訂單價格總和減去平臺支付給所有司機的報酬。Asghari等[62]提出了一種基于分支定界的框架, 以最大化平臺的總收入為目標遞歸地嘗試為每個新的乘客請求找到最優司機; Zheng等[63]和Biswas等[64]都采用基于二分圖匹配的算法, 嘗試把可共享的若干乘客請求進行聚類, 而后通過枚舉的方法把聚類好的乘客請求分派給一輛車, 但這類算法并不適用于大規模路網場景。之前介紹的方案[49]提出的統一的優化目標既可以等價地轉化為最大化平臺的乘客請求完成數, 也能夠等價地轉化為最大化平臺的總收入。合理的行程定價, 以及公平、有效的用戶激勵機制是有待進一步研究的問題。

5.4 不足與啟示

現有研究往往僅針對司機、乘客或ORH平臺的單一角度進行行程規劃。然而, 作為一個雙邊市場, ORH平臺不但要考慮自身收益, 更需要同時兼顧乘客和司機的用戶體驗; 此外, 司機和乘客所處的動態情景也沒有充分考慮。應綜合考慮司機、乘客和ORH平臺三方利益制定自適應的行程動態規劃的優化目標; 行程動態規劃問題的求解方法能夠在密文下高效實現, 即基于密態的乘客請求和車輛狀態對行程動態規劃問題求近似解。

6 隱私保護的行程共享

如表1所示, 行程共享模式包括: 單車單客模式、單車多客模式、多車單客模式和多車多客模式?，F有行程安全共享方法主要關注不同模式下的用戶身份隱私、用戶位置隱私以及ORH平臺商業隱私。這些方法可以分非加密的共享方法和加密的共享方法。非加密的共享方法常用技術包括: 空間隱匿[2]、偽造虛假位置[65]、位置偏移與模糊[66]和差分隱私[67]等。這類方法力圖均衡隱私保護強度與服務質量, 具有較高的效率, 但它們僅提供了有限的隱私保護水平, 且泛化或噪聲機制會影響服務精度。相反地, 加密的共享方法能夠提供更高的隱私保護水平, 且不影響服務精度, 但它們計算開銷較大。這類方法常用技術包括: 私密信息檢索(PIR)[68]、多方安全計算(SMC)[20]、私密交集計算(PSI)[21]、類同態加密(SHE)[18]和部分同態加密(PHE)[19]等。針對不同共享模式, 現有的行程安全共享方法綜述如下。

6.1 隱私感知的行程預處理

行程預處理的主要思想是: 通過某些過濾條件刪除無法完成行程共享的乘客請求或車輛, 或通過聚類分組方法聚合乘客請求, 以達到快速的剪枝行程規劃問題候選解規模的目的。Coslovich等[40]提出了一種基于預先計算可行解的方法預處理乘客請求, 該方法采用兩階段的插入算法來提升效率, 其中第一階利用乘客請求的時間間隔來預先計算可行解, 第二階段再利用這些可行解對新請求進行匹配, 但該方法僅適用于中小規模的行程規劃問題。Ma等[41]提出了一種基于動態空間索引的方法過濾車輛集合, 該方法使用網格劃分網路為區塊, 為每區塊建立車輛的動態時空索引, 然后, 根據乘客起點和終點所在區塊索引雙向篩選鄰近區塊內能滿足時間約束車輛的作為候選集。Luo等[4]同樣采用的區塊索引的方式過濾車輛, 其每次選擇乘客起點所在區塊及其鄰近的8個區塊內的車輛作為候選集, 并利用乘客起點到車輛的歐式距離進一步剪枝候選集; Yu等[42]提出了動態條帶索引結構, 采用條帶劃分的方法對移動物體進行索引獲得了較高的可擴展性和查詢效率, 并實現了數據的分布式處理。Gidofalvi等[43]提出了一種基于請求聚類分組的方法預處理乘客請求, 該方法利用流數據分組技術把具有近似距離的起點/終點進行聚類分組, 并實現了并行化處理。類似地, Ta等[44]和Santi等[45]也采用了聚類分組的方法預處理乘客請求。上述行程預處理方法沒有考慮乘客/車輛的身份和位置隱私泄露問題, 很可能導致用戶隱私泄露, 例如, 在某些車輛稀少區塊內, 敵手易于實現對車輛的關聯與追蹤。行程預處理方法需要支持隱私的動態度量, 以實現剪枝力度與隱私保護強度之間的均衡。

6.2 單車單客模式的行程安全共享

PrivateRide[2]首次提出了ORH服務的隱私保護問題, 其利用輕量級的匿名證書技術保護用戶的身份隱私, 利用空間隱匿技術保護用戶的位置隱私, 利用盲簽名技術保護用戶的支付隱私, 但該方法存在服務精度低, 且僅為司機提供了有限的隱私保護強度。ORide[3]改進了PrivateRide以增強用戶隱私保護水平, 其采用SHE技術和密文打包技術計算乘客與司機之間的密態歐式距離, 并據此完成行程匹配, 但ORide會對乘客泄露司機的位置隱私。TRACE[5]采用四叉樹數據結構和輕量級空間隱匿技術保護用戶位置隱私和ORH平臺的地圖劃分隱私。CoRide[6]針對多ORH服務場景下的行程共享問題, 基于區塊鏈的車霧計算技術提出了一種行程協作共享方法, 該方法采用私密逼近測試[69]和Zerocash[70]保護用戶身份隱私、位置隱私和支付隱私, 以及ORH平臺的商業隱私。此外, 還有一些研究[71-72]基于區塊鏈構建了隱私保護的ORH服務, 但區塊鏈交易驗證的吞吐率往往會成為系統效率瓶頸?？紤]到密文計算效率, 上述隱私保護方案均采用歐式距離作為測量標準進行行程匹配, 但歐式距離無法體現真實的行程開銷, 這勢必導致行程匹配錯誤。Luo等[4]發現使用歐式距離代替路網距離進行單車單客行程匹配存在約25%的錯誤率, 為此, 他們首次提出了基于路網距離的單車單客動態行程安全匹配方法(pRide), 該方法首先利用路網嵌入技術將路網轉化為高維空間中的嵌入路網, 然后, 在嵌入路網下采用PHE計算密態路網距離, 采用姚氏協議比較密態路網距離, 最后, 選出具有最小行駛距離的車輛作為匹配結果。然而, pRide在服務器端的計算和通信開銷較大, 難以支持大規模的并發乘客請求。Yu等[36]提出了一個輕量級的隱私保護方法, 即lpRide, 該方法使用翻轉加解密操作的PHE和嵌入路網技術實現了密態路網距離的高效計算, 使用盲密文分布機制實現了密態路網距離的高效比較, lpRide大幅降低了服務器端的開銷, 支持大規模的并發乘客請求。鑒于現有路網距離安全計算方法無法滿足行程匹配對路網距離計算的實時性需求, 目前基于路網距離的單車單客密態行程匹配方法并不多?，F有的pRide和lpRide也只能利用近似的路網距離進行行程匹配, 基于精確路網距離的行程安全匹配方法亟待深入研究。

6.3 單車多客模式的行程安全共享

PrivatePool[12]使用PHE技術和PSI技術設計了基于逼近測試行程安全規劃方法和基于軌跡重合計算的行程安全規劃方法, 前者通過私密計算乘客行程起點/終點與車輛軌跡之間的最小歐氏距離進行行程規劃, 后者通過私密匹配乘客行程與車輛軌跡之間的最大重疊進行行程規劃。在PrivatePool的基礎上, Pagnin等[73]提出了具有高效率的O-PrivatePool協議, 并進一步提出了考慮時間約束的TOPPool協議。PRIS[13]使用PHE技術面向加密的乘客和車輛的時空行程, 以最大化行駛時長節約量為約束優化目標進行行程安全規劃, 其中, 行駛時長節約量等于乘客行程與車輛行程的總駛時長與該共享行程時長的差值。SRide[14]采用SHE和SMC技術保護乘客和司機的位置隱私, 該方法首先利用時空網格過濾候選司機, 然后, 使用改進的Priv-2SP-SP協議[74]計算乘客行程與司機行程的相似性, 并以最小化車輛行駛總距離為優化目標進行行程規劃。Sherif等[15]將乘客和司機加密后的行程轉換為詞向量, 通過比較乘客與司機之間的時間詞向量相似性和空間詞向量相似性, 以最大化乘客請求完成數為優化目標進行行程規劃。FICA[16]采用基于區塊鏈的車霧計算技術設計了一個保護乘客和車輛位置隱私的行程共享系統, 該系統使用分布式計算單元RSU構建記錄交易的私有鏈, 由RSU負責上傳處理乘客請求, 并利用基于時空標簽的位置私密逼近測試進行行程規劃。此外, 還有一些研究[67,75-76]基于差分隱私技術進行單車多客的行程共享, 其主要思想是通過對原有位置數據添加噪聲保證司機與乘客的時空敏感信息不被泄露, 然后基于添加噪聲后的數據進行行程規劃, 但噪聲的引入會影響行程規劃的精準度。Yu等[77]提出了一種基于群組中心點的車輛選擇算法, 支持在密文下對群組行程共享問題進行同態求解, 并證明了密態歐式距離能夠在群組行程共享中衡量行駛距離。上述單車多客模式的行程安全共享方法主要存在兩個局限性: 1) 這些方法本質上是行程靜態安全共享方法, 即司機和乘客的行程提前預知, 且開始行程共享后, 直至本次共享行程完成前不能更改行程, 顯然這些方法無法適用于城市動態場景; 2)這些方法的行程共享僅能發生在車輛提前預設的有限位置附近, 乘客上下車位置靈活性較差。上述局限性與實際應用中乘客和司機的意愿相違背, 因為司機期望接送更多的乘客, 而乘客期望自定義上下車地點。

針對上述不足, Yu等[17]首次提出了一個隱私保護行程安全動態共享方法—PSRide, 其以最短路網行駛時間為依據, 以最小化車輛繞道時長為優化目標, 在密文下動態規劃行程, 即車輛在行程開始后, 若有空座位仍可以參加新一輪的行程規劃, 當匹配成功時, 車輛動態調整行程表為新乘客服務。Yu等[17]提出在密文下動態規劃行程需要考慮計算和通信開銷的問題, 規劃方法不宜涉及過于復雜的運算, 因此, PSRide利用動態插隊算法以最小化附加行程開銷為優化目標進行密態行程的動態規劃。

圖3 請求插入示例

Figure 3 An example of request insertion

。

該行程動態規劃問題的求解過程僅涉及到加減法操作和比較操作, 因此, 基于前面介紹密態行駛時間的同態計算方法和密文安全比較方法, 采用部分同態加密算法和姚氏協議能夠在密文下高效地求解上述規劃問題。

目前, 城市動態場景下單車多客模式的行程安全動態共享方法較少, 尤其是以路網行駛開銷為依據的行程安全動態共享方法亟待深入研究。

6.4 不足與啟示

隱私感知的行程預處理能夠在保證預期隱私保護強度的前提下最優化地剪枝用戶請求或候選車輛。一般來說, 剪枝力度的增大會有效地降低開銷, 但也可能在一定程度上會減弱隱私保護強度。因此, 可以根據敵手背景知識、隱私保護需求計算預處理對應的條件信息熵, 確定最優的剪枝策略, 進而降低開銷。

行程安全共享能夠有效地避免行程線路和時間表等隱私信息泄露。行程安全共享通常采用歐式距離、路網距離或行駛時間作為行程規劃的基礎依據。單車單客模式行程安全共享可以計算密態歐式距離進行行程規劃, 其效率很高, 但會導致規劃誤差。在行程需處理的支持下, 單車單客模式行程安全共享應計算密態路網距離或行駛時間進行行程規劃。目前密態路網距離或行駛時間的計算效率能夠支持大規模實時的單車單客模式的行程安全共享。單車多客模式的行程安全共享無法采用歐式距離進行行程規劃, 因其會導致行程規劃錯誤, 即無法按時上客/落客。原則上, 單車多客模式的行程安全共享應采用路網距離或行駛時間作為動態規劃的依據, 以避免規劃錯誤。相對于單車單客模式, 單車多客模式的行程安全共享每一次行程規劃需要更多的行程開銷計算, 以及額外的時間表編排, 這對密文計算和通信效率提出了更高的要求。目前僅有少數研究[17]以行駛時間為依據才能夠支持單車多客行程安全動態共享。

多數現有研究本質上是單車單客或單車多客模式的行程安全靜態共享方法。一方面, 行程安全動態共享方面的研究成果較少; 另一方面, 多車單客、多車多客模式的行程安全共享方面尚待進一步研究。應重點關注單車多客、多車單客、多車多客模式的行程安全動態共享方法, 面向密態的乘客請求和車輛狀態, 構建多元化的優化目標, 在密文下高效地完成行程動態規劃問題的求近似解。

7 研究挑戰與未來展望

7.1 研究挑戰

城市動態路網下大規模最小行程開銷的安全計算問題: 針對現有在歐式空間或靜態路網中密態行程開銷計算方法難以適用于交通狀況復雜的動態路網的困境, 在城市動態路網場景下, 如何高效地同態計算與比較密態行程開銷, 以支持大規模密態最小行程開銷的實時度量, 為后續密態行程動態規劃提供決策依據, 這是要解決的基礎性挑戰問題。

ORH服務域內的密態行程動態共享與安全保障問題: 針對城市動態路網下行程動態共享數據量大、動態性強、目標多樣、模式靈活等特點, 在實時計算最小密態行程開銷、社會效用和情景的基礎上, 如何在單一ORH服務域內高效地完成多模式、多目標的密態行程動態規劃, 并保護用戶的身份隱私、位置隱私和支付隱私, 保障用戶的人身安全[78-79], 這是要解決的核心挑戰問題。

ORH服務域間的密態行程協作共享與可控匿名支付問題: 針對多弱信任的ORH服務合作開展行程共享所帶來的用戶交叉認證需求和隱私跨服務域泄露風險, 如何去中心化地高效完成多ORH服務間的密態行程安全共享和流程合規監管, 以實現跨服務域的用戶可控匿名認證、密態行程協作共享、費用可控匿名支付, 這是要解決的探索性挑戰問題。

7.2 研究展望

7.2.1 城市動態路網下高效的密態行程開銷的安全計算與比較

在城市動態路網場景下, 研究高效的密態行程開銷的安全計算與比較方法, 以實現任意位置間的最短時空距離的實時安全度量, 為密態行程動態規劃提供決策依據, 針對大規模動態路網下密態行程開銷計算與比較存在的復雜度高、開銷大等問題, 研究動態路網的高維空間嵌入機制, 以及動態嵌入路網中密態路網距離的同態計算方法, 研究動態路網下密態行駛時間的同態計算方法, 實現輕量、高效的密態行程開銷的同態計算與比較, 使其在時空間維度上密態可度量; 針對密態行程開銷同態計算的精準性和高效性兼顧的需求, 研究密態行程開銷計算的準確率和效率之間量化機制, 為設備能耗、通信開銷、計算效率、結果精度的優化均衡提供理論指導。

7.2.2 多方隱私保護的大規模密態行程動態規劃與安全保障

在單一ORH服務場景下, 研究乘客、司機、ORH平臺三方隱私保護的大規模密態行程動態共享方法, 以實現面向多種共享模式的多目標優化的行程安全動態規劃, 并保護用戶身份、位置和支付隱私, 保障用戶人身安全。

1) 支持隱私動態度量的行程預處理方法

針對隱私需求的主觀敏感度個性化、場景差異化等特點, 在主客體隱私敏感度和應用場景智能感知的基礎上, 研究融合主觀認知和實時情景的隱私動態度量理論體系, 形成隱私風險、保護強度、泄露益損比、效能平衡的一致性量化方法和評價模型; 研究支持隱私動態度量的行程預處理方法, 包括基于動態空間安全索引的預處理方法, 基于行程茫然聚類分組的預處理方法, 在避免用戶隱私泄露的前提下實現隱私可量、可控的行程快速篩選過濾, 以達到快速、安全地剪枝行程規劃問題候選解規模的目的。

2) 融合社會效用與情景的密態行程多目標動態規劃方法

針對城市動態場景下行程共享數據量大、動態性強、目標多樣、模式靈活等特點, 研究多維度的行程動態規劃的優化目標體系, 涉及面向司機的最小化行駛開銷、面向乘客的最小化平均等待時間及最大化社會效用、面向ORH平臺的最大化請求完成數及最大化總收入, 實現針對應用場景的多優化目標自適應融合; 研究社會效用與動態情景的相似度安全計算方法, 涉及用戶社交關系、興趣偏好、地點流行度、交通流量等因素的量化與同態計算, 以提高行程共享的用戶體驗和人文關懷; 研究支持高效同態計算的多模式密態行程動態規劃方法, 面向單車單客、單車多客、多車單客、多車多客模式安全地動態規劃行程, 具體包括可同態求解的動態規劃插隊算法、基于安全索引的行程加密搜索與動態剪枝機制、支持同態計算的行程規劃啟發式算法, 在滿足社會效用、實時情景、時間窗口、繞路開銷等約束條件下, 達成多優化目標的行程規劃問題求近似解, 并保護用戶身份隱私與位置隱私。

7.2.3 跨服務域的去中心化密態行程協作共享

在多個ORH服務共存的場景下, 研究跨ORH服務域的用戶可控匿名認證機制[80-81]、密態行程協作共享協議、費用可控匿名支付機制[70,82-83], 實現弱信任的ORH服務間的行程跨域安全共享, 并保護各ORH服務的商業隱私、用戶隱私和支付隱私。

1) 跨服務域的用戶可控匿名認證機制

針對多ORH服務用戶交叉認證存在的身份管理機制異構性、身份隱私跨域泄露風險、重復認證的額外開銷等問題, 研究基于區塊鏈的用戶身份可控匿名認證機制, 在ORH服務域內構建基于匿名證書的用戶身份匿名認證體系, 在ORH服務域間構建基于區塊鏈和零知識證明的用戶身份可控匿名認證體系, 在保證認證匿名性和可追蹤性的前提下實現輕量級分布式的用戶身份認證, 防止用戶身份隱私泄露和匿名濫用。

2) 跨服務域的密態行程協作共享協議

針對ORH服務域間行程共享存在的約束優化目標異構、隱私跨域泄露等問題, 研究ORH服務域間的密態行程協作規劃協議, 自適應地轉換融合不同ORH平臺的約束條件和優化目標, 在避免ORH平臺的商業隱私泄露的前提下協作完成跨服務域的密態行程安全動態規劃; 研究基于智能合約的跨域共享行程的自動化執行與監管機制, 探索面向行程跨域共享的智能合約形式化創建方法, 通過在區塊鏈上構建多樣性的智能合約, 自動化監督行程跨域共享執行的合規性和真實性。

3) 跨服務域的行程費用的可控匿名支付機制

針對跨ORH服務域支付的“前臺匿名, 后臺實名”的匿名性和可控性需求, 研究基于區塊鏈的高效可控匿名支付機制, 用戶支付時隱藏支付交易的來源、去向和金額, 監管部門執法時可追蹤支付流程, 在保證高支付吞吐率的前提下實現支付的不可雙花性、假名性、不可偽造性、可傳遞性、拆分聚合性和不可鏈接性(用戶地址不可鏈接、多個支付不可鏈接、支付輸入輸出不可鏈接); 研究多方合作的穿透式支付監管策略, 將支付監管與用戶身份管理、支付流程相結合, 實現對非法操作涉及的支付交易和參與方身份的追蹤取證。

7.2.4 ORH服務的法律法規合規保證

隨著《網絡安全法》、《數據安全法》和《個人信息保護法》相繼出臺, 對服務提供商收集、處理數據應當盡到的合規要求也越來越明晰, 如果服務提供商在此過程中無法盡合規審查的義務, 可能會觸發一系列相關法律法規的規定, 進而被追究刑事、民事和行政責任。數據收集需明確合法、正當、必要原則, 并明確收集的目的。即使收集方出于改善服務、數據分析等理由, 也應當謹慎處理收集信息的范圍, 尤其是個人敏感信息。國家網信辦、工業和信息化部、公安部、國家市場監督管理總局聯合制定的《常見類型移動互聯網應用程序必要個人信息范圍規定》, 對ORH服務提供商收集用戶個人信息范圍進行了明, 具體包括: 1) 注冊用戶移動電話號碼; 2) 乘車人出發地、到達地、位置信息、行蹤軌跡; 3) 支付時間、支付金額、支付渠道等支付信息。雖然上述最少必要原則已盡可能地減少了ORH服務中隱私泄露風險, 但已有研究[1-4]揭示: 一方面, ORH服務可能存在潛在安全風險, 導致用戶隱私泄露; 另一方面, ORH服務提供商結合背景知識和歷史數據仍能夠從最少必要收集的信息中推理出大量的敏感信息, 例如, 敏感地點、用戶隱私等。為有效應對上述隱私泄露隱患, 應運用隱私保護技術對最少必要收集的信息進行進一步處理。具體地, 研究采用可控匿名認證技術[80-81]避免注冊用戶移動電話號碼的泄露; 研究采用同態加密[18-19]、多方安全計算[20-21]、差分隱私[67]、匿名化[65-66]等隱私計算技術避免乘車人出發地、到達地、位置信息、行蹤軌跡等行程信息的泄露; 研究采用可控匿名支付技術[70,82-83]避免支付時間、支付金額、支付渠道等支付信息的泄露。

8 結論

目前全球對ORH服務中用戶隱私泄露的監管已愈發嚴格, 在保護用戶隱私的前提下最大化地利用有限的運力資源已成為前沿的熱點和難點問題?；诿艽a學的隱私保護技術提供了強隱私保護和高數據可用性, 已廣泛地應用在ORH服務中。首先, 本文介紹了隱私保護的ORH服務面臨的主要挑戰; 然后, 分析了密態行程開銷的安全計算、行程共享的規劃問題求解方法和隱私保護的行程共享方法, 總結不足和啟示; 最后, 展望了隱私保護的ORH服務的未來研究方向。本文旨在保護多方隱私的前提下, 提高ORH平臺服務質量, 使得網約出行更加智慧、更加安全。

[1] Zhao Q C, Zuo C S, Pellegrino G, et al. Geo-Locating Drivers: A Study of Sensitive Data Leakage in Ride-Hailing Services[C]., 2019: 1-15.

[2] Pham A, Dacosta I, Jacot B, et al. PrivateRide: A privacy-enhanced ride-hailing service[J]., 2017, 2017(2): 38-56.

[3] Pham A, Dacosta I, Endignoux G, et al. ORide: A Privacy-Preserving yet Accountable Ride-Hailing Service[C]., 2017: 1235-1252.

[4] Luo Y C, Jia X H, Fu S J, et al. PRide: Privacy-Preserving Ride Matching over Road Networks for Online Ride-Hailing Service[J]., 2019, 14(7): 1791-1802.

[5] Wang F W, Zhu H, Liu X M, et al. Efficient and Privacy-Preserving Dynamic Spatial Query Scheme for Ride-Hailing Services[J]., 2018, 67(11): 11084-11097.

[6] Li M, Zhu L, Lin X. CoRide: A privacy-preserving collaborative- ride hailing service using blockchain-assisted vehicular fog computing[C]., 2019: 408-422.

[7] Meng X, Kamara S, Nissim K, et al. GRECS: Graph encrytion for approximate shortest distance queries[C].. ACM, 2015: 504-517.

[8] Shen M, Ma B L, Zhu L H, et al. Cloud-Based Approximate Constrained Shortest Distance Queries over Encrypted Graphs with Privacy Protection[J]., 2018, 13(4): 940-953.

[9] Wang Q, Ren K, Du M, et al. SecGDB: Graph encryption for exact shortest distance queries with efficient updates[C]., 2017: 79-97.

[10] Keller M, Scholl P. Efficient, oblivious data structures for MPC[C]., 2014: 506-525.

[11] Xu Y, Tong Y X, Li W. Recent Progress in Large-Scale Ridesharing Algorithms[J]., 2020, 57(1): 32-52. (徐毅, 童詠昕, 李未. 大規模拼車算法研究進展[J]., 2020, 57(1): 32-52.)

[12] Hallgren P, Orlandi C, Sabelfeld A. PrivatePool: Privacy-Preserving Ridesharing[C]., 2017: 276-291.

[13] He Y Y, Ni J B, Wang X Y, et al. Privacy-Preserving Partner Selection for Ride-Sharing Services[J]., 2018, 67(7): 5994-6005.

[14] A?vodji U, Huguenin K, Huguet M, et al. SRide: A privacy-preserving ridesharing system[C]., 2018: 40-50.

[15] Sherif A B T, Rabieh K, Mahmoud M M E A, et al. Privacy-Preserving Ride Sharing Scheme for Autonomous Vehicles in Big Data Era[J]., 2017, 4(2): 611-618.

[16] Li M, Zhu L H, Lin X D. Efficient and Privacy-Preserving Carpooling Using Blockchain-Assisted Vehicular Fog Computing[J]., 2019, 6(3): 4573-4584.

[17] Yu H N, Jia X H, Zhang H L, et al. PSRide: Privacy-Preserving Shared Ride Matching for Online Ride Hailing Systems[J]., 2021, 18(3): 1425-1440.

[18] Fan J F, Vercauteren F. Somewhat Practical Fully Homomorphic Encryption[J]., 2012, 2012: 144.

[19] Paillier P. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[C]., 1999: 223-238.

[20] Huang Y, Evans D, Katz J, et al. Faster Secure Two-Party Computation Using Garbled Circuits[C]., 2011: 35.

[21] Freedman M J, Nissim K, Pinkas B. Efficient Private Matching and Set Intersection[C]., 2004: 1-19.

[22] Liu A, Zhengy K, Liz L, et al. Efficient Secure Similarity Computation on Encrypted Trajectory Data[C]., 2015: 66-77.

[23] Bringer J, Chabanne H, Favre M, et al. GSHADE: Faster Privacy-Preserving Distance Computation and Biometric Identification[C]., 2014: 187-198.

[24] Ishai Y, Kilian J, Nissim K, et al. Extending Oblivious Transfers Efficiently[C]., 2003: 145-161.

[25] Yu H N, Jia X H, Zhang H L, et al. Efficient and Privacy-Preserving Ride Matching Using Exact Road Distance in Online Ride Hailing Services[J]., 2022, 15(4): 1841-1854.

[26] Song D X, Wagner D, Perrig A. Practical Techniques for Searches on Encrypted Data[C]., 2002: 44-55.

[27] Hahn F, Kerschbaum F. Searchable Encryption with Secure and Efficient Updates[C]., 2014: 310-320.

[28] Blanton M, Steele A, Alisagari M. Data-Oblivious Graph Algorithms for Secure Computation and Outsourcing[C].,, 2013: 207-218.

[29] Mouratidis K, Yiu M L. Shortest Path Computation with no Information Leakage[J]., 2012, 5(8): 692-703.

[30] Carter H, Mood B, Traynor P, et al. Secure Outsourced Garbled Circuit Evaluation for Mobile Devices[J]., 2016, 24(2): 137-180.

[31] Liu C, Wang X S, Nayak K, et al. ObliVM: A Programming Framework for Secure Computation[C]., 2015: 359-376.

[32] Lewi K, Wu D J. Order-Revealing Encryption: New Constructions, Applications, and Lower Bounds[C]., 2016: 1167-1178.

[33] Das Sarma A, Gollapudi S, Najork M, et al. A Sketch-Based Distance Oracle for Web-Scale Graphs[C]., 2010: 401-410.

[34] Liu C, Zhu L H, He X J, et al. Enabling Privacy-Preserving Shortest Distance Queries on Encrypted Graph Data[J]., 2021, 18(1): 192-204.

[35] Akiba T, Iwata Y, Yoshida Y. Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling[C]., 2013: 349-360.

[36] Yu H N, Shu J G, Jia X, et al. LpRide: Lightweight and Privacy-Preserving Ride Matching over Road Networks in Online Ride Hailing Systems[J]., 2019, 68: 10418-10428.

[37] Zhang C, Zhu L H, Xu C, et al. PGAS: Privacy-Preserving Graph Encryption for Accurate Constrained Shortest Distance Queries[J]., 2020, 506: 325-345.

[38] Liu X M, Choo K K R, Deng R H, et al. Efficient and Privacy-Preserving Outsourced Calculation of Rational Numbers[J]., 2018, 15(1): 27-39.

[39] Wu D J, Zimmerman J, Planul J, et al. Privacy-Preserving Shortest Path Computation[EB/OL]. 2016: arXiv: 1601.02281. https://arxiv. org/abs/1601.02281.pdf.

[40] Coslovich L, Pesenti R, Ukovich W. A Two-Phase Insertion Technique of Unexpected Customers for a Dynamic Dial-a-Ride Problem[J]., 2006, 175(3): 1605-1615.

[41] Ma S, Zheng Y, Wolfson O. Real-Time City-Scale Taxi Ridesharing[J]., 2015, 27(7): 1782-1795.

[42] Yu Z Q, Liu Y, Yu X H, et al. Scalable Distributed Processing of K Nearest Neighbor Queries over Moving Objects[J]., 2015, 27(5): 1383-1396.

[43] Gidofalvi G, Pedersen T B, Risch T, et al. Highly Scalable Trip Grouping for Large-Scale Collective Transportation Systems[C].:, 2008: 678-689.

[44] Ta N, Li G L, Zhao T Y, et al. An Efficient Ride-Sharing Framework for Maximizing Shared Route[J]., 2018, 30(2): 219-233.

[45] Santi P, Resta G, Szell M, et al. Quantifying the Benefits of Vehicle Pooling with Shareability Networks[J]., 2014, 111(37): 13290-13294.

[46] Gupta A, Hajiaghayi M, Nagarajan V, et al. Dial a Ride from-Forest[J]., 6(2)Article No. 41,

[47] Bei X, Zhang S. Algorithms for trip-vehicle assignment in ride- sharing[C]., 2018:1-7.

[48] Huang Y, Bastani F, Jin R M, et al. Large Scale Realtime Ridesharing with Service Guarantee on Road Networks[J]., 2014, 7(14): 2017-2028.

[49] Tong Y, Zeng Y, Zhou Z, et al. A unified approach to route planning for shared mobility[J]., 2018, 11(11): 1633-1646.

[50] Ascheuer N, Krumke S O, Rambau J. Online Dial-a-Ride Problems: Minimizing the Completion Time[C]., 2000: 639-650.

[51] Feuerstein E, Stougie L. On-Line Single-Server Dial-a-Ride Problems[J]., 2001, 268(1): 91-105.

[52] Xu Y, Tong Y X, Shi Y X, et al. An Efficient Insertion Operator in Dynamic Ridesharing Services[C]., 2019: 1022-1033.

[53] Waisanen H A, Shah D, Dahleh M A. A Dynamic Pickup and Delivery Problem in Mobile Networks under Information Constraints[J]., 2008, 53(6): 1419-1433.

[54] Alonso-Mora J, Samaranayake S, Wallar A, et al. On-Demand High-Capacity Ride-Sharing via Dynamic Trip-Vehicle Assignment[J]., 2017, 114(3): 462-467.

[55] Kameswaran V, Cameron L, Dillahunt T R. Support for Social and Cultural Capital Development in Real-Time Ridesharing Services[C]., 2018: 1-12.

[56] Cheng P, Xin H, Chen L. Utility-Aware Ridesharing on Road Networks[C]., 2017: 1197-1210.

[57] Fu X, Huang J, Lu H, et al. Top-k taxi recommendation in realtime social-aware ridesharing services[C]., 2017: 221-241.

[58] Kleiner A, Nebel B, Ziparo V A. A Mechanism for Dynamic Ride Sharing Based on Parallel Auctions[C]., 2011: 266-272.

[59] Santos D O, Xavier E C. Dynamic Taxi and Ridesharing: A Framework and Heuristics for the Optimization Problem[C]., 2013: 2885-2891.

[60] Cici B, Markopoulou A, Laoutaris N. Designing an On-Line Ride-Sharing System[C]., 2015: 1-4.

[61] Vazifeh M M, Santi P, Resta G, et al. Addressing the Minimum Fleet Problem in On-Demand Urban Mobility[J]., 2018, 557(7706): 534-538.

[62] Asghari M, Deng D X, Shahabi C, et al. Price-Aware Real-Time Ride-Sharing at Scale: An Auction-Based Approach[C]., 2016: 1-10.

[63] Zheng L, Chen L, Ye J. Order dispatch in price-aware ridesharing [J]., 2018, 11(8): 853-865.

[64] Biswas A, Gopalakrishnan R, Tulabandhula T, et al. Profit optimization in commercial ridesharing[C]., 2017: 1481-1483.

[65] Niu B, Li Q H, Zhu X Y, et al. Achieving K-Anonymity in Privacy-Aware Location-Based Services[C]., 2014: 754-762.

[66] Palanisamy B, Liu L. Attack-Resilient Mix-Zones over Road Networks: Architecture and Algorithms[J]., 2015, 14(3): 495-508.

[67] Tong W, Hua J Y, Zhong S. A Jointly Differentially Private Scheduling Protocol for Ridesharing Services[J]., 2017, 12(10): 2444-2456.

[68] Chor B, Goldreich O, Kushilevitz E, et al. Private Information Retrieval[C]., 2002: 41-50.

[69] Zheng Y, Li M, Lou W J, et al. Location Based Handshake and Private Proximity Test with Location Tags[J]., 2017, 14(4): 406-419.

[70] Ben Sasson E, Chiesa A, Garman C, et al. Zerocash: Decentralized Anonymous Payments from Bitcoin[C]., 2014: 459-474.

[71] Zhang H J, Deng E D, Zhu H J, et al. Smart Contract for Secure Billing in Ride-Hailing Service via Blockchain[J]., 2019, 12(5): 1346-1357.

[72] Shivers R, Rahman M A, Shahriar H. Toward a Secure and Decentralized Blockchain-Based Ride-Hailing Platform for Autonomous Vehicles[EB/OL]. 2019: arXiv: 1910.00715. https:// arxiv.org/abs/1910.00715.pdf.

[73] Pagnin E, Gunnarsson G, Talebi P, et al. Toppool: Time- aware optimized privacy-preserving ridesharing[J]., 2019, 2019(4):93-111.

[74] A?vodji U M, Gambs S, Huguet M J, et al. Meeting Points in Ridesharing: A Privacy-Preserving Approach[J].:, 2016, 72: 239-253.

[75] Xu Y, Wei S Y, Wang Y S. Privacy Preserving Online Matching on Ridesharing Platforms[J]., 2020, 406: 371-377.

[76] Prorok A, Kumar V. Privacy-Preserving Vehicle Assignment for Mobility-on-Demand Systems[C]., 2017: 1869-1876.

[77] Yu H N, Zhang H L, Yu X Z, et al. PGRide: Privacy-Preserving Group Ridesharing Matching in Online Ride Hailing Services[J]., 2021, 8(7): 5722-5735.

[78] Yu H N, Zhang H L, Jia X H, et al. PSafety: Privacy-Preserving Safety Monitoring in Online Ride Hailing Services[J]., 2023, 20(1): 209-224.

[79] Chaudhry B, Yasar A U H, El-Amine S, et al. Passenger Safety in Ride-Sharing Services[J]., 2018, 130: 1044-1050.

[80] Wang D, Li W T, Wang P. Crytanalysis of Three Anonymous Authentication Schemes for Multi-Server Environment[J]., 2018, 29(7): 1937-1952. (汪定, 李文婷, 王平. 對三個多服務器環境下匿名認證協議的分析[J]., 2018, 29(7): 1937-1952.)

[81] Wang Z, Fan J, Cheng L, et al. Supervised Anonymous Authentication Scheme[J]., 2019, 30(6): 1705-1720. (王震, 范佳, 成林, 等. 可監管匿名認證方案[J]., 2019, 30(6): 1705-1720.)

[82] Miers I, Garman C, Green M, et al. Zerocoin: Anonymous Distributed E-Cash from Bitcoin[C]., 2013: 397-411.

[83] Kumar A, Fischer C, Tople S, et al. A traceability analysis of monero’s blockchain[C]., 2017: 153-173.

A Survey on Privacy-Preserving Ridesharing for Online Ride Hailing Services

YU Haining1, ZHANG Hongli1, YU Xiangzhan1, QU Jiaxing2

1School of Cyberspace Science, Harbin Institute of Technology, Harbin 150001, China2Heilongjiang Province Cyberspace Research Center, Harbin 150001, China

For efficient utilization of transportation resources, Online Ride Hailing (ORH) services enable riders to hail available vehicles by matching vehicle supplies and rider requests. Along with the advantage of ORH services raises serious privacy concerns. Thus, many studies focus on privacy-preserving ORH services by using some well-established cryptographic primitives. Firstly, we introduce main challenges for privacy-enhanced ORH services under in dynamic city scenarios, including encrypted travel cost computation, encrypted trips dynamic planning and secure ridesharing between different ORH services; then, we review secure travel cost computation about Euclidean distance, road distance and travel time. Euclidean distance secure computation is very efficient but not accurate. Most road distance and travel time secure computation methods are designed for static road networks, but it is desirable to have more methods for dynamic city road networks. We analyze ridesharing dynamic scheduling oriented from riders, drivers and ORH platforms. Existing works solve ridesharing dynamic scheduling with single optimal objective from riders, drivers or ORH platforms. Actually, comprehensive multiple objectives of riders, drivers and ORH platforms should be considered, such as income of ORH platforms, user experience of riders and drivers. We further summarize privacy-aware trip preprocessing and privacy-preserving ridesharing over encrypted trips, including single driver-single rider mode and single driver-multiple riders mode, and then further point out disadvantages and inspiration of existing studies. However, it is desirable to have secure ridesharing of multiple drivers - single rider dynamic mode and multiple drivers - multiple riders dynamic mode. Finally, we summary further works in privacy-preserving ORH services, including secure travel cost computation and comparison over encrypted trips, multiparty privacy-preserving dynamic ridesharing and safety guarantee over large scale encrypted trips, decentralized secure ridesharing cross ORH services, legal and regulatory compliance guarantee. The paper aims to improve the quality of an ORH service and enhance cooperation cross ORH services, while protecting the privacy of all parties. It can make ORH services more intelligent and more secure.

location privacy; secure multi-party computation; ride hailing service; dynamic ridesharing

TP309.2

10.19363/J.cnki.cn10-1380/tn.2024.01.01

于海寧, 博士, 副研究員, Email: yuhaining@hit.edu.cn。

本課題得到國家自然科學基金項目(No. 62172123, No. 61732022)和黑龍江省自然科學基金優秀青年項目(No. YQ2021F007)資助。

2022-04-02;

2022-05-16;

2023-09-26

于海寧 于2013年在哈爾濱工業大學信息安全專業獲得博士學位?，F任哈爾濱工業大學網絡空間安全學院副研究員。研究領域為數據安全、隱私計算等。Email: yuhaining@hit.edu.cn

張宏莉 于1999年在哈爾濱工業大學計算機系統結構專業獲得博士學位。哈爾濱工業大學網絡空間安全學院教授。研究領域為網絡與信息安全、網絡測量與建模、網絡計算、并行處理等。Email: zhanghongli@hit.edu.cn

余翔湛 于2005年在哈爾濱工業大學計算機系統結構專業獲得博士學位。哈爾濱工業大學網絡空間安全學院教授。研究領域為信息安全、網絡流量分析等。Email: yxz@hit.edu.cn

曲家興 于2019年在哈爾濱工程大學計算機應用技術專業獲得博士學位。黑龍江省網絡空間研究中心教授級高級工程師。研究領域為網絡安全、網絡輿情分析等。Email: smilingqu@126.com