Feng Li and Xiangfu Song, Nanyang Technological University; Yingying Li, Hangzhou Normal University; Lisha Yao and Guomin Yang, Singapore Management University; Tianwei Zhang, Nanyang Technological University; Robert H. Deng, Singapore Management University
Distributed Oblivious RAM (DORAM) is a promising building block for privacy-preserving cloud databases and outsourced storage systems. However, existing two-server designs often rely on slow linear scans or heavy cryptographic primitives, making them struggle to balance efficiency and bandwidth, and thus hindering their practical deployment.
We present DuetORAM, a two-server DORAM that achieves constant-round access with O(log N) communication while avoiding these computational bottlenecks. Our key idea is a replicated-to-shared block encoding that allows servers to keep identical ciphertexts for efficient PIR-based retrieval, while locally interpreting them as secret shares to enable oblivious eviction via a lightweight shuffle. We further design a secret-shared shuffle with an offline-online decomposition that shifts most bandwidth-intensive work to a preprocessing phase, significantly reducing online communication. We implement a prototype of DuetORAM and evaluate it under diverse network conditions. Our results show that DuetORAM outperforms both the state-of-the-art two-server scheme DUORAM (reducing retrieval latency by up to 170× in LAN settings), and three-server design S^3ORAM (reducing retrieval latency by 1.7× in LAN and accelerating eviction by 7× in LAN and 5× in WAN, respectively).
USENIX Security '26 Open Access Sponsored by
King Abdullah University of Science and Technology (KAUST)
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

author = {Feng Li and Xiangfu Song and Yingying Li and Lisha Yao and Guomin Yang and Tianwei Zhang and Robert H. Deng},
title = {{DuetORAM}: {Two-Server} Distributed {ORAM} with Constant Rounds and O(log N) Communication},
booktitle = {35th USENIX Security Symposium (USENIX Security 26)},
year = {2026},
isbn = {978-1-939133-58-8},
address = {Baltimore, MD},
pages = {4681--4699},
url = {https://www.usenix.org/conference/usenixsecurity26/presentation/li-feng},
publisher = {USENIX Association},
month = aug
}