Please note: This PhD defence will take place online.
Sajin Sasy, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Ian Goldberg
Our society is now more than ever heavily dependent on digital data and electronic communications. Every day more of our daily activities move to the digital realm, further entrenching us in this dependency. Unfortunately, along with this transition, we are witnessing a steady increase in cyber attacks and data leakages that undermine the security and privacy of our digital data.
While the majority of online communications today use end-to-end encryption to protect data in transit, the metadata of who is conversing with whom, when, how much, and how often remains unprotected. Such metadata by itself can often reveal a lot about an individual to malicious network adversaries. In the context of digital services, while our personal data is protected in transit via end-to-end encryption, they are eventually stored in the clear in large data centers for processing and extracting utility. Such data centers have hence turned into coveted attack targets for malicious actors. Consequently there is a surge in research towards privacy-preserving computations over data, wherein the underlying data remains protected from malicious actors that could gain unauthorized access to a data center.
One approach towards such privacy-preserving computations that has gained practical traction is Trusted Execution Environments (or TEEs). However, TEEs introduce their own set of challenges. Research has demonstrated TEEs’ susceptibility to side-channel attacks that undermine their purported security and privacy guarantees. In this dissertation, we start by establishing the notion of ‘fully oblivious’ algorithms. By definition such algorithms do not leak any information about the underlying private data they operate over via such side channels.
We then provide several fully oblivious algorithms for the fundamental and recurring data operations of compacting, shuffling, and sorting of data. Oblivious compaction, shuffling, and sorting are core building blocks underlying several privacy-preserving solutions today, and are often the expensive bottleneck of such solutions. Our new algorithms improve over the state-of-the-art approaches for these primitives in some combination of their asymptotics, underlying constants, and parallelizability, and with demonstrable improvements in concrete performance always, enabling efficient and secure deployments of privacy-preserving computations.
Finally, we propose a novel design for a metadata-protecting communication system (MPCS) TEEMS designed to facilitate metadata-protected messaging. While there has been tremendous research towards novel MPCS designs, there has been a clear dearth of MPCS constructions that can simultaneously support (i) low latency, (ii) high throughput, (iii) horizontal scalability, and (iv) asynchronicity. TEEMS presents an MPCS that can simultaneously support all four desirable properties for messaging systems by leveraging our new efficient fully oblivious algorithms as building blocks.