From the paper: > "Of course, users can encrypt data they outsource to the cloud, but this alone is not sufficient to achieve privacy protection, because the d

From the paper: > "Of course, users can encrypt data they outsource to the cloud, but this alone is not sufficient to achieve privacy protection, because the data access patterns that users exhibit can reveal information about the content of their data (e.g., see [4, 14]). Therefore, there has been considerable amount of recent research on algorithms for data-oblivious algorithms and storage, which hide data access patterns for cloud-based network data management solutions (e.g., see [9, 10, 11, 12, 13, 18, 21, 22, 23, 25, 26])." Even when data is encrypted, you still need to worry about data access patterns leaking information about the encrypted data. The goal of data-oblivious storage is to scramble arrangement to prevent this kind of access pattern side channel attack.