Struct mc_oblivious_map::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>,  { /* fields omitted */ }

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 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 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<F: FnOnce(u32, &mut A8Bytes<ValueSize>)>(
    &mut self,
    query: &A8Bytes<KeySize>,
    f: F
)

For access: Access 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

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

Remove an entry from the map, by its key.

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.

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

pub fn is_empty(&self) -> bool

Is the map empty

pub 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.

pub 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.