BLUE
Login
EU
ePrint Updates
@eprint.bsky.social
Unofficial bot tracking updates to the IACR Cryptology ePrint Archive (eprint.iacr.org/). Maintained by @str4d.xyz. Currently only posts about new papers. Author names are linkified to Bluesky accounts; contact maintainer for inclusion or removal.
404 followers1 following2.8k posts
EUeprint.bsky.social

Oblivious Single Access Machines: A New Model for Oblivious Computation (Ananya Appan, David Heath, Ling Ren) ia.cr/2024/1029

Abstract. Oblivious RAM (ORAM) allows a client to securely outsource memory storage to an untrusted server. It has been shown that no ORAM can simultaneously achieve small bandwidth blow-up, small client storage, and a single roundtrip of latency. We consider a weakening of the RAM model, which we call the Single Access Machine (SAM) model. In the SAM model, each memory slot can be written to at most once and read from at most once. We adapt existing tree-based ORAM to obtain an oblivious SAM (OSAM) that has O(logn) bandwidth blow-up (which we show is optimal), small client storage, and a single roundtrip. OSAM unlocks improvements to oblivious data structures/algorithms. For instance, we achieve oblivious unbalanced binary trees (e.g. tries, splay trees). By leveraging splay trees, we obtain a notion of caching ORAM, where an access in the worst case incurs amortized O(log²n) bandwidth blow-up and O(logn) roundtrips, but in many common cases (e.g. sequential scans) incurs only amortized O(logn) bandwidth blow-up and O(1) roundtrips. We also give new oblivious graph algorithms, including computing minimum spanning trees and single source shortest paths, in which the OSAM client reads/writes O(|E|⋅log|E|) words using O(|E|) roundtrips, where |E| is the number of edges. This improves over prior custom solutions by a log factor. At a higher level, OSAM provides a general model for oblivious computation. We construct a programming interface around OSAM that supports arbitrary pointer-manipulating programs such that dereferencing a pointer to an object incurs O(logdlogn) bandwidth blowup and O(logd) roundtrips, where d is the number of pointers to that object. This new interface captures a wide variety of data structures and algorithms (e.g., trees, tries, doubly-linked lists) while matching or exceeding prior best asymptotic results. It both unifies much of our understanding of oblivious computation and allows the programmer to write oblivious algorithms combining various common data structures/algorithms and beyond.
Image showing part 2 of abstract.
Image showing part 3 of abstract.
0
EU
ePrint Updates
@eprint.bsky.social
Unofficial bot tracking updates to the IACR Cryptology ePrint Archive (eprint.iacr.org/). Maintained by @str4d.xyz. Currently only posts about new papers. Author names are linkified to Bluesky accounts; contact maintainer for inclusion or removal.
404 followers1 following2.8k posts
HomePopularExplore