For Proper Garbling, Don't Go in Circles!

At Eurocrypt, Daniel Wichs presented a paper entitled "Garbled RAM Revisited" by Craig Gentry, Shai Halevi, Steve Lu, Rafail Ostrovsky, Mariana Raykova, and himself. Their main contribution is to fix a security flaw in a similar paper at last year's Eurocrypt.

The main goal of the two papers is to achieve the equivalent of Yao's garbled circuits for RAM programs. This is desirable because compiling RAM programs to circuits, while possible, can come at a huge cost. As an example, a Google search formulated as a circuit would have to access the whole Internet.

In this context, garbled RAM computation is modeled as a way of outsourcing storage. During a setup phase, a client sends a garbled database to a server. Later, it garbles a small input and a program, which is then evaluated by the server and possible changes the database. This can happen many times. For efficiency, the running time should be proportionate the running time of the RAM programs, and for security, the server should only learn the program output and not even the access pattern of the memory.

An intermediate scheme provides weak security in the sense that the database content and the access pattern are revealed. ORAM then allows to compile such a scheme to a fully secure one.

For the construction, think of the following model for RAM computation: The memory is an array of bits, and the execution proceeds in steps. Every step takes as input the local state and a bit from the memory and outputs the location of the input bit for the next step. The initial and final state correspond to the input and output of the computation, respectively.

It is straightforward to garble the step circuit, the input, and the output. However, garbling the memory bits proves to be harder because the locations of the bits are not static. The previous paper solves this by using a PRF for encoding the bits in the memory and having every step circuit output two encryptions of the possible encoding and the respective garbled label for the next step. However, this introduces a circularity because every step circuit has to include the PRF key and the key to decrypt the output of the previous step.

The authors present two fixes for this. The first one uses IBE and is more efficient with polylogarithmic overhead for circuit creation and computation. The second only uses one-way functions but has overhead N^epsilon for an epsilon > 0.

The first solution requires only public keys in the step circuits and stores bits as secret keys derived from a master key. To allow writing to the memory, a further trick is necessary to avoid another circularity. The ID of the secret keys has to include the time when the location in question was written to at the last time, and the secret is derived in way such that the step circuits can derive the keys for future steps but cannot decrypt for previous steps. Hierarchical IBE can be used for this, but it is not necessary.