FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 | 4 | 5 |   ...   | 28 |

«Uniquely Represented Data Structures with Applications to Privacy Daniel Golovin CMU-CS-08-135 August 2008 School of Computer Science Carnegie Mellon ...»

-- [ Page 1 ] --

Uniquely Represented Data Structures

with Applications to Privacy

Daniel Golovin


August 2008

School of Computer Science

Carnegie Mellon University

Pittsburgh, PA 15213

Thesis Committee:

Guy E. Blelloch, Chair

Gary L. Miller

R. Ravi

Jon M. Kleinberg, Cornell University

Submitted in partial fulfillment of the requirements

for the degree of Doctor of Philosophy.

Copyright c 2008 Daniel Golovin

This research was sponsored by the National Science Foundation under ITR grants CCR-0122581 (The Aladdin Center) and IIS-0121678.

The views and conclusions contained in this document are those of the author and should not be interpreted as representing the official policies, either expressed or implied, of any sponsoring institution, the U.S. government, or any other entity.

Keywords: Unique Representation, Canonical Forms, History Independence, Oblivious Data Structures, Privacy, Forensics, Data Security 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


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 counterparts, 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) Professor of Computer Science Carnegie Mellon University Gary L. Miller Professor of Computer Science Carnegie Mellon University R. Ravi Professor of Operations Research and Computer Science Carnegie Mellon University Jon M. Kleinberg Professor of Computer Science Cornell University

–  –  –

It takes a special environment to cultivate great scientific research and researchers, and I count myself very fortunate to have found such an environment at Carnegie Mellon. It has been a real privilege to work with many eminent faculty and outstanding colleagues, and I owe them many thanks.

First and foremost I want to thank my advisor, Guy Blelloch. He gave me nearly total independence to pursue whatever research projects interested me, to the point where I more or less acted as a free agent within the computer science department, yet was willing “to roll up his sleeves” and join me in working on tricky problems encountered during our research together. This thesis has benefited greatly from his contributions. Guy also taught me the importance of “thinking big,” optimism, and being fearless in research. I also want to thank my other committee members, R. Ravi, Gary Miller, and Jon Kleinberg, for their encouragement and thoughtful insight. Over the years I have noticed that Ravi’s advice is uncannily good; often I have sought it on a wide range of topics, yet I have never once regretted taking it.

Gary always tried to ensure that research and teaching were not only stimulating but also fun. Jon introduced me to the intellectually rigorous parts of computer science when I was an undergraduate at Cornell, and is largely responsible for my ´ entering the field of computer science in the first place. Together with Eva Tardos, he also introduced me to research in computer science and his example strongly influenced my conception of an ideal scholar. Thanks also to Bruce Maggs, for his unwaivering encouragement, great advice, and amusing jokes.

I also want to thank those coauthors of mine not mentioned above: Konstantin Andreev, Charlie Garrod, Vineet Goyal, Anupam Gupta, Amit Kumar, Adam Meyerson, Viswanath Nagarajan, Florin Oprea, Michael Reiter, Mohit Singh, Stephen F.

Smith, Matt Streeter, Kanat Tangwongsan, and Virginia Vassilevska.

Besides those mentioned above, there were several faculty that helped me at various times during my graduate study. Particular thanks go to Stephen Brookes, vii viii Ziv Bar-Joseph, Avrim Blum, Manuel Blum, Alan Frieze, Mor Harchol-Balter, Bob Harper, Tuomas Sandholm, and Danny Sleator.

