Efficient ORAM Based on Binary Tree without Data Overflow and Evictions

ORAM is a useful primitive that allows a client to hide its data access pattern and ORAM technique as a wide range of applications nowadays. In this paper, we propose a verified version of binary-tree-based ORAM with less data access overhead. We provide a new method to reselect the leaf node and write data back to the tree, and accordingly, avoid complicated evict operation. Besides, the bucket capacity is reduced to a constant level. Overall, our scheme improves the efficiency meanwhile maintains security requirement of ORAM.