The intent of this post to clarify any confusion concerning recursion in tree-based ORAM simulators such as Path ORAM (Stefanov et al). Let's store N=7 blocks of bitsize B=4>C*log(7), where C=2. 0 - 0000 1 - 0001 2 - 0010 3 - 0011 4 - 0100 5 - 0101 6 - 0110 We will have Z=1 bucket size in a binary tree of depth 2 and dummy blocks. [0:0000] [1:0001] [4:0100] [2:0010] [3:0011] [5:0101] [6:0110] The client index map 0 - 00 1 - 00 2 - 00 3 - 01 4 - 10 5 - 10 6 - 11 We want to store the index map in a recursive ORAM of the same block size. Since there are at most NlogN bits stored in the index map, we will need at most N(logN-1)/B ≥ 8(log8-1)/4 = 4 blocks to store this data. Compare with the original necessity of storing 7 blocks, and note 4 = ceil 7/C. Explicitly, We store the grouped index map 0 - 0000 1 - 0001 2 - 1010 3 - 11__ where to get an original index i, we instead look up floor i/2 and get the i%2'th slice. We will have Z=1 bucket size in a binary tree of depth 2 and dummy blocks. [0:0000] [1:0001] [_:____] [2:1010] [3:11__] [_:____] [_:____] Note we are only off-by-one from reducing the size of the tree. The client index map 0 - 00 1 - 00 2 - 00 3 - 01 4 - __ 5 - __ 6 - __ Finally, recurse again. We have N'logN'≥(N/C)log(N/C)≥8 bits to store, which will fit in 2 blocks. Note 2 = ceil 7/C/C. Explicitly, We store the grouped index map 0 - 0000 1 - 0001 where to get for an original index i, we instead look up floor i/4 and get the i%4'th slice. We will have Z=1 bucket size in a binary tree of depth 1 and dummy blocks. [0:0000] [1:0001] [_:____] Note we are only off-by-one from reducing the size of the tree. The client index map 0 - 0 1 - 0 2 - _ Thus, the size of the client storage has been reduced by a C^2 factor in exchange for two more lookups in recursive ORAMs. Now, say we wanted the data corresponding to index 5 in the original ORAM. Then we'd need to look floor5/2=2 in the second ORAM, which means we'd need to look up floor2/2=1 in the third ORAM. Check the index map for 1, which corresponds to path 0. We query the third ORAM for path 0, and we get the answer 0011. Since 2%2=0, we obtain the slice 00. Now query the second ORAM for the path 00 (looking for index 2), and we get 1010. Since 5%2=1, we get the slice 10. Finally query the first ORAM for the path 10 (looking for index 5), and we get 0101, the original data. For further clarification, please e-mail surya at [this domain name].