Mix-ORAM: Using delegate shuffles
This addresses the impracticality of ORAM for clients in private storage on untrusted machines, though it appears incremental by building on mix-net technologies.
The paper tackles the high overhead of client-side re-randomization in Oblivious RAM (ORAM) by securely delegating eviction to semi-trusted third parties, resulting in four designs with reasonable periodic costs to make ORAM more accessible.
Oblivious RAM (ORAM) is a key technology for providing private storage and querying on untrusted machines but is commonly seen as impractical due to the high overhead of the re-randomization, called the eviction, the client incurs. We propose in this work to securely delegate the eviction to semi-trusted third parties to enable any client to accede the ORAM technology and present four different designs inspired by mix-net technologies with reasonable periodic costs.