Perfect security baseline protocol
For the perfect security / low performance baseline we will do a simple ORAM-based protocol. Server stores the data blocks in ORAM (we will use PathORAM). Client stores B+ tree and when traversing asks server for blocks. ORAM at this point is virtual/fake - it only reports I/Os and correctly answers queries. This will probably require some modifications to B+ tree code. Otherwise, this should not be too hard.