Research On Cloud-based Verifiable Pattern Matching

Verifiable pattern matching enables users to obtain authenticated pattern matching results over outsourced text data on an untrusted cloud server,which is a fundamental problem in many security-critical big data applications.Especially when these pattern matching based applications are outsourced to third-party clouds,including big database search,human genome data search,text search,etc.,the verification problem is particularly important.However,current schemes proposed to solve this verification problem not only suffer from low efficiency,which still have room for optimization,but also do not yet support efficient data updates.Therefore,in this thesis,we conduct our research and propose schemes to optimize performance and solve efficiency problem of data updates.We made two contributions as follows.First,we propose a secure hashing based verifiable pattern matching scheme,which significantly improves the performance of the state-of-the-art scheme.We design a novel verifiable data structure for pattern matching based on the newly proposed ordered set accumulator and the classical suffix array structure.Our scheme only involves fast cryptographic hash computations,resulting in vast performance improvements.It also supports multi-pattern matching verification,which is more suitable for practical applications.In addition,our scheme supports public verifiability with no secret key requirement.We prototyped the proposed scheme;the experimental results confirm that the performance of our scheme is better than the state-of-the scheme.Second,we propose a dynamic verifiable pattern matching scheme to support efficient data updates.We embed unique randomness to decouple the character and its index in the outsourced data and convert continuous text data to discrete set data for enabling efficient data updates.Then we reduce the verification problem to a discrete set membership testing problem.By employing the RSA accumulator as a tool,we finally construct a dynamic verifiable pattern matching scheme.To our best knowledge,this is the first scheme that supports efficient data updates.In addition,the proposed scheme also partially improves the performance in storage and computation cost,compared with the state-of-the-art scheme.Experimental evaluation shows that the performance and data update supporting of our scheme is encouraging for its use in practical applications,in comparison with the best existing scheme.