Crate mc_oblivious_map
source ·Expand description
Implementation of a bucketed cuckoo hash table where the arena is an
oblivious RAM
A cuckoo hash table is a data structure that performs access and removal
using a constant number of operations.
The trick is that our cuckoo hash table is actually 2 orams with 2 different
hash functions. The key is always hashed twice for access, read, and removal
because we guarantee the element must only reside in the location of its
hash in one of the two orams. This also implies that these operations are
oblivious, because we always do 2 oram queries, once per each oram, and
inherit obliviousness from the oram. In our case, each hash bucket is an
oram bucket that can hold multiple values. See
https://www.ru.is/faculty/ulfar/CuckooHash.pdf for a survey of cuckoo hash
using varying numbers of hash functions and bucket size.
Insertion requires variable time and is not usually oblivious. This is ok
for use on things like fog view/ledger where nothing they are inserting is
secret. It is possible to obtain obtain obliviousness for things like
fog-ingest. Please see documentation in [vartime_write_extended()] and
ObliviousHashMap::access_and_insert()
Structs
- A bucketed cuckoo hash table built on top of oblivious storage.
- Factory implementing OMapCreator for this type, based on any ORAM Creator. Otherwise it is very difficult to invoke CuckooHashTable::new() generically