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.
No comments:
Post a Comment