PhD Proposal: Trace Oblivious Computation

Talk
Chang Liu
Time: 
10.12.2015 13:30 to 15:00
Location: 

AVW 3258

Privacy preserving computation is attracting increasing attention in recent years, with applications to secure cloud computing and secure multi-party computations. Encryption of data alone is insufficient for privacy. It is imperative that programs' execution behavior leaks no sensitive information about secret inputs. Recent research studies how to leverage a powerful cryptographic tool called \emph{Oblivious RAM} (or ORAM for short) to obfuscate memory access traces. While achieving strong, provable security, existing ORAM techniques incur poly-logarithmic overhead for each memory access.
In preliminary work, I observed that, for certain programs (or portions of a program) whose access traces do not depend on secret inputs, their access traces need not be obfuscated, thus avoiding the ORAM overhead. Therefore, I formally defined the security notion of \emph{trace obliviousness} that a program must satisfy to prevent information leakage through execution traces. In particular, for the secure cloud computing scenario, I defined the notion of \emph{memory trace obliviousness} (or MTO), while for the secure multi-party computation scenario, I defined the notion of \emph{memory- and instruction- trace obliviousness}. I developed programming analysis tools, i.e. \emph{security type systems}, to formally enforce that a given program satisfies trace-obliviousness.
I propose two pieces of work. First, I propose a theory to reason about oblivoius programs. Particularly, the system will enable formally reasoning about the security of an ORAM implementation, which none prior work can achieve. Secondly, I propose to extend the current obliviousness analysis framework to handle distributed computing programs.
Examining Committee:
Dr. Elaine Shi, Chair
Dr. Michael Hicks, Co-Chair
Dr. Jon Froehlich, Dept. Representative
Dr. Dawn Song, Committee Member