1. Oblix: An Efficient Oblivious Search Index 2018 EncryptedDatabases IntelSGX Oakland
    Pratyush Mishra, Rishabh Poddar, Jerry Chen, Alessandro Chiesa and Raluca Ada Popa
    [View PDF on people.eecs.berkeley.edu]
    [Show BibTex Citation]

    @INPROCEEDINGS{8418609,
    author={P. {Mishra} and R. {Poddar} and J. {Chen} and A. {Chiesa} and R. A. {Popa}},
    booktitle={2018 IEEE Symposium on Security and Privacy (SP)},
    title={Oblix: An Efficient Oblivious Search Index},
    year={2018},
    volume={},
    number={},
    pages={279-296},
    keywords={authorisation;cryptography;data structures;query processing;Oblix;searchable encryption;encrypted data;search queries;doubly-oblivious data structures;oblivious search index;oblivious-access techniques;Cryptography;Servers;Indexes;Hardware;Data structures;applied cryptography;cloud security;oblivious ram;searchable encryption},
    doi={10.1109/SP.2018.00045},
    ISSN={2375-1207},
    month={May},}

Search indices are fundamental building blocks of many systems, and there is great interest in running them on encrypted data. Unfortunately, many known schemes that enable search queries on encrypted data achieve efficiency at the expense of security, as they reveal access patterns to the encrypted data. In this paper we present Oblix, a search index for encrypted data that is oblivious (provably hides access patterns), is dynamic (supports inserts and deletes), and has good efficiency. Oblix relies on a combination of novel oblivious-access techniques and recent hardware enclave platforms (e.g., Intel SGX). In particular, a key technical contribution is the design and implementation of doubly-oblivious data structures, in which the client’s accesses to its internal memory are oblivious, in addition to accesses to its external memory at the server. These algorithms are motivated by hardware enclaves like SGX, which leak access patterns to both internal and external memory. We demonstrate the usefulness of Oblix in several applications: private contact discovery for Signal, private retrieval of public keys for Key Transparency, and searchable encryption that hides access patterns and result sizes.

  1.