7 ms·

This feels like a hollow announcement, given that there's no code or design details to look at. I am curious how they intend to let a client run queries agains

by akerl_ 12y ago

This feels like a hollow announcement, given that there's no code or design details to look at. 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.

onezeno 12y ago
Perhaps by using homomorphic encryption? http://en.wikipedia.org/wiki/Homomorphic_encryption http://en.wikipedia.org/wiki/Homomorphic_encryption
- taariqlewis 12y ago
  It was my understanding that homomorphic encryption was not yet ready for deployment. I didn't see that mentioned in the too brief blog post.
- michwill 12y ago
  No. It is possible to do it without HE! Full HE is 10^12 slower than normal computations, so impractical yet. In our case, the actual computations are done on the client
  - davidw 12y ago
    So if I have, say, 10,000 patients, and I want to sort them by name, or search for those whose names begin with 'D', I need to fetch them all first?
    - michwill 12y ago
      To be precise, when you dataset is large, you fetch about log(index_size)
      - tmd83 12y ago
        More than the size of the data read (which I'm not sure how big would actually be) I'm more concerned about the latency. Isn't a lot of normal db server side operation now a fetch-from-db + do-calculation-on-client type operation? 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?
        michwill 12y ago
        > 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.
    - michwill 12y ago
      No, you don't fetch them all. In fact, we tested search over encrypted archives of linux kernel mailing list w/o downloading that :-)
      - michwill 12y ago
        The server knows which pieces of the trees are you reading. That's all it knows.
mwilkison 12y ago
We JUST launched and started working on this but we do want to get code to you all as fast as possible. We'll post a progress update on our blog each week and share it here to keep everyone in the loop.
deleted 12y ago
[deleted]
mtrimpe 12y ago
Not to mention that the any ability to do proper range queries would offer relatively easy ways to hack the encryption. 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.
- michwill 12y ago
  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
  - JoshTriplett 12y ago
    Doesn't that reveal information to the server based on which B-trees the client accesses?
    - michwill 12y ago
      Ops, I thought I'm responding here. The server actually knows which pieces of B-Trees you access. But no more than that.
      - kevinnk 12y ago
        If it knows what pieces you access, how do you prevent the sever from learning ordering?
zvrba 12y ago
Look up private information retrieval (PIR) and oblivious RAM (ORAM). EDIT: This particular bit from the announcement "but we're pushing query logic and decryption keys client-side" seems to point to ORAM. 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.
- michwill 12y ago
  Seems to be similar to ORAM, that's right. And practical enough to be implemented: fulltext search query to aws takes about 0.5 s (not slowing down when multiple clients do these queries in parallel)
  - swordswinger12 12y ago
    How do you handle joins?
    - michwill 12y ago
      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
anologwintermut 12y ago
Not sure how they do it, but it has been done before as a research project http://css.csail.mit.edu/cryptdb/ http://css.csail.mit.edu/cryptdb/. One of the tricks it uses(though by no means the only) is to do a binary search in an index, it actually has the client decrypt a node and compare and then give the server the result.
- michwill 12y ago
  Seems somewhat similar. Though seems like they use deterministic encryption (like AES with same IV), we don't have to do that.
- michwill 12y ago
  Re-read their paper about mOPE. Very similar indeed. The difference is that in our case the server doesn't know the tree structure, with cryptdb it does.
  - swordswinger12 12y ago
    So you use a scheme similar to mOPE? How do you handle tree rebalancing? Is your variant of mOPE deterministic?
    - michwill 12y ago
      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
      - anologwintermut 12y ago
        so ORAM with this on top of it ?
      - swordswinger12 12y ago
        I didn't ask whether you use deterministic encryption, I asked whether your variant of mOPE is deterministic. It's possible to use randomized encryption for the leaves of mOPE and still construct a deterministic OPF. 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?

by akerl_ 12y ago

onezeno 12y ago

Perhaps by using homomorphic encryption? http://en.wikipedia.org/wiki/Homomorphic_encryption http://en.wikipedia.org/wiki/Homomorphic_encryption

taariqlewis 12y ago
It was my understanding that homomorphic encryption was not yet ready for deployment. I didn't see that mentioned in the too brief blog post.
michwill 12y ago
No. It is possible to do it without HE! Full HE is 10^12 slower than normal computations, so impractical yet. In our case, the actual computations are done on the client
- davidw 12y ago
  So if I have, say, 10,000 patients, and I want to sort them by name, or search for those whose names begin with 'D', I need to fetch them all first?
  - michwill 12y ago
    To be precise, when you dataset is large, you fetch about log(index_size)
    - tmd83 12y ago
      More than the size of the data read (which I'm not sure how big would actually be) I'm more concerned about the latency. Isn't a lot of normal db server side operation now a fetch-from-db + do-calculation-on-client type operation? 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?
      - michwill 12y ago
        > 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.
  - michwill 12y ago
    No, you don't fetch them all. In fact, we tested search over encrypted archives of linux kernel mailing list w/o downloading that :-)
    - michwill 12y ago
      The server knows which pieces of the trees are you reading. That's all it knows.

mwilkison 12y ago

We JUST launched and started working on this but we do want to get code to you all as fast as possible. We'll post a progress update on our blog each week and share it here to keep everyone in the loop.

deleted 12y ago

[deleted]

mtrimpe 12y ago

Not to mention that the any ability to do proper range queries would offer relatively easy ways to hack the encryption. 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.

michwill 12y ago
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
- JoshTriplett 12y ago
  Doesn't that reveal information to the server based on which B-trees the client accesses?
  - michwill 12y ago
    Ops, I thought I'm responding here. The server actually knows which pieces of B-Trees you access. But no more than that.
    - kevinnk 12y ago
      If it knows what pieces you access, how do you prevent the sever from learning ordering?

zvrba 12y ago

Look up private information retrieval (PIR) and oblivious RAM (ORAM). EDIT: This particular bit from the announcement "but we're pushing query logic and decryption keys client-side" seems to point to ORAM. 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.

michwill 12y ago
Seems to be similar to ORAM, that's right. And practical enough to be implemented: fulltext search query to aws takes about 0.5 s (not slowing down when multiple clients do these queries in parallel)
- swordswinger12 12y ago
  How do you handle joins?
  - michwill 12y ago
    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

anologwintermut 12y ago

Not sure how they do it, but it has been done before as a research project http://css.csail.mit.edu/cryptdb/ http://css.csail.mit.edu/cryptdb/. One of the tricks it uses(though by no means the only) is to do a binary search in an index, it actually has the client decrypt a node and compare and then give the server the result.

michwill 12y ago
Seems somewhat similar. Though seems like they use deterministic encryption (like AES with same IV), we don't have to do that.
michwill 12y ago
Re-read their paper about mOPE. Very similar indeed. The difference is that in our case the server doesn't know the tree structure, with cryptdb it does.
- swordswinger12 12y ago
  So you use a scheme similar to mOPE? How do you handle tree rebalancing? Is your variant of mOPE deterministic?
  - michwill 12y ago
    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
    - anologwintermut 12y ago
      so ORAM with this on top of it ?
    - swordswinger12 12y ago
      I didn't ask whether you use deterministic encryption, I asked whether your variant of mOPE is deterministic. It's possible to use randomized encryption for the leaves of mOPE and still construct a deterministic OPF. 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?