Black-Box Garbled RAM

Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao's garbled circuit construction, except that known realizations of Garbled RAM make non-black-box use of the underlying cryptographic primitives. In this paper we remove this limitation and provide the first black-box construction of Garbled RAM with polylogarithmic overhead. Our scheme allows for garbling multiple RAM programs being executed on a persistent database and its security is based only on the existence of one-way functions. We also obtain the first secure RAM computation protocol that is both constant round and makes only black-box use of one-way functions in the Oblivious Transfer hybrid model.

Authors

• Sanjam Garg
• Steve Lu 0001
• Rafail Ostrovsky

Keywords

• Random access memory
• Cryptography
• Databases
• Central Processing Unit
• Computer science
• Complexity theory
• Random Access Machine
• Cryptographic Primitives
• One-way Function
• Time And Space
• Running Time
• Root Node
• Input Size
• Tree Level
• Local Memory
• Database Size
• Memory Size
• Access Patterns
• Most Significant Bit
• Fast Forward
• Memory Content
• Multi-party Computation
• Security Parameter
• Single Circuit
• Program Size
• Future Parents
• Left Child
• Input Label
• Negligible Probability
• Number Of Reads
• Tree Nodes
• Security Proof
• Encrypted Form
• Space Cost
• Garbled RAM
• Black-Box Cryptography
• One-Way Functions
• Secure Computation