2026-08-17T04:45:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24356 2025-12-12T14:53:39Z ddc:004 open_access

MetaDORAM: Info-Theoretic Distributed ORAM with Less Communication Falk, Brett Hemenway Noble, Daniel Ostrovsky, Rafail ORAM MPC DORAM multi-server ORAM active ORAM A Distributed Oblivious RAM is a multi-party protocol that securely implements a RAM functionality on secret-shared inputs and outputs. This paper presents two information-theoretically secure DORAMs whose communication costs are asymptotic improvements over the state of the art. Let n be the number of memory locations and let d be the bit-length of each location. The first, MetaDORAM1, is statistically secure, with n^{-ω(1)} leakage. It has amortized O(log_b(n) d + b ω(1) log(n) + log³(n)/log(log(n))) bits of communication per memory access. Here, b ≥ 2 is a free parameter and ω(1) is any super-constant function (in n). The most communication-efficient prior statistically secure DORAM was that of Abraham et al (PKC 2017), which has cost O(log_b(n) d + b ω(1) log_b(n) log²(n)). MetaDORAM1 is a Θ(ω(1) log(log(n)))-factor improvement over the work of Abraham et al whenever d = O(log²(n)). The second protocol, MetaDORAM2, achieves perfect security. It has amortized communication cost O(log_b(n)d + b log(n) + log³(n)/log(log(n))) where, again, b ≥ 2 is a free parameter. The best prior perfectly secure DORAM is that of Chan et al (ASIACRYPT 2018) which has communication cost O(log(n) d + log³(n)). MetaDORAM2 is therefore a Ω(log(log(n)))-factor improvement over the DORAM of Chan et al under any parameter range (by setting b = log(n)) and is a Θ(log(n))-factor improvement for d = Ω(n^ε) for any constant ε > 0 (by setting b = d/log(n)). Our work is the first perfectly secure DORAM with sub-logarithmic communication overhead. MetaDORAM2 comes at the cost of a once-off (for any given n) setup phase which requires exponential (in n) computation. Both DORAMs are in the 3-party setting with security against 1 semi-honest, static corruption. By a trivial transformation, these can be transformed, respectively, into statistically and perfectly secure active 3-server ORAM protocols secure against 1 corrupt server, with the same communication costs. These multi-server ORAM protocols are likewise asymptotic improvements over the state of the art. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Brett Hemenway Falk and Daniel Noble and Rafail Ostrovsky 2025 Is Part Of LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2025.6 urn:nbn:de:0030-drops-243560 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.6 eng https://creativecommons.org/licenses/by/4.0/legalcode