Cryptology ePrint Archive: Report 2019/071

Repeatable Oblivious Shuffling of Large Outsourced Data Blocks

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

Abstract: 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.

Category / Keywords: cryptographic protocols / oblivious shuffling, data outsourcing, cloud computing

Original Publication (with minor differences): 10th ACM Symposium on Cloud Computing (SoCC'19)

Date: received 21 Jan 2019, last revised 20 Nov 2019

Contact author: zhilinz at sfu ca

Available format(s): PDF | BibTeX Citation

Note: fix some typo errors

Version: 20191120:182514 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]