I am not a cryptographer so I'm not entirely sure what I'm reading, I mean I'm technically literate like most of you but cryptography is not my field.
Is there any chance it's possible for somebody to reduce this to an understandable precis for the uninitiated, or is that a ridiculous question considering the topic at hand?
Any clarification in explanation would certainly be welcome, I'd just like to understand a little more. Thanks in advance!
> 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).
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.
* The client stores does a lot of work (storing a map of all keys, for one). Could the client get away with ONLY generating a new search token when a document is updated/inserted? That is, could the client only be responsible for creating "UTc+1 ← H1(Kw, STc+1)" and "e ← ind ⊕ H2(Kw, STc+1)" (in the update portion of "Algorithm 1")? In other words, could the map W be stored on the server, as well?
Hope these questions make sense!
- You could store W on the server, but you would leak additional information to the server during an update - namely, the per-keyword update frequency. Section 5.5 describes an extension to reduce client-side storage at the cost of additional computation.