ORAM and MPC
In the previous article, we introduced the concept of ORAM and presented a simple implementation – Path ORAM.
We discussed two scenarios: Client / Server and CPU / Memory.
The goal is to prevent the Server from extracting information from the Client’s access pattern.
Similarly, we aim to prevent the Memory from gaining information from the CPU’s access pattern.
Many MPC protocols convert programs into circuits for execution.
If we use the internal wires of a circuit to simulate an array, the circuit complexity for each array access is O(array size).
If there are many accesses and the array is large, the cost can be very high.
However, moving the array outside the circuit risks information leakage.
Therefore, Gordon et al. proposed a solution: using circuit + ORAM.
This means moving the array outside the circuit but protecting the data and data access pattern with ORAM.
The ORAM logic is implemented in the circuit and computed using an MPC protocol. The two parties jointly execute the role of the ORAM client / CPU.
The circuit’s interior is protected by the MPC protocol, so no one knows the data / virtual address.
The circuit’s exterior is protected by ORAM, so no one knows the data / virtual address either.
Pure function + State + Instruction
The original program logic is now divided into segments of pure functions by memory access.
(state, memory value) -> (next instruction, new state)
Whenever a read / write to memory is needed, instead of directly obtaining the value, it produces a read / write instruction with a virtual address, along with the current state.
This instruction is executed by ORAM. The execution result, together with the state, is then passed to the pure function to calculate the next memory instruction and new state.
During this process, only physical memory access instructions are reconstructed from the shares.
In this architecture, there’s no need to use very large arrays as circuit inputs, thus providing an opportunity to achieve sublinear complexity. (ORAM is polylog)
However, the original paper mentions that a more expensive initialization is required. The cost is then amortized over multiple operations.
Because using ORAM with circuits has a cost, this approach is only cost-effective when the array is sufficiently large (> 2^18).
Secure Computation with Sublinear Amortized Work (at 35m38s)
Postscript
RAM is not random access memory.
RAM is random access “machine”.
A basic Turing machine only has a tape. To implement the functionality of x = arr[100], we need 100 steps to move to arr[100].
A random access machine is a Turing machine with random access memory. Reading or writing to arr[100] only takes one step. (Refer to Figure 1.3 in The Design and Analysis of Computer Algorithms)
In Ostrovsky’s ORAM paper, RAM is described using the interactive machines approach from Goldwasser et al.. Two Turing machines, “CPU” and “MEM”, exchange messages. The CPU sends instructions, and MEM sends results. Both Turing machines are message-driven.