There’s a nice new paper out called “Private Editing Using Untrusted Cloud Services” by Yan Huang and David Evans. They also provide a Firefox extension that implements their scheme. I like their approach for a few reasons.
First, their core advancement is to implement incremental encryption efficiently. Incremental encryption is an often-overlooked method of performing insert, delete, and replace operations on ciphertext. It’s a useful branch of applied cryptography — one that should be used more.
However, the naive implementation of incremental encryption would involve encrypting each character separately, slowing down client/server communications a lot. To get around this, they organize deltas in an Indexed Skip List. This makes it easy to group characters into variable-sized blocks, as well as update them quickly.
For those of you implementing “secure” note-taking web services, this is the right way to do it.