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.