Sophos: Forward Private Searchable Encryption

Raphael Bost came to MIT to give a talk on his recent CCS paper about forward private searchable encryption. I’ll give an overview of his work, but I refer you to his paper for more details.

The idea behind searchable encryption is that a user wants to outsource data to the cloud securely while keeping search functionalities. Generic solutions such as Fully Homomorphic Encryption (FHE), Multi-party computation (MPC), and Oblivious RAM (ORAM) have perfect security but large computational and communication overhead. The question is if we can get more efficient solutions. The answer is yes, but we have to leak some information. There is a security/performance tradeoff.

Work on property preserving encryption, such as deterministic encryption and order preserving encryption, are legacy compatible and very efficient, but they are not secure in practice (e.g. attacks on CryptDB). Index-based searchable encryption is a structured encryption of a reversed index, where the search queries allow partial decryption. However, there is search leakage: repetition of queries (search pattern) and update leakage: updated documents and repetition of updated keywords.

There are also file injection attacks, where purposefully crafted documents are injected into the database and binary search is used to recover the query. The active version of this attack use the update leakage property: for an update, most searchable encryption schemes leak if the inserted document matches the previous query. We need searchable encryption schemes with oblivious updates, i.e. forward privacy.

What does “forward private” mean? An update does not leak any information on the updated keywords. So the goals of Sophos is a forward index-based scheme with low search and update overhead. The construction is fairly involved, so I refer you to the paper. However, the main “trick” is to use a trapdoor permutation like RSA, and this results in no update leakage. However, there is still search pattern leakage and a “history” of the keyword w, i.e. the timestamped list of updates of w.

There is an implementation of this scheme on Gitlab. This is an interesting line of research that is working toward performing specialized operations on encrypted data. This type of progress makes certain operations on encrypted data more practical!