Oblix: an efficient oblivious search index
blog.acolyer.org
blog.acolyer.org
It's on the front page (yay!), but no comments so far. I wonder, are you reading it and pondering the implications or have you dismissed it after reading? (cynically, I guess there would be a lot of comments if that was the case.)
Is this exciting for you? Trivial?
In cryptography, "oblivious" protocols allow users to interact with data in a way that is independent from the underlying memory locations of the data. In other words, you cannot infer anything about the data based on its distribution or access patterns in memory addresses.
The foundation of this concept is oblivious RAM (ORAM), which is a memory model that (simply speaking) makes many redundant calls and operations to memory addresses so that the memory addresses associated with relevant data are obscured (compare with the idea of "padding" operations to make them constant time against side channels). The current state of the art ORAM schemes have O(log n) complexity per access, for data size n.
Now on top of the oblivious memory model we have oblivious data structures, like search indices. Therefore this article is describing an oblivious data structure, which requires its own protocol development and complexity study separate from the underlying ORAM.