Paper 2019/071

Repeatable Oblivious Shuffling of Large Outsourced Data Blocks

Zhilin Zhang, Ke Wang, Weipeng Lin, Ada Wai-Chee Fu, and Raymond Chi-Wing Wong


As data outsourcing becomes popular, oblivious algorithms have raised extensive attentions since their control flow and data access pattern appear to be independent of the input data they compute on and thus are especially suitable for secure processing in outsourced environments. In this work, we focus on oblivious shuffling algorithms that aim to shuffle encrypted data blocks outsourced to the cloud server without disclosing the permutation of blocks to the server. Existing oblivious shuffling algorithms suffer from issues of heavy communication and client computation costs when blocks have a large size because all outsourced blocks must be downloaded to the client for shuffling or peeling off extra encryption layers. To help eliminate this void, we introduce the ``repeatable oblivious shuffling'' notation that restricts the communication and client computation costs to be independent of the block size. We present an efficient construction of repeatable oblivious shuffling using additively homomorphic encryption schemes. The comprehensive evaluation of our construction shows its effective usability in practice for shuffling large-sized blocks.

Note: fix some typo errors

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision.10th ACM Symposium on Cloud Computing (SoCC'19)
oblivious shufflingdata outsourcingcloud computing
Contact author(s)
zhilinz @ sfu ca
2019-11-20: last of 2 revisions
2019-01-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zhilin Zhang and Ke Wang and Weipeng Lin and Ada Wai-Chee Fu and Raymond Chi-Wing Wong},
      title = {Repeatable Oblivious Shuffling of Large Outsourced Data Blocks},
      howpublished = {Cryptology ePrint Archive, Paper 2019/071},
      year = {2019},
      doi = {10.1145/3357223.3362732},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.