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?
This looks very interesting.<p>I guess that this would be the next-best thing after FHE?.<p>The catch is the performance, right? I mean, the paper says:<p>"In order to make the database end-to-end encrypted yet still capable of performing queries, the client encrypts the
buckets (at the time of creation or modification). The server, which stores the buckets, never knows the encryption
key used. The objects referenced by the leaf nodes of the B-Tree indexes are also encrypted client-side. As a result,
the server doesn’t know how individual objects are organized within the B-Tree or whether they belong to an index
at all. Since ZeroDB is encryption agnostic, probabilistic encryption can ensure that the server cannot even compare
objects for equality.
<i>When a client performs a query, it asks the server to return buckets of the tree as it traverses the index remotely
and incrementally</i>, as in Fig. 2b. The client fetches and decrypts buckets in order to figure out which buckets in the
next level of the tree to fetch next. Frequently accessed buckets can be cached client-side so that subsequent queries
do not make unnecessary network calls."<p>Which would suggest that it might be a bit slow to do many round-trips for each query.<p>I'm guessing there could be some specific use-cases where this is not so relevant?<p>I would love to have some more knowledgeable people comment on this as it would be really neat to be able to start using a DB with these features.
Seems that this initial release only supports python. The client is obviously heavy, since it has to run all the queries, etc. Thankfully the protocol is well defined, so it's just a question of effort to support more languages.<p><a href="https://docs.zerodb.io/" rel="nofollow">https://docs.zerodb.io/</a>
I read the whitepaper, and while I have many questions one detail in particular jumped out at me:<p>"The client authenticates with an X.509 certificate or a self-signed certificate
where the private key is derived from a passphrase. When a passphrase is used, the scrypt algorithm is used to derive
a private key from the passphrase. Information about the salt is stored server-side and is given before establishing an
authenticated encrypted connection.
... The symmetric key is derived from either the passphrase,
the private key in an X.509 certificate, or provided by a key management service (KMS)."<p>You're deriving a private key from a user-defined passphrase, then storing the salt used to derive the password <i>on the server</i>, which is defined to be untrusted. I understand you use scrypt to derive the private key, but this still seems like a massive, massive footgun. Database systems are usually kept up and running for a long time, like maybe even years. If the server gets the salt, isn't it only a matter of time before even a very slow brute-force attack can re-derive the authentication credential and make whatever queries it wants?
I can't help but compare this system to Datomic. Effectively, what ZeroDB is calling the "database" is what Datomic calls a "storage service"; and what ZeroDB is calling the "client", Datomic calls the "transactor."<p>In both architectures, "blocks" of data get pulled from the storage service (database) to the transactor (client), which decodes blocks into rows of tables or indexes, does a query which possibly mutates those tables/indexes, generates new blocks from the mutated tables/indexes, and uploads them.<p>The difference is that ZeroDB's blocks are encrypted by the client, obviously—but I'm not sure that this is a <i>semantic</i> difference in the architectures of the two databases. I'm wondering if an equivalent change could be made to Datomic's transactor logic, without materially affecting the way Datomic works. (The question is basically how much of Datomic's required block <i>metadata</i>, necessary for finding the blocks on the storage service, leaks information which ZeroDB has managed to sequester inside the encrypted blocks instead.)
BTW, you can hop in our Slack [<a href="http://slack.zerodb.io/" rel="nofollow">http://slack.zerodb.io/</a>] channel if you have any questions.
Being able to query/search/sort on encrypted data sounds really powerful and super relevant for this day and age.<p>I look forward to playing around with it.<p>Very cool MacLane!
SQL Server has Always Encrypted - <a href="https://msdn.microsoft.com/en-us/library/mt163865.aspx" rel="nofollow">https://msdn.microsoft.com/en-us/library/mt163865.aspx</a>
OK - So why should I use ZeroDb when it seems to be using Crypt-DB for encrypted query processing [which is the USP of ZeroDb] when cryptDb is fully open source, free and verifiable?
Well...<p>Guess I need to rename <a href="https://github.com/StabbyCutyou/0db" rel="nofollow">https://github.com/StabbyCutyou/0db</a>
Also the name of a popular silent disco company in San Francisco:<p><a href="https://www.facebook.com/ZEROdBsf/" rel="nofollow">https://www.facebook.com/ZEROdBsf/</a><p>Clearly not overlapping business though.