Back to search

Cornell University

On Program Obfuscation

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2016

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Telang, Sidharth
Chair dc:contributor.chair
  • Pass,Rafael N.
Committee members dc:contributor.committeemember
  • Juels,Ari
  • Tardos,Eva

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
9597224

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Telang, Sidharth. On Program Obfuscation. Doctor of Philosophy thesis, Cornell University, 2016. https://hdl.handle.net/1813/43702