Efficient Oblivious Substring Search via Architectural Support

Performing private and efficient searches over encrypted outsourced data enables a flourishing growth of cloud based services managing sensitive data as the genomic, medical and financial ones. We tackle the problem of building an efficient indexing data structure, enabling the secure and private execution of substring search queries over an outsourced document collection. Our solution combines the efficiency of an index-based substring search algorithm with the secure-execution features provided by the SGX technology and the access pattern indistinguishability guarantees provided by an Oblivious RAM. To prevent the information leakage from the eventual access pattern side-channel vulnerabilities, we redesign three ORAM algorithms, and perform a comparative evaluation to find the best engineering trade-offs for a privacy-preserving index-based substring search protocol. The practicality of our solution is supported by a response time of about 1 second to retrieve all the positions of a protein in the 3 GB string of the human genome.