I am curious how they intend to let a client run queries against a dataset that the server cannot read without the server having to send all the encrypted data over the wire, or at least an index of all the encrypted data. Which sounds limiting for large datasets.
I find some ideas in MIT mOPE paper similar though
EDIT: Also, you say the server does not know the tree structure. Do you mean it doesn't know the structure until you query, or the structure is always obfuscated (including access patterns and search patterns)?
EDIT2: What is the round complexity of a single query in your protocol?
I've been thinking a lot about this and the only way to handle the problem this tries to solve is to:
* treat the database as a collection of events
* let each event have a visibility that matches our concept of privacy (public | shared with X, Y & Z | private)
* have this communication encrypted using already existing OTR protocols (see some of Moxie Marlinspike's posts on it)
* make the database queryable on this aggregate of event data.
It's really just a case of finding the essential complexity and making it as simple, but not simpler, than that.
The annoying thing is that while it's a tough bullet to bite; it's not even that though. Something like Datomic could already get you halfway there.
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
The server actually knows which pieces of B-Trees you access. But no more than that.
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.
A client can batch multiple inserts but the server cannot batch inserts from multiple clients.
Since the system is fully immutable each update would also include the state of the system it is an update to (which can be outdated.)
Essentially you're modelling human communication with each event being equivalent to a human speech act.
For most cases that would offer sufficient conflict resolution and more expensive commit strategies could be used only where more needed; much like how lattice/CALM-based programming languages such as Bloom deal with distribution.
Yes immutable data makes the inserts O(1) but increases the query costs proportionally to the number of producers.
You need to traverse all possible systems states to do a complete lookup.
Encryption also makes server side pruning and garbage collection of old system state difficult unless you just clear everything greater than n days old.
1) As for the query costs; yes they are there. For public data you could still create pre-computed indexes but for privately shared data the recipients/accessors of that data would need to create appropriate indexes.
In general this scheme indeed requires each producer (person/identity) to also maintain their own indexes.
2) I don't get what you mean by doing a complete lookup.
3) Since this would be a fully federated/decentralized system there would not really be such a thing as server side pruning since the 'server' would just be a peer that indexes public data.
Given that data is immutable clients would simply hold on to the data they need for their calculations and could choose to depend on the server to keep a copy for them.
If nobody (wants to pay to) hold onto a copy of some data anymore then it has been garbage collected.
P.S. Have you looked at the Datomic model? It works quite similar to this proposal with regards to things like storage, peering, computing indexes etc.
I was recently reading a number of ORAM papers, considering to implement something as a side-project to play a bit with modern C++. The overhead is significant, but practical, i.e., far less than homomorphic encryption.
But I think proper joins can be implemented with this idea
In our case, the actual computations are done on the client
And a compromise client can still pull data by running query against the server right? So is the primary improvement that one cannot use database tools to easily export the full dataset? If I know correctly isn't database with encryption support also do dumps and other full db operations encrypted too?
Very valid concern. That is the bottleneck, and that was the first thing we've checked.
> Isn't a lot of normal db server side operation now a fetch-from-db + do-calculation-on-client type operation?
Not if you want to find something. Calculation-on-client is probably html rendering etc.
> And a compromise client can still pull data by running query against the server right?
Yes, but it's ok if you have millions of users, each with his own private data. It would probably cost too much to break into each client's computer (imagine a million bitcoin wallers with 0.1 bitcoin each).
Currently available databases, when used with encryption, store the key in memory. So, memory dump or mitm attack could help an attacker to collect the key.