Yeah, I'd love a "Tarsnap for email". GMail is good, but I do worry about it. But encrypting everything as soon as it arrives would push the burden of searching and filtering back out to the client. Haven't figured out an optimal solution.

Why would it be pushed to the client?

Seems to me you can do this just as well on server side, and work more on ensuring Server<->Client interface security. Crypto tokens would be a start.

How would you do a full text search on the server if the server only holds an encrypted version of the data? To my knowledge, no homomorphic encryption algorithms exist that can be used for practical applications such as full-text search.

The way to tackle this would be to make index creation on the client incremental: any new messages are downloaded, decrypted, indexed, the index encrypted and uploaded back to the server. I'm not good enough with either search/indexing or crypto to know how you'd use such an incremental encrypted index to perform an actual search without having to decrypt (and therefore download) the entire index first. In fairness, I haven't researched this yet.

Securing the client-server comms is a solved problem, I'm not aware of any problems with SSL/TLS as long as the server also authenticates itself (which current browsers don't permit, but is easy to do with SSL directly).

Caveat: I'm neither cperciva nor tptacek (let alone Bruce Schneier) so there's a high probability I made some factual mistakes in this post.

How about a mutually-trusted third party (somewhat like OpenID identity providers are supposed to work right now)? The mail service uploads your encrypted index to the search provider, you upload your key directly to them as well (possibly beforehand), and the search provider returns the results to the mail service. It's not quite client- or server-side, then, though; after all, you could specify the third party to be your own machine if you were paranoid, or their own server if you were lazy/unconcerned. It creates more of a flexible spectrum of privacy levels.

There has been a lot of work in the last 10 years on search over encrypted data. Some of the more practical schemes do operate similar to how you describe; searching over encrypted indices. For example, check out Chang & Mitzenmacher's "Privacy Preserving Keyword Searches on Remote Encrypted Data": http://eprint.iacr.org/2004/051.pdf

There has also been a lot of theoretical work in topics like predicate- and functional-encryption which could eventually be used for richer queries.

I'm forgetting - which author wrote about 'Friends of Privacy' who would create false profiles and websites in order to protect the populace?

Question for you - how much would you be willing to pay for your name, user accounts, and other specific information to never come up on the first page of Google, Pipl, or other search engines?

Vernor Vinge - Rainbows End

ReputationDefender.com/MyPrivacy

It appears to be very cheap. I have no connection with this company or anyone who works for it, ttbomk.

MyPrivacy protects you from stalkers, scam artists and direct marketers, by continually tracking down your personal information and removing it from databases on the Internet. MyPrivacy removes your name, address, age, phone number, past addresses, and names of relatives from websites that sell or give away your personally identifiable information without your permission.

Amazing. Well done. Thank you.