01224nas a2200145 4500008004100000245008400041210006900125520074800194100001700942700001900959700001800978700002900996700001601025856003701041 2018 eng d00aMore is Less: Perfectly Secure Oblivious Algorithms in the Multi-Server Setting0 aMore is Less Perfectly Secure Oblivious Algorithms in the MultiS3 a
The problem of Oblivious RAM (ORAM) has traditionally been studied in a single-server setting, but more recently the multi-server setting has also been considered. Yet it is still unclear whether the multi-server setting has any inherent advantages, e.g., whether the multi-server setting can be used to achieve stronger security goals or provably better efficiency than is possible in the single-server case. In this work, we construct a perfectly secure 3-server ORAM scheme that outperforms the best known single-server scheme by a logarithmic factor. In the process, we also show, for the first time, that there exist specific algorithms for which multiple servers can overcome known lower bounds in the single-server setting.
1 aChan, Hubert1 aKatz, Jonathan1 aNayak, Kartik1 aPolychroniadou, Antigoni1 aShi, Elaine uhttps://arxiv.org/abs/1809.00825