"The server doesn’t know how individual objects are organized within a tree structure, or whether they even belong to a tree structure at all.
...
When a client performs a query, it asks the server to return buckets of the tree as it traverses it, in a just-in-time fashion"
The server can however infer quite a lot from the order of bucket request, especially which buckets constitute a tree.
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
Comments
"The server doesn’t know how individual objects are organized within a tree structure, or whether they even belong to a tree structure at all. ... When a client performs a query, it asks the server to return buckets of the tree as it traverses it, in a just-in-time fashion"
The server can however infer quite a lot from the order of bucket request, especially which buckets constitute a tree.
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