Telang, Sidharth2016-04-042016-04-042016-02-01bibid: 9597224https://hdl.handle.net/1813/43702Program 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.en-USdissertation or thesis