利用分散式正規表式比對保護URL檢查之隱私

Abstract

近年來，URL檢查由於安全瀏覽服務的廣泛使用，因此其隱私問題變得愈發重要。有鑑於此，我們提出了一個保護隱私的URL檢查系統，其特色為將使用者的URL分割成若干份秘密以保護使用者的隱私。我們的系統利用多個計算節點對不同份秘密進行正則表達式匹配，因此只要至少有一個節點被視為半誠實的，則所有節點和伺服器都無法獲取所有的秘密以還原使用者的URL，從而保護了使用者的隱私。我們用Python語言打造了系統的概念證明，並優化了我們的系統，以在URL檢查的情境中更高效地進行計算並減少網絡流量的傳輸。我們在Easylist廣告域數據集上評估了我們系統的整體性能。實驗結果顯示，我們的優化技術在一個簡易的測試中能將計算時間從113.10秒大幅縮短至0.04秒，而在一般情況下，優化後的系統完成一個匹配過程只需要約3至4秒，非常高效。

Recently, as URL checking becomes more and more popular because of widely used Safe Browsing service, its privacy issue becomes more and more important. Therefore, we propose a privacy-preserving URL checking system which splits the user's URL into secret shares to protect the user's privacy. Our system utilizes several computing nodes to compute regular expression matching result on different secret shares, so that as long as at least one node is considered semi-honest, none of the nodes and the server could obtain all the secret shares to reveal the user's URL, and thus the user's privacy is preserved. We design a proof-of-concept of our system in Python, and optimize our system to compute more efficiently and transmit less network traffic in URL checking application. We evaluate our system's overall performance on Easylist ad domain dataset. The result shows that our optimization techniques greatly accelerates the matching process from 113.10s to 0.04s in a simple case, and our well-optimized system takes about 3 \textasciitilde 4s to finish a matching process in average case, which is quite efficient.