Thanks also to my friends and colleagues who helped make my time at Carnegie Mellon enjoyable. Neel Krishnaswami, Vyas Sekar, and Matt Streeter proved excellent conversationalists on a wide range of topics. Ronit Slyper and Jim McCann seem to keep their lives, like the graphics lab in which they work, full of fun toys and cool ideas. Daniel Leeds kept me wondering on the moral implications of recent results in neuroscience (“If the amygdala is damaged in this particular way, the patient loses all empathy for other human beings. Hmmm.”). Mike Gerber, Kevin Bowers, and Paul Massey kept me busy on the racquetball court. Thanks also to David Abraham, Michael Ashley-Rollman, Nina Balcan, David Brumley, Hubert Chan, Shuchi Chawla, Vince Conitzer, Liz Crawford, Michael De Rosa, Jon Derryberry, Kedar Dhamdhere, Mike Dinitz, Abie Flaxman, Deepak Garg, Andrew Gilpin, Varun Gupta, Benoˆ Hudson, Yan Ke, Ryan Kelly, Lea Kissner, Ioannis Koutis, ıt Katrina Ligett, Sean McLaughlin, Viswanath Nagarajan, Sandeep Pandey, Harald R¨cke, Maayan Roth, Don Sheehy, Elaine Runting Shi, Mohit Singh, Amitabh Sinha, a Srinath Sridhar, Joshua Sunshine, Justin Weisz, Adam Wierman, Ryan Williams, Shan Leung Maverick Woo, Noam Zeilberger, and Shuheng Zhou. Thanks also to the Gerbers, Schusters, Fischers, Kleiners, Levaris, Smalls, Tewners, Wassermans, and Hoexters, for helping to make Pittsburgh feel like home.

This research was sponsored by the National Science Foundation under ITR grants CCR-0122581 and IIS-0121678. I would like to thank the NSF and the American taxpayers for their patronage, and I will try to ensure that it redounds to their benefit. (The next phase of my plan to achieve this goal is to move into a significantly higher tax bracket.) Carnegie Mellon’s computer science department provides a fantastic environment in which to conduct research. Thanks to Sharon Burks, Deb Cavlovich, Catherine Copetas, Sophie Park, and the whole jovial and efficient administrative staff for making sure I and the other graduate students could focus on our research and education.

Another interesting feature of the department is its culture, which often takes a playful stance towards the unique building in which it is currently housed, Wean hall. Built in the brutalist architectural style, Wean is a gigantic poured concrete structure that could benefit from some interesting decorations, which the students tend to provide. As I was writing this dissertation some new decorations happened to appear in random locations throughout the building – anonymous poems concerning Wean and its inhabitants. Since the department is scheduled to move into ix new digs at the (currently under construction) Gates-Hillman complex within a year or so, I decided to reproduce one of these poems for posterity, in homage to this fun Carnegie Mellon tradition. See Figure 1. Thanks, anonymous whimsicallymischievous students.

–  –  –

Figure 1: An ode to Wean Hall. This was poem #18 of the many anonymous poems that spontaneously appeared throughout the building in 2008.

Finally, I want to thank my family for all the love and support they have provided over the years. Though it’s a bit of a clich´, my parents always thought e I could do anything I put my mind to. My wife Jennifer provided plenty of love, brownies, and a sympathetic ear. She also did her best to make sure I had a healthy work-life balance, which is not an easy thing to maintain in a very competitive field.

This thesis is dedicated to them.


–  –  –

3.4 The total time to lookup all keys in a map of capacity 220 with x · 220 keys stored in it, as a function of x.................... 48

3.5 The total time to delete all keys from a map of capacity 220 with x · 220 keys stored in it, as a function of x................ 48

3.6 The raw performance ratios of the URHashMap and the Java HashMap for insertions, lookups, and deletions, based on the data displayed in Figures 3.3 through 3.5 and suitably smoothed............ 48

4.1 Two representations of a treap, one standard and one geometric... 56

4.2 Two red-black trees with the same set of keys.............. 57

4.3 A binary search tree rotation about edge {x, y}............. 58

4.4 Pseudocode for merging two uniquely represented heaps....... 65

5.1 A skip list, with the search path for key 12 illustrated.......... 68

5.2 Psuedocode for a hash-consing based labeling scheme......... 72

–  –  –

6.1 Pseudocode for Kalai and Vempala’s “lazy leading tree” [KV05], slightly modified from the original. For Theorem 31, N is set to T /n.... 160 List of Tables

3.1 The correspondence between stable marriage and hashing....... 29

3.2 The space adjusted performance ratios of the URHashMap against that of a separate chaining implementation at loads of 50%, 75%, and 100%. The corresponding loads for the URHashMap are 40%, approximately 46%, and 50%, respectively.................... 47

4.1 The linked list operations, with the running times for a conventional implementation.............................. 51

4.2 The binary search tree operations that our uniquely represented implementation will support......................... 55

4.3 Some additional treap operations our uniquely represented implementation will support. See [SA96] for more detail........... 62

