How to Garble RAM Programs

by Steve Lu and Rafail Ostrovsky

Oded's comments

Following the same theme as in choice Nr 94, but in a different context, this work wishes to obtain an analogue of Yao's garbled-circuits construction (and it various features) for the context of RAMs rather than TMs (without paying the obvious overhead involved in emulating a RAM on a TM). Unlike in choice Nr 94, they cannot take advantage of the (relatively) efficient emulation of RAMs on NTMs (since they cannot assign the non-deterministic work to a powerful prover).

Following is my attempt to outline their solution, assuming familiarity with Yao's garbled-circuits (G-ckts) as well as with Oblivious RAMs (see also choice Nr 94). Recall that the two possible bit values of each input (resp., output) wire of a G-ckt is represented by a pair of random (secret) strings, and the same holds also for all internal wires. The party that evaluates the G-ckt starts with strings that corresponds to the input values and is able to obatin the strings that correspond to the output values (as well as all intermediate values), but it may not know the mapping of strings to values.

Of course, there is no problem to decompose the computation of a circuit to a sequence of gate-evaluations, but in such a case it is crucial that the representation used by the output wire of a gate fit the representation that is used in the input wire of the gate to which the former feeds. (In fact, Yao's construction is nothing but a composition of such gates that have matching wire representation.) Furthermore, the party that constructs all these G-ckts, is the one that chooses the (random string) representation, and so this party can choose these representations as outlined above. (Note, however, that this party should use the same representation only when the wires are to be associated, or else security will be lost.)

Turning to the RAM model, all that changes is that the allocation of which gate feeds to which other gate (via the external memory) is not fixed, but rather determined on the fly by the CPU. If, when constructing the G-ckts, the constructor knows that at Step $i+1$ the CPU will use a value that was determined (written to memory) in Step $j$, then it could just match the representation of the output of Step $j$ with the input of Step $i+1$. Unfortunately, the constructor does not know this a priori (and this becomes known only when Step $i$ is executed). Oblivious RAMs (ORAMs) also do not solve this problem; in them, the distribution of memory accesses is a priori known, but not the actual values assigned under these distributions. Still, starting with an ORAM does help, since typically in ORAMs, when the CPU reads a memory location it ``essentially'' knows at what time this location was last updated.

The solution uses three types of (small) G-ckts:

  1. single-CPU step computers, the $i$th is called $i$-computer;
  2. convertors from some output representation to some input representation;
  3. compilers that generate convertors, where the $i$th such compiler (called $i$-compiler) generates an $(j,i+1)$-covertor for some $j The computers and compilers are constructed and communicated by the sending party (i.e., the constructor), while the convertors (which consist of a single G-gate or table) are generated on-the-fly by executing the compilers.

    The $i$-computer takes (representations of) the contents of the CPU's registers and (respresentations of) the (authentiacted) memory-cell contents (i.e., the contents in some specific address $a$), and produce (i) representations for the updated contents of the CPU registers, (ii) representation of the updated (and autheticated) contents of memory location $a$, and (iii) the address to be read next presented both in the clear and in a representation that fits the $i$-compiler.

    The $i$-compiler takes as input a representation of the seed of the PRF (actually, it can be hard-wired into it!), a representation of an address $a$, and produces a convertor from the representation used in the last writing to addresss $a$ (performed in step $j Actually, one may combine the compiler and the convertor. This combined G-ckt takes as input a representation of the seed of the seed of the PRF (again, it can be hard-wired into it), a representation of an address $a$ and a representation of the corresponding value last written to address $a$ (at time $j

    The original abstract

    See the Crypto eprint record.

    Back to list of Oded's choices.