Efficiency of oblivious algorithms vs non-oblivious algorithms? 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.
Yes. There is an $\Omega(\log n)$ lower bound on ORAM. Therefore directly using ORAM to transform a non-oblivious algorithm to oblivious algorithm would incur a logN overhead. It is an open problem to design an ORAM matching the lower bound.
No. There exists algorithms that do not have more efficient solution. As an apparent example, accessing a memory cell out of N cells requires $O(1)$ time in non-oblivious case but $\Omega(\log n)$ time in oblivious case, implied by the lower bound. I cannot think of more "useful" algorithms since there are not many lower bound proven.


I'm posting two relevant citations:


Nicholas Pippenger and Michael J. Fischer. Relations Among Complexity Measures. Journal of the ACM, Vol. 26, No 2, April 1979, pp 361–381. ACM PDF
Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs. Journal of the ACM, Vol. 43, No 3, May 1996, pp 431–473. doi:10.1.1.44.8961 ACM PDF


[follow up]

Adding more relevant (but incomplete list of) papers.


Goodrich, Michael T. "Randomized shellsort: A simple oblivious sorting algorithm." In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pp. 1262-1277. Society for Industrial and Applied Mathematics, 2010.
Mitchell, John C., and Joe Zimmerman. "Data-oblivious data structures." In LIPIcs-Leibniz International Proceedings in Informatics, vol. 25. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014.
Zahur, Samee, and David Evans. "Circuit structures for improving efficiency of security and privacy tools." In Security and Privacy (SP), 2013 IEEE Symposium on, pp. 493-507. IEEE, 2013.
Goodrich, Michael T., and Michael Mitzenmacher. "Privacy-preserving access of outsourced data via oblivious RAM simulation." In International Colloquium on Automata, Languages, and Programming, pp. 576-587. Springer Berlin Heidelberg, 2011.
Blanton, Marina, Aaron Steele, and Mehrdad Alisagari. "Data-oblivious graph algorithms for secure computation and outsourcing." In Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications security, pp. 207-218. ACM, 2013.
Nikolaenko, Valeria, Stratis Ioannidis, Udi Weinsberg, Marc Joye, Nina Taft, and Dan Boneh. "Privacy-preserving matrix factorization." In Proceedings of the 2013 ACM SIGSAC conference on Computer &amp; communications security, pp. 801-812. ACM, 2013.
Keller, Marcel, and Peter Scholl. "Efficient, oblivious data structures for MPC." In International Conference on the Theory and Application of Cryptology and Information Security, pp. 506-525. Springer Berlin Heidelberg, 2014.
Wang, Xiao Shaun, Kartik Nayak, Chang Liu, T. H. Chan, Elaine Shi, Emil Stefanov, and Yan Huang. "Oblivious data structures." In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pp. 215-226. ACM, 2014.