4.4 The heap operations............................ 62

4.5 Running times for various heap implementations with n keys. Running times for binary heaps are taken from [CLRS01], while those for binomial and Fibonacci heaps are either taken from [Koz91] or may be inferred from the implementation described therein...... 63

5.1 The skip list operations that our uniquely represented implementation will support.............................. 68

5.2 Some useful notation and definitions of various structures we maintain for the ordered subsets implementation............... 126

–  –  –

Introduction Consider the following secure redaction problem: an organization possesses a classied version of some document. The organization wants to remove certain sensitive information from the document to create an unclassified version of it which will be released to the public. The unclassified version will then be analyzed by powerful adversaries (henceforth called “observers”) that will try to extract all the information they can from it. You are tasked with preparing the unclassified version of the document. How can you prepare it so as to guarantee that the adversaries cannot learn any sensitive information?

This question is of some practical importance. Hartline et al. [HHM+ 05] describe an example of a CIA document that was released by the New York Times in 2000 as a PDF file with classified information redacted by overlaying black boxes. Unfortunately the overlays could easily be removed revealing key information about the CIA’s role in the 1953 overthrow of the Iranian Government. In 2005 the US military released a PDF report on the accidental shooting of Italian intelligence agent Nicola Calipari in Iraq, again with classified information redacted by overlaying black boxes. Again the overlays could be removed, and among the information revealed was the name of the US military shooter, Mario Lozano. In 2007 the F´d´ration Internationale de l’Automobile leaked confidential technical inforee mation about the McLaren and Ferrari racing cars in much the same way. These are just a few prominent cases among many recent examples of such leaks.

The secure redaction problem is part of a more general problem. Computer users on a typical system leave significant clues to their recent activities, in the form of logs, unflushed buffers, files marked for deletion but not yet deleted, and so on. This can have significant security implications. To address these concerns,

2 Chapter 1: Introduction

the notion of history independent data structures was devised. Roughly, a data structure is history independent if an observer with access to the underlying hardware of the system (i.e., the memory layout of the data structure) can learn no more information than a legitimate user accessing the data structure via its standard interface.

Intuitively, this property is called history independence because the memory layout of the data structure will in general be a function of the historical sequence of operations performed on the system, and so any sensitive information that is leaked can be thought of as containing some information about this historical sequence of operations.

Pages:   || 2 | 3 | 4 | 5 |   ...   | 28 |

Similar works:

«Science and technology in Medieval Islam What is Islam? Islam is a religion that began in the 7th century with the prophet Muhammad in Mecca. Muhammad believed that he was a messenger sent by God to teach people the right way to live. ‘Islam’ is an Arabic word which means ‘submission to God’. The holy book of Islam is the Qur’an (‘Koran’), and the centre for Muslim worship is the ‘House of Prayer’ in Mecca. During the 6th century, Arabia had two powerful neighbours: the...»

«AN INVESTIGATION OF LITHOSPHERIC STRUCTURE AND EVOLUTION IN CONVERGENT OROGENIC SYSTEMS USING SEISMIC RECEIVER FUNCTIONS AND SURFACE WAVE ANALYSIS by Joshua A. Calkins A Dissertation Submitted to the Faculty of the DEPARTMENT OF GEOSCIENCES In Partial Fulfillment of the Requirements For the Degree of DOCTOR OF PHILOSOPHY In the Graduate College THE UNIVERSITY OF ARIZONA August 2008 2 THE UNIVERSITY OF ARIZONA GRADUATE COLLEGE As members of the Dissertation Committee, we certify that we have...»

«Syed ​Zafar​ ul Hussan ​Gilani William Gates Building, 15 JJ Thomson Ave, Cambridge CB3 0FD, UK +44 7459 789978 | ​Cambridge email​ | ​Personal email​ | ​Webpage​ | ​Github​ | ​LinkedIn​ | ​Google Scholar CURRENT RESEARCH INTERESTS: Distributed Systems, Social Network Analysis, Information Propagation/Dissemination EDUCATION: ● Aug 2017, University of Cambridge Doctor of Philosophy (Ph.D.) in Computer Science Dissertation: “Measuring and Modelling the impact of...»

