[anologwintermut]

Not sure how they do it, but it has been done before as a research project 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]

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]

So you use a scheme similar to mOPE? How do you handle tree rebalancing? Is your variant of mOPE deterministic?

[michwill]

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

[swordswinger12]

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?

[anologwintermut]

so ORAM with this on top of it ?

[michwill]

Seems somewhat similar. Though seems like they use deterministic encryption (like AES with same IV), we don't have to do that.