Secure Compression and Pattern Matching Based on Burrows-Wheeler Transform

Searchable compressed data structures (e.g.Burrows-Wheeler Transform) enable one to create a memoryefficient index for large datasets such as human genomes. On the other hand, storing such an index in a third-party server, e.g., cloud, may have the privacy and confidentiality issues. An open problem in the community is to construct a secure variant of such a data structure. This problem is challenging as most of the existing works were shown to be insecure and none of them is able to perform pattern matching. In this paper, we provide the first solution based on Burrows-Wheeler Transform (BWT) to solve this problem (our scheme can do both compression and pattern matching). A new security definition, called isomophism-restricted IND-CPA security, is proposed. We show that our scheme is secure under this definition and our scheme is practical by experiments.