Paper 2023/291

PEO-Store: Practical and Economical Oblivious Store with Peer-to-Peer Delegation

Wenlong Tian, University of South China, Nanyang Technological University
Jian Guo, Nanyang Technological University
Zhiyong Xu, Suffolk University
Ruixuan Li, Huazhong University of Science and Technology
Weijun Xiao, Virginia Commonwealth University

The growing popularity of cloud storage has brought attention to critical need for preventing information leakage from cloud access patterns. To this end, recent efforts have extended Oblivious RAM (ORAM) to the cloud environment in the form of Oblivious Store. However, its impracticality due to the use of probability encryption with fake accesses to obfuscate the access pattern, as well as the security requirements of conventional obliviousness designs, which hinder cloud interests in improving storage utilization by removing redundant data among cross-users, limit its effectiveness. Thus, we propose a practical Oblivious Store, PEO-Store, which integrates the obliviousness property into the cloud while removing redundancy without compromising security. Unlike conventional schemes, PEO-Store randomly selects a delegate for each client to communicate with the cloud, breaking the mapping link between a valid access pattern sequence and a specific client. Each client encrypts their data and shares it with selected delegates, who act as intermediaries with the cloud provider. This design leverages non-interactive zero-knowledge-based redundancy detection, discrete logarithm problem-based key sharing, and secure time-based delivery proof to protect access pattern privacy and accurately identify and remove redundancy in the cloud. The theoretical proof demonstrates that the probability of identifying the valid access pattern with a specific user is negligible in our design. Experimental results show that PEO-Store outperforms state-of-the-art methods, achieving an average throughput of up to 3 times faster and saving 74% of storage space.

Available format(s)
Publication info
Oblivious StoreDelegationZero-Knowledge ProofSecure Deduplication
Contact author(s)
wenlongtian @ usc edu cn
guojian @ ntu edu sg
zxu @ suffolk edu
rxli @ hust edu cn
wxiao @ vcu edu
2023-02-27: approved
2023-02-26: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Wenlong Tian and Jian Guo and Zhiyong Xu and Ruixuan Li and Weijun Xiao},
      title = {PEO-Store: Practical and Economical Oblivious Store with Peer-to-Peer Delegation},
      howpublished = {Cryptology ePrint Archive, Paper 2023/291},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.