Building PRISM-Proof Web Services
technologyreview.com
technologyreview.com
(...it would be interesting though if someone figured out a way for the server to only store data without possibility to tie it to a particular identity, so they could still do aggregate queries on it. dunno if it's possible though while still not alowing the client to access data he's not allowed to see. and I bet someone could figure out a way to identify which of the non-client-encrypted-but-anonymized-through-such-a-method data you access from the server is actually yours via some patter recognition...)
I understand that the paper discusses the ability to search the database for a string within records encrypted using different keys (without knowing what the search term is), but it makes no mention of sorting.
Dan Boneh talked about this at trustycon this year. It's a pretty interesting concept.
What makes it impossible for the untrusted server to serve malicious JavaScript? I can't think of a scenario where I could trust code I get from an untrusted party...
"It is possible for a service built with Mylar to search across encrypted data stored on its servers, for example, so a person could search documents they had uploaded to a file storage service."
If the server doesn't have access to the plain text then you are giving the server access to a useful subset so it can do things like index it right? That useful subset must then be of interest to folks in the NSA.... So either the server has access to the plain text (temporarily or permanently) or it has access to a useful subset.
And from there a whole host of attacks are possible. Not that this surprises me. If robust encryption architectures were easy....
E.g. a traditional reverse index is generally conceptually turned into relations <word,word-id> and <word-id,document-id,position> (though in reality there's tons of tricks to store them more efficiently by removing a lot of redundant information).
If all indexing passes through the client (client downloads and decrypts every message, and uploads bits and pieces to update the index with), and the client maintains the <word,word-id> relations (optionally passing it back to the server encrypted, in chunks), you've improved things a bit, but only a tiny bit (anyone with access to the index can apply some fairly trivial statistical attacks that makes it uninteresting to attack the encrypted real messages).
You can improve on that by leaving off or fuzz the position to reduce the potential for statistical analysis, at the cost of recall. E.g. if you drop position entirely, you can get the server to tell you which documents contains the individual words in "service built with Mylar", but you'll have to retrieve all of them to determine if the phrase is present.
You can also do stuff like "inventing" additional detail. E.g. assign "fuzz" word-id 42, but based on some operation on the document id, you might also/instead assign it word-id 201. The problems with each of these type of attempts at obfuscation is that they alter your search patterns, and you'd need to figure out how to obscure from the server that word-id's 42 and 201 in fact are two different subsets of the same thing, or you're still leaking information. You can also record outright wrong information, at the cost of having to download more messages to weed out the false positives when searching.
You can "scale" your tradeoff between accurate recall and information leak pretty much arbitrarily from letting the server only see a single bit of your word-id and a single bit of your document id's, to the full word-id, document-id and position, depending on how much work you're willing to do client side - every bit you chop off means you need to retrieve a larger number of documents to post-process the results to get something useful, but gives the server less information about your document collection.
You can improve further on it by letting third parties provide "indexing services" and farm the indexing to them, without ever letting them see the documents. You could even break the collection into pieces and merge the results client side, so no single service has the whole picture. But of course it just raises the bar for an adversary.
But you are of course right that all of this is going to leak information that might be useful to an adversary - the approach taken just moves the difficulty bar up and down a bit. Ultimately all you can do is make an assessment about how much the information is worth to you and make an educated guess based on that about how much you can "afford" to farm out to servers that are not under your physical control...
Frankly I think the problem with NSA-proofing it, though, is that while you can certainly take pleasure in driving up their costs, if you make it impossible for them to simply eavesdrop or break your encryption, the only thing you've really achieved is to make them prioritise other attacks, like capturing copies of all the mail before it reaches your servers. Large amounts of that traffic will be entirely unencrypted anyway, since many of the sites people exchange e-mail with still don't support SSL/TLS.
If the NSA wants it, they've already got it folks.
They mention search. I wrote a comment elsewhere in this thread about some simple approaches to doing that while reducing information leaks (that'd potentially make more serious attacks on your documents viable if you're not very careful), but if they have some cryptographically sound mechanisms to outright prevent information leaks but still allow searches for example, that'd be a big deal.
In theory, homomorphic encryption might eventually let us let the server run almost any algorithm over the encrypted data without decrypting it, but for now, they are way too slow to be practical for most things.