[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 ?