Secure Outsourced Pattern Matching based on Bit-Parallelism | ||
| The Modares Journal of Electrical Engineering | ||
| Article 2, Volume 16, Issue 3, 2016, Pages 14-23 PDF (819.32 K) | ||
| Authors | ||
| Mohamad Hasan Samadani; Mehdi Berenjkoub* | ||
| Isfahan University of Technology | ||
| Abstract | ||
| Secure outsourcing is essential to growth of cloud usage. There are some protocols allowing any functionality to be outsourced. However, specific constructions are necessary in order to do so in an efficient way. In this paper, we consider the problem of secure outsourced pattern matching. Our solution is based on Bit-Parallel Shift-ADD algorithm. The properties of this insecure algorithm allow our construction to search in an outsourced text, without revealing any non-trivial information to the computing server. We achieve a round optimal protocol that allows us to search for patterns with wildcards and handles the Hamming distance computation. Since the protocol has no leakage to the server, it cannot be optimal considering communication complexity; however, we suggest efficient techniques to achieve communication optimality through outsourcing of decryption as well. The security of our protocol is proved in the semi-honest setting. Then, in order to retain the efficiency of the protocol, we omit the correctness property in the malicious setting and prove that the scheme remains private in the presence of malicious adversaries. | ||
| Keywords | ||
| : secure pattern matching; two-party computation; outsourcing; Bit-Parallel Shift-ADD | ||
|
Statistics Article View: 92 PDF Download: 57 |
||
| Number of Journals | 45 |
| Number of Issues | 2,196 |
| Number of Articles | 24,877 |
| Article View | 28,764,255 |
| PDF Download | 18,602,797 |