michwill

Oh wow, thanks for the links, will need to go through that!

We've seen gundb [http://gun.js.org/] keeping data distributed between clients. Also, I'm even thinking if it is possible to run ZeroDB on top of SpiderOak's Crypton (which is inspired by ZODB) :-)

In fact, soon we want to switch away from Python pickles (which also could have security problems) into serializing to msgpack. And that makes everything much better in terms of cross-language compatibility.

So, things people dreamed about inside ZODB, pretty much :-)

Heh, yeah.ZODB seems to be pretty good for the purpose here (it's performance is usually not the bottleneck).

But when indexing large texts, it becomes a problem. One way to solve it is instead of using generic serializing for data structures, take real structure into account. Many isinstance() calls cause the CPU bottleneck [http://www.upfrontsystems.co.za/Members/roche/where-im-calli...]. Though, it turns out to be not as bad [http://www.upfrontsystems.co.za/Members/roche/where-im-calli...]

1. Yes, this is a fair problem. Currently common solution is this. You encrypt data with, say, AES, and AES content keys with your public key. Whenever you want to share, you (not cloud) re-encrypt all the content keys for all people you want to share with. This can be pretty computationally expensive. The way to solve this, mentioned in the article - proxy re-encryption. There are such algorithms which allow the cloud to re-encrypt data on your behalf, without knowing your keys. Compromised cloud would have only choice of executing or not executing re-encryption.

2. Same as (1). You either re-encrypt all the content keys on the client side, which could be an expensive process. Or you use proxy re-encryption to let the server re-encrypt data for your new key.

3. That I don't understand. Ok, attacker breaks into remote database. What can he do? When user logs in, he[user] doesn't ever say decryption key to the server. That was the whole point of this article :-)

Oh wow. Do you have a github repo?)

ZeroDB here. We're not homomorphic, and it is possible to make a cloud hosting you're talking about w/o homomorphic encryption.

But if you are to perform heavy computing on server side, you have to be homomorphic. Or other amazing opportunities like decentralized key management, content tokenization (DRM) etc appear from this homomorphic work (even if the speed is 100 times slower than unencrypted)

Yes, that's currently the plan!

More than that: when end-user is SMB but paying customer is a B2B cloud software vendor, needs are often the same as for startups.

ZeroDB co-founder here.

Basically, end-to-end encryption for client (browser, mobile) software vs protecting backend software which uses some flavor of SQL

I think, your points are largely correct. You indeed need to lock multiple buckets when you commit data which could be slow.

My point is that you can tolerate that if your application is something like gmail. Client A has his own tree saved on the server, not intersecting with the tree of client B. Client A probably is not going to write from multiple places simultaneously too often.

But if you have groups of clients writing to the same tree, I think it's better to have some writing client which handles multiple commits of others.

> I assume michwill is probably taking notes!

Yes, you're correct! ;-)

> "one table, one source of truth, period," or "Use for write-seldom; read-often applications only,"

Right. Another model - "write and read only your private information". So, three use-cases here

> information leakage issues

I already think, for solving this we probably should just switch to ORAM. Very valid concern! That said, we cannot really deduce the order of objects referenced in leaf nodes (and there could be a thousand of them).

In any case. Expect our implementation to be extremely simple (but useful) first. Probably suitable for "users record their private info" application. Then we'll be addressing scalability issues, information leakage etc.

Thank you for making a very good comment!

One thing which we will probably inherit from ZODB is server-side versioning of all objects. E.g. if something gets corrupted, it's easy enough to roll back to a previous version.

If the model is "each user has its very own private tree" applies (would be the case for gmail or evernote-like application), I think clients quite can maintain it (having the version history, of course). If it's groups of users having access to the same objects, we should have some maintenance clients.

CryptDB doesn't use homomorfic encryption. It is doing sortable deterministic encryption. E.g. after encryption the server can determine whether a > b or a == b. They have a very good understanding of what data does it leak, when can you do that and when cannot.

