Pbsx: A Practical Private Boolean Search Using Intel SGX

Abstract Searchable encryption enables private keyword search over encrypted data held on an untrusted cloud. However, existing searchable encryption schemes promise search efficiency at the expense of additional privacy leakage or expensive storage overhead. Intel SGX is a promising tool to allow efficient and private keyword search. However, since the size of enclave created by SGX is limited, frequent sensitive-page swaps between the enclave and the untrusted memory cause severe performance degradation for large datasets. Moreover, SGX does not protect against access pattern leakages which are vulnerable to statistical inference attacks. To overcome the above problems, we present Pbsx, an efficient private boolean searchable encryption scheme using Intel SGX. Pbsx firstly analyzes and chooses the suitable index data structures (e.g. bitmap and bloom filter tree) for private boolean search in the context of Intel SGX. Pbsx then combines these index data structures with oblivious random access machine (ORAM) schemes to design oblivious index data structures (e.g. oblivious bitmap and oblivious bloom filter tree), such that it could provide storage efficiency without suffering from access pattern leakages. Since the direct composition of the index data structures and the ORAM schemes is extremely costly for search operations, we design auxiliary data structures (e.g. map table and id index tree) to mitigate the efficiency barrier. Based on these oblivious index data structures, we propose oblivious search algorithms which can achieve a worst-case sub-linear search time. We implement Pbsx and evaluate the performance of our constructions with various metrics. Comparing with previous schemes, the results indicate that when the number of search keywords in the query is more than 500, Pbsx achieves a 5∼12x speed-up for the million-level dataset and a 13∼51x speed-up for the small dataset. In addition, Pbsx also achieves less access pattern leakages.