Daniel Golovin

Uniquely Represented Data Structures with Applications to Privacy Degree Type: Ph.D. in Computer Science
Advisor(s): Guy Blelloch
Graduated: December 2008

Abstract:

In a typical application storing some data, if the memory representations of the internal data structures are inspected, they may leave significant clues to the past use of the application. For example, a data structure with lazy deletions might retain an object that the user believes was deleted long ago; this is problematic in environments requiring high security or strict privacy guarantees. We can eliminate such problems entirely by demanding that a data structure implementation store exactly the information specified by an abstract data type (ADT), and nothing more. This property is sometimes called strong history independence. To attain it, it is often necessary and always sufficient to ensure the data structure is uniquely represented. That is, any two sequences of operations which bring the ADT to the same logical state will cause the implementation to generate the same memory representation. This observation begs the following question.

For each abstract data type, what is the added cost for uniquely represented implementations over their conventional counter-parts, in terms of time, space, and randomness?

In this dissertation, we will answer this question for several important abstract data types, and argue that the overhead for unique representation is sufficiently low to warrant its widespread use in high security and high privacy environments. Towards this end, we provide the theoretical foundation for the development of efficient uniquely represented systems that provably store exactly the information their designs specify, and nothing more.

Thesis Committee:
Guy E. Blelloch (Chair)
Gary L. Miller
R. Ravi
Jon M. Kleinberg (Cornell University)

Peter Lee, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Unique Representation, Canonical Forms, History Independence, Oblivious Data Structures, Privacy, Forensics, Data Security