ZeroDB white paper: An end-to-end encrypted database
Interesting concept. I disagree with this statement from the "Data confidentiality" section:<p>> Unlike CipherBase [6], our approach doesn’t leak information about the order of the elements. By observing access patterns, the server can only figure out which buckets are leaf nodes and which are branch nodes, but not whether the child node is located to the left or right of the parent node.<p>The paper correctly notes that when a client does a range query, it leaks information about the total number of blocks returned. However, if I've understood correctly, it <i>also</i> leaks the identities of those blocks. The closer two tree nodes are in order, the more likely they are to be touched by the same request. A passive adversary could use this to extract information about the relative ordering of encrypted nodes.<p>Also, active adversaries cause much worse problems. Let's say I have the ability to cause someone to do queries on the encrypted database, without observing the results. By simply doing separate index lookups on two different fields, I can extract a lot of information by looking at which nodes were touched by both queries.<p>Finally, I noticed that the paper doesn't describe how the B-trees are modified. If the client is the only party that knows how to decrypt nodes, then it's responsible for splitting and merging nodes to keep the tree balanced. Doesn't this require some kind of distributed coordination, so that multiple clients don't trample on each other's changes?