Towards Dynamic Verifiable Pattern Matching

Verifiable pattern matching enables users to obtain authenticated query results over outsourced data on an untrusted remote server. It is a fundamental problem in many security-critical big data applications, including big database search, human genome data search, text search, etc., especially when these applications are outsourced to third-party clouds. However, the state-of-the-art schemes do not yet support efficient data updates. In this work, we propose the first dynamic verifiable pattern matching scheme to support efficient data updates. The proposed scheme is built on two ideas: one is to embed unique randomness to decouple the character and its index in the outsourced data, enabling efficient data updates; the other is to reduce the verifiable pattern matching problem to a discrete set membership testing problem, which relies on the decoupling introduced in the first idea. Based on these two ideas, the proposed scheme first employs the suffix array index structure to search pattern matching queries. The scheme then authenticates the outsourced text using a newly designed authenticated data structure based on the RSA accumulator, which guarantees the verifiability of pattern matching query results. Data update is naturally supported using the RSA accumulator working on discrete sets. Based on the proposed design, we have prototyped a proof-of-concept for the proposed scheme and have conducted an extensive experimental evaluation. In addition to supporting efficient data update, our experimental results show that the proposed scheme incurs reduced verification cost in comparison with the baseline state-of-the-art scheme.

1 Introduction

With the development of next generation Internet of Things technologies, a massive data will be widely collected and used, supporting a number of big data-driven applications and changing our daily lives [1], [2], [3]. Pattern matching in big data is a fundamental problem widely studied, employed in many practical applications [4], [5], [6], [7], [8], [9], [10], including cybersecurity threat detection, traffic filtering, database query, biological computing, and others. Due to the limitations of local computing resources and the rapid development of cloud computing and ubiquitous computing, pattern matching outsourcing to remote servers has attracted growing interest as an alternative to traditional pattern matching on local servers (e.g., [11]).