ObSQRE : efficient full-text index for oblivious substring search queries with Intel SGX

The problem of finding the positions of the repetitions of a string within a text, known as substring search, recurs in many application scenarios. When the size of the text is huge, the construction of a full-text index is the only viable solution since it allows to perform substring search queries in sublinear time. In this scenario, it may be unconvenient to store the index locally, in turn requiring to outsource both the data and the computation to the cloud. This may become an issue when dealing with confidential information, e.g. biological data of a patient who resorts to personalized medicine, since an untrusted cloud service provider may gain illicit benefits from such confidential data. Secure enclaves allow to instantiate trusted and authenticated execution environments on untrusted machines, preventing any rogue access to their internal content. While they allow to securely handle confidential data in plaintext, the most widespread implementation of enclaves, Intel SGX, is prone to side channel attacks that are especially effective in leaking sensitive information. In this work, we propose Oblivious Substring Query on Remote Enclave (ObSQRE), a novel substring search protocol that implements oblivious full-text indices to solve the private substring search problem in the outsourcing scenario. It prevents an adversary with root privileges on an untrusted machine from inferring the structure of the text as well as the correlation between queries. It encompasses three different substring search algorithms that rely on the ORAM cryptographic primitive to prevent any information leakage. To the best of our knowledge, ObSQRE is the first to directly address the remote private substring search problem exploiting secure enclaves. ObSQRE exhibits practical performance, being able to find occurrences of a protein (~3000 nucleotides) within 32 MB of genomic data in only 500 ms.

La ricerca di sottostringhe all'interno di un testo più ampio è un problema comune in diversi scenari. Quando la dimensione del testo è considerevole, opportune strutture di indicizzazione consentono di cercare sottostringhe con complessità sublineare nella lunghezza del testo; date le dimensioni usuali di un indice, potrebbe essere dispendioso memorizzarlo ed interrogarlo su una macchina desktop. Una possibile soluzione consiste nell'esternalizzare sia l'indice che la ricerca delle sottostringhe presso un fornitore di servizi di cloud computing. Quando i dati contenuti nel testo sono sensibili, come per esempio quelli del genoma di un paziente che si sottopone a trattamenti di medicina personalizzata, affidare la gestione delle informazioni ad un soggetto terzo presenta criticità legate alla privacy dei dati. In questo contesto, le enclavi consentono di eseguire le porzioni sensibili di un programma in un'area di memoria inaccessibile dall'esterno, consentendo di operare su dati in chiaro senza compromettere la loro segretezza. Tuttavia l'implementazione di enclavi più diffusa, Intel SGX, è vulnerabile ad attacchi a side channel, che sono in grado di estrarre il contenuto di enclavi che non adottano contromisure specifiche. In questo lavoro presentiamo Oblivious Substring Query on Remote Enclave (ObSQRE), un nuovo protocollo per la ricerca di sottostringhe basato su indici testuali cosiddetti oblivious, che garantiscono sia la segretezza del testo che delle sottostringhe cercate, nascondendo anche le loro similarità. ObSQRE fornisce tre distinti algoritmi di ricerca, che sfruttano le ORAM per nascondere le informazioni recuperabili tramite side channels. Secondo la nostra indagine, ObSQRE è la prima soluzione per la ricerca di sottostringhe in maniera oblivious basata su enclavi. I risultati sperimentali mostrano l'efficienza di ObSQRE in scenari reali, dato che è possibile cercare una proteina (~3000 nucleotidi) in un genoma di 32 MB in circa 500 ms.