Oblivious NFA evaluation with an untrusted third party
Oblivious substring matching is a well-studied problem, with plentiful applications in scenarios with privacy-preservation requirements, e.g., genome matching, malicious code detection, etc. A natural generalization of oblivious substring matching is oblivious finite automata evaluation, which matc...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
Nanyang Technological University
2022
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/162890 |
| _version_ | 1811681397485600768 |
|---|---|
| author | Zhou, Haoran |
| author2 | Tay Kian Boon |
| author_facet | Tay Kian Boon Zhou, Haoran |
| author_sort | Zhou, Haoran |
| collection | NTU |
| description | Oblivious substring matching is a well-studied problem, with plentiful applications in scenarios with privacy-preservation requirements, e.g., genome matching, malicious code detection, etc. A natural generalization of oblivious substring matching is oblivious finite automata evaluation, which matches a wider collection of patterns than substrings. In this paper, we propose an efficient protocol for the oblivious evaluation of Non-deterministic finite Automata (NFA) with the help of an untrusted third party and extend the protocol to Non-deterministic Finite state transducers. We prove the security of the protocol against one corrupted party. We further experiment with such protocol on a pattern-matching task with its complexity. |
| first_indexed | 2024-10-01T03:40:18Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/162890 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:40:18Z |
| publishDate | 2022 |
| publisher | Nanyang Technological University |
| record_format | dspace |
| spelling | ntu-10356/1628902022-11-11T08:13:44Z Oblivious NFA evaluation with an untrusted third party Zhou, Haoran Tay Kian Boon School of Computer Science and Engineering kianboon.tay@ntu.edu.sg Engineering::Computer science and engineering::Data::Data encryption Oblivious substring matching is a well-studied problem, with plentiful applications in scenarios with privacy-preservation requirements, e.g., genome matching, malicious code detection, etc. A natural generalization of oblivious substring matching is oblivious finite automata evaluation, which matches a wider collection of patterns than substrings. In this paper, we propose an efficient protocol for the oblivious evaluation of Non-deterministic finite Automata (NFA) with the help of an untrusted third party and extend the protocol to Non-deterministic Finite state transducers. We prove the security of the protocol against one corrupted party. We further experiment with such protocol on a pattern-matching task with its complexity. Bachelor of Engineering (Computer Engineering) 2022-11-11T08:13:44Z 2022-11-11T08:13:44Z 2022 Final Year Project (FYP) Zhou, H. (2022). Oblivious NFA evaluation with an untrusted third party. Final Year Project (FYP), Nanyang Technological University, Singapore. https://hdl.handle.net/10356/162890 https://hdl.handle.net/10356/162890 en SCSE21-0810 application/pdf Nanyang Technological University |
| spellingShingle | Engineering::Computer science and engineering::Data::Data encryption Zhou, Haoran Oblivious NFA evaluation with an untrusted third party |
| title | Oblivious NFA evaluation with an untrusted third party |
| title_full | Oblivious NFA evaluation with an untrusted third party |
| title_fullStr | Oblivious NFA evaluation with an untrusted third party |
| title_full_unstemmed | Oblivious NFA evaluation with an untrusted third party |
| title_short | Oblivious NFA evaluation with an untrusted third party |
| title_sort | oblivious nfa evaluation with an untrusted third party |
| topic | Engineering::Computer science and engineering::Data::Data encryption |
| url | https://hdl.handle.net/10356/162890 |
| work_keys_str_mv | AT zhouhaoran obliviousnfaevaluationwithanuntrustedthirdparty |