Abstract
Yao's garbled circuit construction is a fundamental construction in cryptography and recent efficiency optimizations have brought it much closer to practice. However, these constructions work only for circuits and garbling a RAM program involves the inefficient process of first converting it into a circuit. Towards the goal of avoiding this inefficiency, Lu and Ostrovsky (Eurocrypt 2013) introduced the notion of "garbled RAM'' as a method to garble RAM programs directly. It can be seen as a RAM analogue of Yao's garbled circuits such that, the size of the garbled program and the time it takes to create and evaluate it, is proportional only to the running time on the RAM program rather than its circuit size.
In this talk, I will describe a construction with strictly poly-logarithmic overhead in both space and time, based only on the minimal and necessary assumption that one-way functions exist. Furthermore, this construction makes only black-box use of one-way functions. This scheme allows for garbling multiple programs being executed on a persistent database.
Based on joint works with Steve Lu, Rafail Ostrovsky, and Alessandra Scafuro.