Eurocrypt 2013, Day 4: How to Garble RAM Programs

The last talk  of Eurocrypt 2013 was given by  Steve Lu on  secure two-party computation via garbling RAM programs (joint work with Rafail Ostrovsky).  He started with  the  motivating example of secure cloud computing, in which there is a client that wants to store some data remotely and then repeatedly a remote server have to perform computations on that data, without knowing the data or the nature of the computation, and the result of the computation. 

The goal of their work is to obtain an analogue Yao's garbled circuits construction for RAM programs, more specifically they show how to garble any RAM program π that runs in t time and has size n in O(t· poly(k,log n)) time, keeping all the non-interactive properties of the Yao’s Garbled circuits and assuming the existence of one-way functions.  This problem  can be trivially solved by representing the program π  as a circuit and then garble it, but unfortunately in some cases this approach can lead to a big blow-up in program size.

The main two ingredients of their solution are Obliviuos RAMs, firstly introduced by  Ostrovsky  and Yao’s Garbled Circuits. The former   enables a client storing only a small amount of data locally to remotely store a large amount of data  and access them while hiding the identities of the items being accessed. The RAM model of computation is used with stored programs and a small stateful CPU that executes a sequence of reads and writes to locations stored on a large memory. Given the CPU state ∑ and the most recently read element x, CPU(∑, x) performs add/mult, updates program counter, executes PRF, outputs the next read/write command and updates the new state ∑’. As for the Yao’s garbled circuit , the construction  is based on three PT algorithms (G,GI,GE), where G is the program garbling algorithm, GI is the input garbling algorithm and GE is the evaluation algorithm.

Steve Lu described these algorithms. In order to garble a RAM program π_t that runs in time t, G generates the garbled circuits  necessary to execute t steps of π_t. Each step consists of a garbled ORAM query followed by a garbled CPU computation in such a way that  the garbling is independent of the actual program path. The garbled program is then sent to the server that can evaluate the program. The GI  algorithm for garbling input is just a time labeled encoding and the GE algorithm performs evaluation of the garbled program executing the same steps as the program garbling algorithm G but evaluating garbled circuits instead of generating them.

The talk ended with the interesting open problem of how to achieve reusable   garbled RAM programs, as has been done in (GKPVZ12) for garbled circuits.