There exists “a clear need to provide proper confidentiality protection” to outsourced data where the data itself and access to that data is “not under the control of the data owner.” Content protection through encryption alone is not sufficient confidentiality protection. Even if the data is encrypted, an external server can observe every access to physical data blocks. With possible limited other knowledge, confidentiality can be breached; for example, it is possible to “establish correlation of accesses aimed at the same item,” such as different transactions on a particular stock. Not only that, but observing patterns of access to specific blocks of data could, in some cases, even “infer the plaintext order on the encrypted content of the blocks.”

The authors propose a solution to data confidentiality protection that addresses not only content, but also access and pattern confidentiality. That solution employs a shuffle index where the logical data “structure is dynamically reorganized at every access.” Shuffling includes cover searches, which are fake searches that are executed in conjunction with the actual target. The authors feel that the performance overhead generated, which obviously depends upon specific configurations, is acceptable.

The paper goes into great depth in discussing such topics as the correctness and complexity of shuffle index management, execution of range queries, and performance management. All in all, given the increased recognition of and need for true confidentiality protection, this paper should receive strong attention and review by experts in the field.