BIOS ORAM: Improved Privacy-Preserving Data Access for Parameterized Outsourced Storage
This work addresses privacy-preserving data access for clients using outsourced storage, offering an incremental improvement in asymptotic efficiency over previous ORAM schemes.
The paper tackles the problem of hiding data access patterns in outsourced storage by introducing BIOS ORAM, a novel ORAM scheme that reduces I/O overhead from logarithmic to polynomial, achieving statistical security and I/O overhead ranging from O(1) to O(log^2 n/(log log n)^2) depending on client-side parameters.
Algorithms for oblivious random access machine (ORAM) simulation allow a client, Alice, to obfuscate a pattern of data accesses with a server, Bob, who is maintaining Alice's outsourced data while trying to learn information about her data. We present a novel ORAM scheme that improves the asymptotic I/O overhead of previous schemes for a wide range of size parameters for client-side private memory and message blocks, from logarithmic to polynomial. Our method achieves statistical security for hiding Alice's access pattern and, with high probability, achieves an I/O overhead that ranges from $O(1)$ to $O(\log^2 n/(\log\log n)^2)$, depending on these size parameters, where $n$ is the size of Alice's outsourced memory. Our scheme, which we call BIOS ORAM, combines multiple uses of B-trees with a reduction of ORAM simulation to isogrammic access sequences.