On Program Obfuscation

Other Titles
Abstract

Program obfuscation is an exciting new area of research with wide-ranging applications and implications throughout cryptography and computer science. The most widely accepted security notion for obfuscation is indistinguishability obfuscation (iO ), which on one hand is surprisingly useful for many applications [134, 42] and on the other hand can plausibly exist [70]. Despite this amazing progress, there are still some barriers to its ambition as a "central hub" in cryptography. Firstly, all known obfuscation mechanisms incur an overhead proportional to the circuit size of the program being obfuscated, leading to a major source of inefficiency. Secondly, there are no plausible, natural intractability assumptions on which these mechanisms can be based. In this thesis we study the above issues. • We construct an indistinguishability obfuscator for Turing machines and RAM programs, where the obfuscation overhead is independent of the running time of the program. • We introduce a natural assumption on multilinear encodings, a candidate for which was provided in the seminal work of [66], and show this assumption, together with other standard hardness assumptions, suffices to construct iO for circuits. • We show methods to bootstrap iO from quantitatively weaker notions of iO (in particular, notions with significantly relaxed efficiency guarantees). In the process of obtaining the above results, we discover fascinating connections between obfuscation and randomized encodings [8, 10]. In particular, we study the notion of randomized encodings in a new setting where the time to encode a program is independent of the running time of a program. We show that this setting for randomized encoding is not only interesting in its own right from a theoretical perspective, but also has many applications in cryptography.

Journal / Series
Volume & Issue
Description
Sponsorship
Date Issued
2016-02-01
Publisher
Keywords
Location
Effective Date
Expiration Date
Sector
Employer
Union
Union Local
NAICS
Number of Workers
Committee Chair
Pass,Rafael N.
Committee Co-Chair
Committee Member
Juels,Ari
Tardos,Eva
Degree Discipline
Computer Science
Degree Name
Ph. D., Computer Science
Degree Level
Doctor of Philosophy
Related Version
Related DOI
Related To
Related Part
Based on Related Item
Has Other Format(s)
Part of Related Item
Related To
Related Publication(s)
Link(s) to Related Publication(s)
References
Link(s) to Reference(s)
Previously Published As
Government Document
ISBN
ISMN
ISSN
Other Identifiers
Rights
Rights URI
Types
dissertation or thesis
Accessibility Feature
Accessibility Hazard
Accessibility Summary
Link(s) to Catalog Record