Crate mc_oblivious_ram

One of the main ideas in PathORAM is to use a position map, which is recursively an ORAM. The position map is built on top of an ORAM implementation.

Tuning the characteristics of the position map is important for overall performance, and the PathORAM doesn’t really care about those details. So in this implementation, PathORAM contains Box, which allows for sizing and tuning to be done at runtime.

PositionMap also has slightly different initialization from ORAM. You want the PositionMap to begin in a random state, not a zeroed state. But writing random values to all the position maps on initialization is slow. To avoid the need for this, we “implicitly” initialize each position to a value which is the output of a secure block cipher.

The core PathORAM implementation, using PositionMap as a block box, appears in the path_oram module. PathORAM must also use the ORAMStorage to fetch, scan, and return branches in the storage and execute the path ORAM eviction algorithm.

Structs

• CircuitORAM4096Z2Creator
  Creator for CircuitORAM based on 4096-sized blocks of storage and bucket size (Z) of 2, and a basic recursive position map implementation
• CircuitORAM4096Z4Creator
  Creator for CircuitORAM based on 4096-sized blocks of storage and bucket size (Z) of 4, and a basic recursive position map implementation
• CircuitOramDeterministicEvictor
  An evictor that implements a deterministic branch selection in reverse lexicographic order and using the Circuit ORAM eviction strategy
• CircuitOramDeterministicEvictorCreator
  A factory which creates an CircuitOramDeterministicEvictor that evicts from the stash into an additional number_of_additional_branches_to_evict branches in addition to the currently checked out branch in reverse lexicographic order
• ORAMU32PositionMap
  A position map implemented on top of an ORAM Positions are represented as 32 bytes inside a page in an ORAM.
• PathORAM
  An implementation of PathORAM, using u64 to represent leaves in metadata.
• PathORAM4096Z4Creator
  Creator for PathORAM based on 4096-sized blocks of storage and bucket size (Z) of 4, and a basic recursive position map implementation
• PathOramDeterministicEvictor
  An evictor that implements a deterministic branch selection in reverse lexicographic order and using the Path ORAM eviction strategy
• PathOramDeterministicEvictorCreator
  A factory which creates an PathOramDeterministicEvictor that evicts from the stash into an additional number_of_additional_branches_to_evict branches in addition to the currently checked out branch in reverse lexicographic order.
• TrivialPositionMap
  A trivial position map implemented via linear scanning. Positions are represented as 32 bytes inside a page.
• U32PositionMapCreator
  Creates U32 Position Maps, either the trivial one or recursively on top of ORAMs. The value size times the Z value determines the size of an ORAM bucket