In our db, random observer cannot see how data are ordered or whether elements are equal to each other.

Homomorfic encryption would be ideal of course, but it is slow and impractical for the moment

You're right, clients will be responsible for inserting data, re-balancing the tree etc.

HN doesn't allow to reply too deep in the tree of comments, so I continue here.

ZODB on which we base is ACID-complaint, so it cares about simultaneous writes. You either don't use cache, or get invalidation requests if you do (so that you have up-to-date tree if you want to update).

Though, it sounds like the ideal situation is when each user has his own private data, so there are not so many simultaneous writes into the same tree.

Indexes are created where you told them to. So, if you include an arbitrary field, it's probably not going to be indexed to start with. And yes, query is for indexed fields.

I guess, we can have another type of behavior where all new fields are indexed. It doesn't sound like a "clean way" to me, however some developers could desire that

I consider ZODB as more like a framework for quickly building databases. ZODB developers (we've talked to many of them) consider upgrading objects as no-problem (because they have very well understood patterns for that) etc.

While that's ok for Zope/ZODB developers, it's not for an average user. We need to wrap it up to make easily usable, without requiring developers to read tons of documentation and "Design patterns" in advance!

And, obviously, some universal json query language is needed

Usually it's order of 100-200 KB per query but caching things like the tree root makes this footprint smaller (e.g. second query is always faster than first one).

We tested it with pretty ad-hoc parameters (just to check if it's practical at all!), will soon write an automatic optimizer for them, minimizing query time.

Yes, we think about it. This information is not rock-solid and changes with time as the tree re-balances. But for ultimate security, I think, we need something like a proper Oblivious RAM protocol

Yes, you are right. The server stores indexes (which are actually trees), but the query logic is on clients.

For example, full text search over your text queries, or range queries for your numerical data.

The idea is that data in databases is organized in B-Trees, so we traverse those from a remote client. It is fast enough because usually only logarithmic fraction of a tree needs to be seen by the client.

Good question. We thought about two cases. One is when your are sole owner of the data.

The other is when the owner of the data is some group (like JP Chase). In this case we can have server-side quotas for handling cases when one or several clients are compromised. So, in this case it's more about distributing trust

With mongodb, you either pass your key along with query or lose your ability to search. In our case, we don't pass the key to the server, yet having the ability to query

It is scalable enough because you need to download log(index_size) rather than full index.

The use case - any private data which you'd like to encrypt on the server while preserving ability to search. Medical records, financial data, emails are some examples.

Easier to say what this database is not for. Big data applications where you need to use a significant portion of data in the db (like 10%) in map-reduce queries is probably not what ZeroDB would be practical for.

You're right, good that someone is familiar with ZODB!

We plan to make it a full-scale database. For that, we obviously require to have some convenient query language (similar or even compatible with Mongo's).

We've talked to original developers of ZODB and they (independently) suggested that having a language-independent query language is something they constantly thought of :-) In fact, it seems like many of them dream to take ZODB (or a db based on it ;-) where Mongo is now.

Nope, query logic happens on the client, so server doesn't know the key. Client is the one who records data and indexes encrypted, and who uses indexes from remote.

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.

Index sizes are pretty similar (consider the same).

Having the index end-to-end encrypted imposes some limitations though. You have to do several requests when you want to do one query which is obviously slower. Though, still practical.

And since the CPU logic happens on the client, in some cases (many simultaneous clients) the performance can be actually better.

Right at the moment, we don't. The prototype is a proof-of-principle. And the first version will probably have index on pre-computed properties used instead of joins.

But I think proper joins can be implemented with this idea

Well, actually we don't use determenistic encryption, and the server knows nothing about ordering. It merely stores the trees and returns requested pieces (w/o knowing which piece is that or is it a piece of a tree at all).

I find some ideas in MIT mOPE paper similar though

> I'm more concerned about the latency

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.