«Osmoticand Stroke-Induced Blood-Brain Barrier Disruption Detected by Manganese-Enhanced Magnetic Resonance Imaging A dissertation submitted to the faculty of Worcester Polytechnic Institute in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Biomedical Engineering by David G. Bennett June 2007 Approved: Christopher H. Sotak, Ph.D. Major Advisor Professor Department of Biomedical Engineering Worcester Polytechnic Institute George D. Pins, Ph.D. Karl G. Helmer,...»

«An Experimental Characterization of a High Degree of Freedom Spark-Ignition Engine to Achieve Optimized Ignition Timing Control by Robert G. Prucka A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Mechanical Engineering) in The University of Michigan 2008 Doctoral Committee: Professor Dionissios N. Assanis, Co-Chair Research Associate Professor Zoran S. Filipi, Co-chair Professor Charles W. Kauffman Gregory L. Ohl, Chrysler LLC Robert...»

«FOREWORD This book gathers some of the essays which are fruits of recent debates and dialogues that have only just begun. The Philosophy of Liberation that I practice, not only in Latin America, but also regarding all types of oppression on the planet (of women, the discriminated races, the exploited classes, the marginalized poor, the impoverished countries, the old and homeless exiled and buried in shelters and asylums, the local religions, the homeless and orphaned children (a lost...»

«3 $74 6 FULL-SCALE LEACHATE-RECIRCULATING MSW LANDFILL BlOREACTOR ASSESSMENTS David A. Carson US. Environmental Protection Agency Risk Reduction Engineering Laboratory (ML-CHL) 26 W. Martin Luther King Drive Cincinnati, Ohio 45268-3001 USA INTRODUCTION The integrated waste management hierarchy philosophy continues to develop as a useful tool to solve solid waste issues in an environmentally respot isible manner. Recent statistics indicate that approximately two thirds of municipal solid waste...»

«Advanced Proton Conducting Polymer Electrolytes for Electrochemical Capacitors by Han Gao A thesis submitted in conformity with the requirements for the degree of Doctor of Philosophy Department of Materials Science & Engineering University of Toronto © Copyright by Han Gao 2015 Advanced Proton Conducting Polymer Electrolytes for Electrochemical Capacitors Han Gao Doctor of Philosophy Department of Materials Science & Engineering University of Toronto Research on solid electrochemical energy...»

«Craft Production and Socio-Economic Marginality Living on the Periphery of Urban Teotihuacan by Mercedes Oralia Cabrera Cortés A Dissertation Presented in Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy Approved March 2011 by the Graduate Supervisory Committee: Barbara L. Stark, Co-Chair George L. Cowgill, Co-Chair Katherine A. Spielmann Steven E. Falconer ARIZONA STATE UNIVERSITY May 2011 ABSTRACT This dissertation investigates socio-economic strategies adopted by...»

«COMBINED EXPERIMENTAL/THEORETICAL APPROACH TOWARD THE DEVELOPMENT OF CARBON TOLERANT ELECTROCATALYSTS FOR SOLID OXIDE FUEL CELL ANODES by Eranda Nikolla A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Chemical Engineering) in The University of Michigan Doctoral Committee: Assistant Professor Suljo Linic, Co-chair Professor Johannes W. Schwank, Co-chair Professor Erdogan Gulari Professor John W. Halloran Professor Phillip E. Savage ©...»

«The Development of Models to Identify Relationships Between First Costs of Green Building Strategies and Technologies and Life Cycle Costs for Public Green Facilities by Yong Han Ahn Dissertation submitted to the faculty of the Virginia Polytechnic Institute and State University in partial fulfillment of the requirements for the degree of Doctor of Philosophy In Environmental Design and Planning Annie R. Pearce, Chair Michael J. Garvin Mido Chang Georg Reichard Norbert M. Lechner February 18,...»

«STABLE ISOTOPE RATIOS OF BENTHIC MARINE FAUNA: DEVELOPING RECORDS OF ANTHROPOGENIC CHANGE A Dissertation Presented to the Faculty of the Graduate School of Cornell University In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy by David Michael Baker February 2010 © 2010 David Michael Baker STABLE ISOTOPE RATIOS OF BENTHIC MARINE FAUNA: DEVELOPING RECORDS OF ANTHROPOGENIC CHANGE David Michael Baker, Ph. D. Cornell University 2010 Worldwide, the escalation of...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.