eprint.iacr.orgpaper

Hashing Beats Trees: Practical Oblivious Dictionaries in SGX

An IACR ePrint paper by Erik-Oliver Blass and Travis Mayberry proposing oblivious probabilistic hash tables (chaining, power-of-two-choices, stash-less cuckoo, de-amortized cuckoo hashing) built over Path ORAM as a replacement for oblivious AVL trees when deployed inside Intel SGX enclaves. It shows that SGX's small trusted client memory lets the position map recursion be shrunk to ≤3 levels, making constant-access hash tables beat Θ(log n) tree traversal, and derives via large-scale simulation the concrete padding parameters needed for "double obliviousness" (bounding hash-table rebuild probability to ≤2^-40) that prior ORAM literature lacked. Their SGX implementation reports up to 20x faster lookups and 12x faster inserts than oblivious-tree baselines.