Succinct garbled RAM from indistinguishablity obfuscation

In this thesis, I give the first construction of a succinct garbling scheme for RAM programs. For a program requiring space S and time T to compute, the size of its garbling is Õ(S) instead of poly(T). This construction relies on the existence of indistinguishability obfuscation, as well as the existence of injective one-way functions. As a building block, I introduce and construct a primitive called asymmetrically constrained encryption (ACE). This primitive is an encryption system for which keys can be punctured on succinctly described sets of plaintexts. For programs acting on ACE-encrypted values, I give a natural and general condition for their obfuscations to be indistinguishable, using the fact that the encryption and decryption keys can be separately punctured. This succinct garbling scheme serves as a drop-in replacement for the ubiquitous garbled circuits of Yao, but with better asymptotic parameters. In some cases, these improved parameters allow qualitatively new applications.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Holmgren, Justin Lee

Advisor dc:contributor.advisor

• Shafi Goldwasser.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/100600

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/100600