Recently, plenty of researchers are looking at designing efficient data-oblivious algorithms. Roughly speaking, an algorithm is said to be data-oblivious if its data access patterns are independednt of the input i.e. the data access pattern of the algorithm does not leak any information about the input of the algorithm. Few of the algorithms already looked at include sorting, BFS, minimum spanning tree and convex-hull. These oblivious algorithms have various applications for the cloud and efficient secure computation. My queires regarding the same are as follows:
- Is ORAM a generic method to transform any non-oblivious algorithm to its oblivious counterpart?
- Is it always possible to construct a oblivious algorithm with the same asymptotic complexity as that of its non-oblivious counterpart? Please provide me with pointers to works which discuss on the same.