Struct CuckooHashTable

pub struct CuckooHashTable<KeySize, ValueSize, BlockSize, RngType, O>
where
    KeySize: ArrayLength<u8> + Add<ValueSize> + PartialDiv<U8> + 'static,
    ValueSize: ArrayLength<u8> + PartialDiv<U8>,
    BlockSize: ArrayLength<u8> + PartialDiv<U8>,
    RngType: RngCore + CryptoRng + Send + Sync + 'static,
    O: ORAM<BlockSize> + Send + Sync + 'static,
    Sum<KeySize, ValueSize>: ArrayLength<u8> + Sub<KeySize, Output = ValueSize> + PartialDiv<U8>,
{ /* private fields */ }

A bucketed cuckoo hash table built on top of oblivious storage.

The Block stored by ORAM is considered as a bucket in the hashing algorithm. The bucket gets broken up into aligned chunks of size KeySize + ValueSize, so the number of items in a bucket is BlockSize / (KeySize + ValueSize)

Implementations

impl<KeySize, ValueSize, BlockSize, RngType, O> CuckooHashTable<KeySize, ValueSize, BlockSize, RngType, O>

where KeySize: ArrayLength<u8> + Add<ValueSize> + PartialDiv<U8> + 'static, ValueSize: ArrayLength<u8> + PartialDiv<U8>, BlockSize: ArrayLength<u8> + PartialDiv<U8>, RngType: RngCore + CryptoRng + Send + Sync + 'static, O: ORAM<BlockSize> + Send + Sync + 'static, Sum<KeySize, ValueSize>: ArrayLength<u8> + Sub<KeySize, Output = ValueSize> + PartialDiv<U8>,

pub fn new<OC, M>(desired_capacity: u64, stash_size: usize, maker: M) -> Self

where OC: ORAMCreator<BlockSize, RngType, Output = O>, M: 'static + FnMut() -> RngType,

Create a new hashmap The ORAM should be default initialized or bad things will happen

Trait Implementations

impl<KeySize, ValueSize, BlockSize, RngType, O> ObliviousHashMap<KeySize, ValueSize> for CuckooHashTable<KeySize, ValueSize, BlockSize, RngType, O>

where KeySize: ArrayLength<u8> + Add<ValueSize> + PartialDiv<U8> + 'static, ValueSize: ArrayLength<u8> + PartialDiv<U8>, BlockSize: ArrayLength<u8> + PartialDiv<U8>, RngType: RngCore + CryptoRng + Send + Sync + 'static, O: ORAM<BlockSize> + Send + Sync + 'static, Sum<KeySize, ValueSize>: ArrayLength<u8> + Sub<KeySize, Output = ValueSize> + PartialDiv<U8>,

fn read( &mut self, query: &A8Bytes<KeySize>, output: &mut A8Bytes<ValueSize>, ) -> u32

To read: Early return if the query is all zero bytes Hash the query (twice) Load the corresponding blocks from ORAM (one at a time) Interpret block as [(KeySize, ValueSize)] Ct-compare the found key with the query If successful, cmov OMAP_FOUND onto result_code and cmov value onto result. Return result_code and result after scanning both loaded blocks

fn access_and_remove<F: FnOnce(u32, &mut A8Bytes<ValueSize>) -> Choice>( &mut self, query: &A8Bytes<KeySize>, f: F, )

For access: Access (without deleting) must be fully oblivious, unlike write

• Checkout both buckets, scan them for the query, copying onto a stack buffer
• Run callback at the stack buffer
• Scan the buckets again and overwrite the old buffer
• If the callback asked to delete the item, also zero out its key.

We would like to be constant-time about whether deletes happened or not, but changing the number of items in the map is a side-effect which we leak some information about, so we can’t be totally principled about that.

fn vartime_write_extended( &mut self, query: &A8Bytes<KeySize>, new_value: &A8Bytes<ValueSize>, allow_overwrite: Choice, allow_sideeffects_and_eviction: Choice, ) -> u32

For writing: The insertion algorithm is, hash the item twice and load its buckets. We always add to the less loaded of the two buckets, breaking ties to the right, that is, prefering to write to oram2. If BOTH buckets overflow, then we choose an item at random from oram1 bucket and kick it out, then we hash that item and insert it into the other bucket where it can go, repeating the process if necessary. If after a few tries it doesn’t work, we give up, roll everything back, and return OMAP_OVERFLOW.

This is amortized constant time, but not constant time due to this relocation. The intuition is that if we treat the hash functons as random functions, we can treat the graph connecting buckets that are both the target of an element as a random graph and with high probability a sparse random graph doesn’t have any cycles. See the proof here: https://cs.stanford.edu/~rishig/courses/ref/l13a.pdf

The access function is an alternative that allows modifying values in the map without taking a variable amount of time.

Note: this function is not generally oblivious with respect to the item being inserted. In many cases, inserts don’t need to be oblivious. It is possible to use this function in such a way as to perform an completely oblivious insert. We will explain that now. This function has some limited data oblivious guarantees:

• If we restrict attention to calling vartime_write on items q which are already in the OMAP, then it is oblivious with respect to such q.
• If we restrict attention to calling vartime_write on items q which are not already in the OMAP, then it is oblivious with respect to these, assuming that the hash function used in the map has a strong PRF property.
• However, calling the function DOES reveal if q is already in the map or not. To avoid leaking this information, and perform a fully oblivious write-or-insert operation, the caller should use the access_and_insert function from the ObliviousHashMap::access_and_insert() trait.

fn len(&self) -> u64

Get the number of items in the map.

fn capacity(&self) -> u64

Get the capacity of the map. TODO: What should this be for the hashmap? At the moment this is number of buckets * bucket size. But this is not an achievable value of len in practice.

fn remove(&mut self, query: &A8Bytes<KeySize>) -> u32

Remove an entry from the map, by its key.

fn is_empty(&self) -> bool

Is the map empty

fn access<F>( &mut self, key: &Aligned<A8, GenericArray<u8, KeySize>>, callback: F, )

where F: FnOnce(u32, &mut Aligned<A8, GenericArray<u8, ValueSize>>),

Access from the map at some position, and forward the value to a callback, which may modify it.

fn vartime_write( &mut self, key: &Aligned<A8, GenericArray<u8, KeySize>>, value: &Aligned<A8, GenericArray<u8, ValueSize>>, allow_overwrite: Choice, ) -> u32

Write to the map at a position.

fn access_and_insert<F, R>( &mut self, key: &Aligned<A8, GenericArray<u8, KeySize>>, default_value: &Aligned<A8, GenericArray<u8, ValueSize>>, rng: &mut R, callback: F, ) -> u32

where F: FnOnce(u32, &mut Aligned<A8, GenericArray<u8, ValueSize>>), R: RngCore + CryptoRng,

Access the map at a position, inserting the item if it doesn’t exist, AND obliviously inserting a new item with a default value and random key if the targetted item DOES exist.