Sophos – Forward Secure Searchable Encryption

I do research in this area. What exactly would you like clarified?

The abstract, if you rearrange it and remove some of the jargon, is actually pretty comprehensible (to me, at least).

> Searchable Symmetric Encryption aims at making possible searching over an encrypted database stored on an untrusted server while keeping privacy of both the queries and the data… This work proposes [a new, more efficient technique], which does not leak [whether or not] a newly inserted element matches previous search queries.

Further TL;DR: a way to put an encrypted dataset on an untrusted server such that it can be efficiently searched without the server knowing the decryption key or even the search query. Queries cannot be rerun after more data is added (which would otherwise leak information about the encrypted dataset and/or encrypted query).

I'll just explain the searchable part. I'm an amateur cryto enthusiast, though.

Basically, you'd think to search through an encrypted database, you'd have to decrypt it first. That's a pain in the ass if your DB is in some place outside of your complete control. You can't give them your key and tell them to decrypt it, because your DB host will decrypt and know all your secret information. The other way is to download the entire DB, which is impossible for obvious reasons. Even if you controlled your own DB, with traditional encryption you'd have to decrypt each entry and figure out if your thing matches the entry. (You could compare ciphertext, though, which I don't know why this isn't the accepted standard)

Basically this scheme is proposing a way to do it even on DB's controlled by a hostile actor. Pretty neat.

I haven't looked closely at the full construction, but it's fairly similar to an earlier paper by Cash et al. (https://eprint.iacr.org/2014/853) which is surprisingly practical - their system can do keyword searches on the entire English Wikipedia in just a couple seconds.

In terms of security, things are a bit more complicated. The last ~year has seen a couple papers (https://eprint.iacr.org/2016/718 and https://eprint.iacr.org/2016/172) that demonstrate damaging and practical attacks against most SSE constructions. It's really not clear how secure any SSE scheme is in practice, or whether there is a sensible model in which SSE can be both secure and efficient enough for practical use.

Do you mean https://gitlab.com/sse/sophos/tree/master ?

    > Sophos' dependencies need a compiler 
    > supporting C++14 (Sophos' core codebase doesn't).
    > It has been successfully built and tested on 
    > Ubuntu 14 LTS using both clang 3.6 and gcc 4.9.3 
    > and on Mac OS X.10 using clang 7.0.0

I don't see Windows mentioned anywhere.