Q-Gram Based Encrypted Codeword Dictionary for Fast Searches Over a Large Collection of Encrypted Unstructured Documents

Abstract

With the advent of cloud computing, many businesses prefer to store their unstructured documents over the cloud. The preference is to store the encrypted unstructured document over the cloud for security. In most of these instances, one of the main criteria is to support fast searches without requiring any form of decryption. It is thus important to develop methods and architectures that can perform fast searches without compromising security and return the rank results for a client query. The proposed scheme use the enhanced version of the symmetric encryption algorithm for unstructured documents and develops a novel secure searchable hierarchical in-memory indexing scheme for each encrypted document using multiple Bloom filters and construct a dictionary over a large collection of encrypted unstructured documents. The dissertation also proposes a method to perform parallel rank searches over a large collection of encrypted unstructured documents. This is a novel contribution that proposes a methodology of constructing a dictionary using hierarchical in-memory index for performing fast and parallel rank searches over a large collection of encrypted unstructured documents. It introduces the concept of Q-gram and X-gram to represent the sizes of secure words in a single keyword and multiple keyword setups for building the encrypted searchable index, and provide multiple Bloom filters for a given encrypted unstructured document or a chunk to build encrypted searchable indexes using a separate Bloom filter for a set of bytes. The proposed construction enables fast rank searches over encrypted unstructured documents. A detailed study of 44 billion codewords worked out using off the shelf serves to demonstrate the effectiveness of single keyword Layer Indexing method. A detailed study of up to 1 billion codewords from a patient health care data is worked out using of the shelf serves to demonstrate the effectiveness of M-Index method.