International Association
for Cryptologic Research

Yao\'s Garbled Circuits is one of the central and one of the most widely used tools in cryptography, both in theory and in practice. It has numerous applications and multiple implementations, as well as over 1800 scientific citations (according to Google Scholar). It\'s applicability comes from multiple desirable features: it can be based on any one-way function (which yields efficient implementations based on block-ciphers such as AES), has minimal interaction, and garbled inputs can be generated given only the knowledge of the cryptographic keys used for garbling inputs and thus input garbling is independent of the garbled circuit structure. However, one of the major drawbacks of Yao\'s Garbled Circuit method is the need to \"compile\" Random Access Machine (RAM) programs into circuits, which often leads to exponential increases both in the garbled program size and in the garbled program running time, compared to the RAM program. Consider, for example, binary search: while the RAM program for binary search can be executed in logarithmic time in its input size, a circuit computation requires a linear-sized representation and work. Nevertheless, the non-interactive nature of Yao\'s Garbled Circuits can sometimes far outweigh the need to compile programs into circuits.

The question that we consider in this paper is this: is it possible to retain all of the desirable features of Yao\'s Garbled Circuits mentioned above, including its non-interactive feature without taking a potentially exponential hit in unrolling RAM programs into circuits? We affirmatively answer this question. In particular, we show how to garble any RAM program (where once garbled, the Garbled RAM program can be executed non-interactively on a single garbled input, just like Yao) so that its garbled program running time increases by a fixed polynomial in the security parameter (just like Yao) times poly-logarithmic quantity both in the input size and the original program running time. The garbled program sizeis proportional to the original program running time times a fixed polynomial in the security parameter times poly-log of the input size. The garbled input (compared to the original input) grows by poly-log in its size times the security parameter.

Just like Garbled Circuits, the input encoding is independent from the specific RAM program that is garbled, and only depends on the input encoding keys, and the recipient of the garbled program can select (parts of) the garbled input via Oblivious Transfer.

As an illustrative example, consider binary search: our result shows that Bob can give data consisting of $n$ sorted private-key encrypted numbers using $O(n * polylog(n))$ encryptions to Alice (assuming each encrypted number fits into a word). Later, Bob can garble any binary search into non-interactive garbled program of size $k^{O(1)} * polylog(n)$, where $k^{O(1)}$ is a fixed polynomial in the security parameter. The binary search query can be chosen and garbled by Bob after he uploaded his data to Alice and without having to remember the data. Alice can execute garbled binary search non-interactively in $k^{O(1)} * polylog(n)$ steps. We stress that the size of our garbled RAM program as well as its running time is only poly-logarithmic in the input size. In contrast, all previous secure protocols for binary search required either programs that were at least linear in the input size or, if sub-linear, required at least logarithmic number of rounds of interaction.

Our result is very general: an arbitrary garbled RAM program can be executed non-interactively with only poly-logarithmic increase in the running time (compared to insecure execution) and the garbled program will retain its compact size even if the program has multiple loops, multiple nested execution branches, recursion, etc.

Our techniques generalize and unify several previous results, including Oblivious RAMs and Yao\'s Garbled Circuits. As a stepping stone towards our general result, under the assumptions that one-way functions exist, we show how to make a one-round Oblivious RAM with poly-log overhead per read/write. Previous poly-log overhead, constant-round RAMs were either not secure or based on pairing-based hardness assumptions. In contrast, our result is based on the necessary assumption of any one way function. In fact, we need only PRFs or any symmetric-key encryption in our construction.