請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/90015
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 蕭旭君 | zh_TW |
dc.contributor.advisor | Hsu-Chun Hsiao | en |
dc.contributor.author | 賴侃軒 | zh_TW |
dc.contributor.author | Kan-Hsuan Lai | en |
dc.date.accessioned | 2023-09-22T17:03:50Z | - |
dc.date.available | 2023-11-09 | - |
dc.date.copyright | 2023-09-22 | - |
dc.date.issued | 2023 | - |
dc.date.submitted | 2023-08-13 | - |
dc.identifier.citation | Backlinko. Backlinko: google search results analysis. https://backlinko.com/search-engine-ranking, May 2023.
D. Beaver. Efficient multiparty protocols using circuit randomization. CRYPTO (1991), pages 420––432, 1991. Ross Cox. Regular expression matching can be simple and fast (but is slow in java, perl, php, python, ruby, ...). https://swtch.com/~rsc/regexp/regexp1.html, May 2023. Helei Cui, Yajin Zhou, Cong Wang, Xinyu Wang, Yuefeng Du, and Qian Wang. Ppsb: An open and flexible platform for privacy-preserving safe browsing. IEEE Transactions on Dependable and Secure Computing, 18(4):1762–1778, 2021. Roger Dingledine, Nick Mathewson, and Paul F. Syverson. Tor: The second-generation onion router. In Matt Blaze, editor, Proceedings of the 13th USENIX Security Symposium, August 9-13, 2004, San Diego, CA, USA, pages 303–320. USENIX, 2004. Yuefeng Du, Huayi Duan, Lei Xu, Helei Cui, Cong Wang, and Qian Wang. Peba:Enhancing user privacy and coverage of safe browsing services. IEEE Transactions on Dependable and Secure Computing, pages 1–15, 2022. EasyList. Easylist filter blocking rules. https://adblockplus.org/filter-cheatsheet, May 2023. EasyList. Easylist filter list, version: 202305230654. https://easylist.to/easylist/easylist.txt, May 2023. Thomas Gerbet, Amrit Kumar, and Cédric Lauradoux. A privacy analysis of google and yandex safe browsing. In 2016 46th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 347–358, 2016. V M Glushkov. The abstract theory of automata. Russian Mathematical Surveys, 16(5):1, oct 1961. Google. Google safe browsing. https://safebrowsing.google.com/, May 2023. Google. Google safe browsing api. https://developers.google.com/safe-browsing/v4, May 2023. Google. Google safe browsing statistics. https://transparencyreport.google.com/safe-browsing/overview, May 2023. Google. Google/re2: Re2 is a fast, safe, thread-friendly alternative to backtracking regular expression engines like those used in pcre, perl, and python. it is a c++ library. https://github.com/google/re2, May 2023. Hermann Gruber and Markus Holzer. From finite automata to regular expressions and back — a summary on descriptional complexity. Electronic Proceedings in Theoretical Computer Science, 151:25–48, may 2014. John Hopcroft. An n log n algorithm for minimizing states in a finite automaton. In Zvi Kohavi and Azaria Paz, editors, Theory of Machines and Computations, pages 189–196. Academic Press, 1971. Myungsun Kim, Hyung Tae Lee, San Ling, Benjamin Hong Meng Tan, and Huax-iong Wang. Private compound wildcard queries using fully homomorphic encryption. IEEE Transactions on Dependable and Secure Computing, 16(5):743–756, 2019. Tingwen Liu, Alex X. Liu, Jinqiao Shi, Yong Sun, and Li Guo. Towards fast and optimal grouping of regular expressions via dfa size estimation. IEEE Journal on Selected Areas in Communications, 32(10):1797–1809, 2014. Edward F Moore et al. Gedanken-experiments on sequential machines. Automata studies, 34:129–153, 1956. Yoshiki Nakagawa, Satsuya Ohata, and Kana Shimizu. Efficient privacy-preserving variable-length substring match for genome sequence. Algorithms for Molecular Biology, 17(1):9, Apr 2022. Salman Niksefat, Babak Sadeghiyan, Payman Mohassel, and Saeed Sadeghian. Zids: A privacy-preserving intrusion detection system using secure two-party computation protocols. The Computer Journal, 57(4):494–509, 2014. M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2):114–125, 1959. Luigi Sgaglione, Luigi Coppolino, Salvatore D’Antonio, Giovanni Mazzeo, Luigi Romano, Domenico Cotroneo, and Andrea Scognamiglio. Privacy preserving intrusion detection via homomorphic encryption. In 2019 IEEE 28th International Conference on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE), pages 321–326, 2019. Kana Shimizu, Koji Nuida, Hiromi Arai, Shigeo Mitsunari, Nuttapong Attra-padung, Michiaki Hamada, Koji Tsuda, Takatsugu Hirokawa, Jun Sakuma, Goichiro Hanaoka, and Kiyoshi Asai. Privacy-preserving search for chemical compound databases. BMC Bioinformatics, 16(18):S6, Dec 2015. Ken Thompson. Programming techniques: Regular expression search algorithm. Commun. ACM, 11(6):419–422, jun 1968 | - |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/90015 | - |
dc.description.abstract | 近年來,URL檢查由於安全瀏覽服務的廣泛使用,因此其隱私問題變得愈發重要。有鑑於此,我們提出了一個保護隱私的URL檢查系統,其特色為將使用者的URL分割成若干份秘密以保護使用者的隱私。我們的系統利用多個計算節點對不同份秘密進行正則表達式匹配,因此只要至少有一個節點被視為半誠實的,則所有節點和伺服器都無法獲取所有的秘密以還原使用者的URL,從而保護了使用者的隱私。我們用Python語言打造了系統的概念證明,並優化了我們的系統,以在URL檢查的情境中更高效地進行計算並減少網絡流量的傳輸。我們在Easylist廣告域數據集上評估了我們系統的整體性能。實驗結果顯示,我們的優化技術在一個簡易的測試中能將計算時間從113.10秒大幅縮短至0.04秒,而在一般情況下,優化後的系統完成一個匹配過程只需要約3至4秒,非常高效。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2023-09-22T17:03:50Z No. of bitstreams: 0 | en |
dc.description.provenance | Made available in DSpace on 2023-09-22T17:03:50Z (GMT). No. of bitstreams: 0 | en |
dc.description.tableofcontents | 口試委員會審定書 i
誌謝 ii 摘要 iii Abstract iv Contents v List of Figures viii List of Tables ix 1 Introduction 1 2 Background 5 2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Deterministic Finite Automaton . . . . . . . . . . . . . . . . . . . . 7 2.3 Regex Transformation . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Secret Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4.1 Split a Secret . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4.2 Reconstruct a Secret . . . . . . . . . . . . . . . . . . . . . . 10 2.5 Computations on Secret Sharing Domain . . . . . . . . . . . . . . . 10 2.5.1 XOR Operation on the Secret Sharing Domain . . . . . . . . 11 2.5.2 NOT Operation on the Secret Sharing Domain . . . . . . . . 11 2.5.3 AND Operation on the Secret Sharing Domain . . . . . . . . 12 2.5.4 OR Operation on the Secret Sharing Domain . . . . . . . . . 14 3 Problem Definition 15 3.1 Entities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Threat Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 Design Goal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4 Proposed Method 18 4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2.1 User . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2.2 Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2.3 Computing Node . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3 Regex Matching on the Secret Sharing Domain . . . . . . . . . . . . 21 4.3.1 Split DFA Matrix into Secret-Shared Form . . . . . . . . . . 22 4.3.2 Comparison between Secret Shares on Secret Sharing Domain 23 4.3.3 Obtain Value from Secret-Shared DFA Matrix . . . . . . . . . 24 4.3.4 Evaluate Result on Secret-Shared DFA Matrix . . . . . . . . 26 5 Implementation 27 5.1 Basic Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.1.1 Generate Secret-Shared DFA Matrix . . . . . . . . . . . . . . 27 5.1.2 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.1.3 Evaluate Result . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.2 Optimization 1: Compare Input and State Separately . . . . . . . . . 29 5.3 Optimization 2: Perform Independent-ANDs in One Request . . . . . 31 5.4 Optimization 3: Use PRNG to Generate Split Beaver Triples . . . . . 31 5.5 Optimization 4: Reduce Input Character Set . . . . . . . . . . . . . . 32 6 Evaluation 33 6.1 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.2 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6.2.1 Complexity of DFA Size . . . . . . . . . . . . . . . . . . . . 34 6.2.2 the Number of AND Operations . . . . . . . . . . . . . . . . 37 6.2.3 Beaver Triple Length . . . . . . . . . . . . . . . . . . . . . . 38 6.3 Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.4 Computation Time and Network Traffic Size . . . . . . . . . . . . . 41 7 Related Work 46 8 Discussion and Future Work 48 8.1 Verifiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 8.2 Availability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 8.3 Evaluation on Multiple DFAs . . . . . . . . . . . . . . . . . . . . . 49 8.4 Limitation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 9 Conclusion 51 Bibliography 52 | - |
dc.language.iso | en | - |
dc.title | 利用分散式正規表式比對保護URL檢查之隱私 | zh_TW |
dc.title | Distributed Regular Expression Matching for Privacy-Preserving URL Checking | en |
dc.type | Thesis | - |
dc.date.schoolyear | 111-2 | - |
dc.description.degree | 碩士 | - |
dc.contributor.oralexamcommittee | 游家牧;陳昱圻 | zh_TW |
dc.contributor.oralexamcommittee | Chia-Mu Yu;Yu-Chi Chen | en |
dc.subject.keyword | 正規表式比對,隱私保護,URL 檢查,秘密分享,DFA, | zh_TW |
dc.subject.keyword | regex matching,privacy-preserving,URL checking,secret sharing,DFA, | en |
dc.relation.page | 55 | - |
dc.identifier.doi | 10.6342/NTU202304122 | - |
dc.rights.note | 同意授權(全球公開) | - |
dc.date.accepted | 2023-08-13 | - |
dc.contributor.author-college | 電機資訊學院 | - |
dc.contributor.author-dept | 資訊工程學系 | - |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-111-2.pdf | 1.07 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。