#constant-time #oblivious-ram #hash-table #read

no-std mc-oblivious-map

Implementation of Oblivious Hash Map data structures on top of Oblivious RAM

4 stable releases

2.3.0 Mar 25, 2023
2.2.0 Mar 12, 2022
2.0.0 Apr 17, 2021
1.0.0 Mar 9, 2021

#1211 in Data structures

Download history 27/week @ 2024-07-25 88/week @ 2024-08-01 53/week @ 2024-08-29 70/week @ 2024-09-05 33/week @ 2024-09-12 129/week @ 2024-09-19 153/week @ 2024-09-26 7/week @ 2024-10-03 120/week @ 2024-10-17 100/week @ 2024-10-24 31/week @ 2024-11-07

251 downloads per month

GPL-3.0 license

155KB
2.5K SLoC

mc-oblivious-map

This crate provides an implementation of an oblivious hashmap on top of oblivious RAM, meeting the requirements in the trait described in mc-oblivious-traits.

In crate right now:

  • An implementation of Cuckoo hashing with buckets, using Oblivious RAM as the cuckoo hashing arena. See wikipedia for background. This is close to or the same as CUCKOO-DISJOINT algorithm described by this paper, except for the use of Oblivious RAM. The access-or-insert method is novel in this work, see code comments for discussion.

For more background, see also "power of two choices" hashing (ABKU99, Mitzenmacher). And wikipedia for additional background. This is conceptually an ancestor of cuckoo hashing. The main reason to use this, or cuckoo hashing, in our context, is that it guarantees that reads make exactly two accesses to the table, which makes the constant-time property easy to verify. Cuckoo hashing achieves good memory utilization, better than "power of two choices", which is what we tried first.

Dependencies

~435KB