文摘
Oblivious RAM (ORAM) is a security-provable model that can be used to protect a client’s access pattern to remote storage. Existing ORAM constructions were designed mainly for communication efficiency, but the server-side storage efficiency was generally neglected. This paper proposes DF-ORAM, which has the following features when N blocks each of B bits are outsourced: (i) server-side storage overhead is 3N bits (i.e., no dummy blocks); (ii) no server-side computational cost; (iii) server-client communication cost is \(O(\log N\cdot B)\) bit per query; and (iv) client-side storage cost is \(O(\lambda \cdot B)\) bits where \(\lambda \) is a security parameter. Asymptotical and implementation-based evaluation demonstrate DF-ORAM to be the most communication-efficient and storage-efficient one among the existing ORAMs that do not require server-side computation.