You've probably seen CryptDB from MIT. They make it possible to do certain types of queries (range etc) by making security compromises (giving some clues to hack encryption).
We don't make such compromises (zero compromises, yes!). The way we do it is to actually traverse encrypted b-trees from the client, while b-trees are on the server. So, we pretty much split it between client and server at the lowest level of how db operates
Well, actually the server doesn't know the ordering and how pieces of B-Tree refer to each other, it doesn't even know which data form the index and which are the actual data.
Though, observing access patterns, it could probably deduce which data belong to the tree and some info about ordering (which will hold true until we re-balance the tree, which happens on inserts).
I think, if we change objects each time we do queries, we can prevent this data leak.
Comments
You've probably seen CryptDB from MIT. They make it possible to do certain types of queries (range etc) by making security compromises (giving some clues to hack encryption).
We don't make such compromises (zero compromises, yes!). The way we do it is to actually traverse encrypted b-trees from the client, while b-trees are on the server. So, we pretty much split it between client and server at the lowest level of how db operates
Doesn't that reveal information to the server based on which B-trees the client accesses?
Ops, I thought I'm responding here.
The server actually knows which pieces of B-Trees you access. But no more than that.
If it knows what pieces you access, how do you prevent the sever from learning ordering?
It knows the ordering of the encrypted data, but it doesn't know what the data is.
How is that different than cryptDb then? CryptDb only reveals ordering as well (and only if the client requests it.)
Well, actually the server doesn't know the ordering and how pieces of B-Tree refer to each other, it doesn't even know which data form the index and which are the actual data.
Though, observing access patterns, it could probably deduce which data belong to the tree and some info about ordering (which will hold true until we re-balance the tree, which happens on inserts).
I think, if we change objects each time we do queries, we can prevent this data leak.
That seems like it reveals exactly the same kinds of information that range queries reveal.