Privacy preserving fuzzy keyword search in database as a service paradigm

The database service provider is Honest-But-Curious in a Database as a Service (DaaS) paradigm. Thus, to guarantee the confidentiality and searchability of all outsourced data, the owners always encrypt them by using particular encryption techniques, such as the searchable encryption, homomorphic encryption, etc. However, most of these proposed works are designed for searching on outsourced data by accurate keyword matching. Only a few research works are concerning about encrypted-database fuzzy keyword search, while they also have limitations in the query efficiency, storage consumption and security. Therefore they are not suitable to the DaaS paradigm. In this paper, a privacy preserving fuzzy keyword search mechanism is proposed by combining the high coding-efficiency Huffman codes with high storage-efficiency Bloom filters under the support of existing secure encryption algorithms. On one hand, the Huffman coding based index tree provides high search efficiency; on the other hand, the similarity keyword set based Bloom filters achieves low storage consumption. Analysis of security and performance, and real data set based experiments further confirm the security, storage consumption and search efficiency of proposed search techniques.